使用簡單的公式鏈接列表

我一直在這個老實說。我已經實現了這個功能的難點，但現在只是一件小事。我想寫的方法是刪除鏈表的每個第N個塊大小。所以，如果我有一個大小爲7 {1,2,3,4,5,6,7}，N=2,blockSize=2的鏈表，我想刪除大小爲blockSize（2）的每個第N（第2）塊，所以刪除3,4,7。現在爲了讓我的循環工作，我需要爲我創建的一個int值寫一個表達式叫做numBlocksRemoved。它計算要刪除的塊的總數。在這種情況下，這將是2.這是我有：使用簡單的公式鏈接列表

numBlockRemoved=(size/blockSize)/N;

然而，這隻能有時，當數字看起來很不錯。如果我有size=8,N=2, blockSize=2，那麼我得到numBlockRemoved=2，這是正確的。但是，對於上面的示例，我得到int值爲1，這是不正確的。我想要2.我已經考慮過這麼漫長的荒謬。我只是不能想出一個適用於numBlockRemoved的公式。有任何想法嗎？計算塊的數量時

來源

2011-02-28 iRobot

對於鏈接列表，你不應該提前計數。事實上，鏈表通常不知道它們的大小。相反，當你到達列表的末尾時，你的循環應該完成。 – aaz 2011-02-28 02:38:15

那麼它是一個自定義鏈表類。每個鏈表都有一個成員變量大小。 – iRobot 2011-02-28 02:39:53

嘗試

floor(ceil(size/blockSize)/N) 

floor(ceil(7/2)/3) = 1 
floor(ceil(7/2)/2) = 2 
floor(ceil(8/2)/2) = 2

的您擁有的街區數量：

blocks = ceil(size/blockSize)

ceil因爲您沒有m ind爲未滿塊。

那麼你跳過每N，所以：

floor(blocks/N)

floor，因爲你要麼算塊或你不知道。

來源

2011-02-28 02:39:46 Eelvex

這也不管用。對於size = 7，N = 2，blockSize = 2，你得到1，但應該是2. – iRobot 2011-02-28 02:41:11

@iRobot：是的，我現在明白了;只是一秒... – Eelvex 2011-02-28 02:41:56

沒有這仍然無法正常工作。嘗試size = 7，N = 3，blockSize = 2。應該是1，但你的產品2 – iRobot 2011-02-28 02:47:14

舍入應該是向上的不完全塊仍然是一個塊（但不計算去除塊的數量時）：

numBlockRemoved=((size+blockSize-1)/blockSize)/N;

來源

2011-02-28 02:33:53 AProgrammer

不，這是不正確的。考慮size = 7，N = 3，blockSize = 2：你得到numBlockRemoved = 2，但它應該是1. – iRobot 2011-02-28 02:39:12

好吧，你只需要向上舍入爲blockSize分區。我會解決我的答案。 – AProgrammer 2011-02-28 02:45:40

(size + (blockSize - 1))/(blockSize * N)

來源

2011-02-28 02:43:44 aaz

不，考慮size = 3，N = 2，blockSize = 1 – iRobot 2011-02-28 02:46:16

我混淆了'blockSize'和'N' - 現在檢查它。 – aaz 2011-02-28 02:48:20

試想一下系統 - 如果你把大小的塊大小的每個第N塊，你有效地消除「超級塊」的大小（N *塊大小）。所以第一近似，你有

nBlocks = floor [size/(N * blockSize)]

現在，從你的榜樣，即使你沒有在最後得到一個完整的塊，你還是想刪除它。如果移除最後一個完整塊之後的剩餘部分多於（N-1）個完整塊，則會發生這種情況。因此算法是

superblock = N * blockSize 
nBlocks = floor (size/superblock) 
remainder = size - (nBlocks * superblock) 
if remainder > (N - 1) * blockSize { 
    nBlocks += 1 
}

可以通過添加將翻倒的大小在一個完整的超級塊當且僅當它小於一個街區（類似於通過舍入的量在端部摺疊1調整到公式加.5然後發言）。由於這種情況，如果我們連一個號碼爲超級塊的最後一塊，我們必須添加（塊大小 - 1），這給了我們

(size + (blockSize - 1))/(blockSize * N)

也就是上面AAZ的公式。所以你可以繼續並將他的答案標記爲已接受;我只想解釋他是如何達到這個公式的。

來源

2011-02-28 15:51:26

使用簡單的公式鏈接列表

回答

相關問題