Подойдя с простой формулой для связанного списка - PullRequest
Новая
       0

Подойдя с простой формулой для связанного списка

2 голосов
/ 28 февраля 2011

Я честно занимался этим уже несколько дней.Я уже реализовал сложную часть этой функции, но теперь есть только одна маленькая вещь.Метод, который я хочу написать, состоит в том, чтобы удалить каждый N-й блок blockSize из связанного списка.Поэтому, если у меня есть связанный список размером 7 {1,2,3,4,5,6,7}, N=2, blockSize=2, я хочу удалить каждый N-й (2-й) блок размера blockSize (2), поэтому удалите 3,4,7.Теперь, чтобы мои циклы for работали, мне нужно написать выражение для значения int, которое я создал, с именем numBlocksRemoved.Он рассчитывает общее количество блоков, которые будут удалены.В этом случае это будет 2. Вот что у меня есть: 

numBlockRemoved=(size/blockSize)/N;

Однако, это работает только иногда, когда цифры выглядят хорошо.Если у меня есть size=8,N=2, blockSize=2, тогда я получаю numBlockRemoved=2, что правильно.Однако для приведенного выше примера я получаю значение int, равное 1, что неверно.Я хочу 2. Я думал об этом, оооочень долго это смешно.Я просто не могу придумать формулу, которая работает для numBlockRemoved.Есть идеи?

Ответы [ 4 ]

3 голосов
/ 28 февраля 2011

Попробуйте 

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, потому что вы не возражаете против неполных блоков.

затем вы пропускаете каждое N, поэтому: 

floor(blocks/N)

floor, потому что вы либо считаете блок, либо нет.

2 голосов
/ 28 февраля 2011

Округление должно быть в сторону увеличения, когда вычисление количества блоков, поскольку неполный блок все еще является блоком (но не при вычислении количества удаленных блоков): 

numBlockRemoved=((size+blockSize-1)/blockSize)/N;
1 голос
/ 28 февраля 2011

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

0 голосов
/ 28 февраля 2011

Просто подумайте об этом систематически - если вы берете каждый N-й блок размера blockSize, вы эффективно удаляете «суперблоки» размера (N * blockSize). Итак, в первом приближении у вас есть 

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 и затем получая слово). ). Так как это происходит, если мы находимся хотя бы на одно число в последнем блоке суперблока, мы должны добавить (blockSize - 1), что дает нам 

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

Какая формула ааза приведена выше. Так что вы можете пойти дальше и отметить его ответ как принятый; Я просто хотел объяснить, как он пришел к этой формуле.

...