TAOCP, последовательные вопросы распределения

Question

я столкнулся с несколькими проблемами при работе tacop 2.2.2 последовательного распределения, переупаковка раздел памяти на странице 247.

субъект есть п стеков, имеющих общую площадь расположения L0 < L < LX, изначально мы базовый комплект [J] = TOP [J] = L0 для 1 < = J < = п

цель состоит в том, когда происходит переполнение при вставке или удалении элементов относительно в стек I, как переупаковка память. (помещение для стека i, взяв некоторые из столов, которые еще не заполнены).

a). найти наименьший k, для которого i < k < n и TOP [k] < BASE [k + 1], если таковые k существует. (L), для TOP [k]> = L> BASE [i + 1] наконец, Установите BASE [j] -> BASE [j ] + 1, TOP [J] -> TOP [J] + 1, для г < J < к

вот мои вопросы:

как они находят стек, которые не должны быть заполнены? стек k? и почему выбрал самый маленький k?

Answer 1

Чтобы найти стек, который еще не заполнены, основная идея используется факт:

Стек k не полный < ==>TOP[k] < BASE[k+1]

Петля в первом шаг алгоритма работает k от i+1 до n, чтобы найти первый k, который удовлетворяет этому условию.

Также обратите внимание, что изначально все пространство присваивается последнему, n th, путем установки BASE[n] = TOP[n] = L0 и BASE[n+1]=LInfty. Поэтому, если все «более высокие» стеки не заполнены, мы найдем такой номер k.

Ваш второй вопрос (Почему мы выбираем наименьшее такое k?) Более легко ответил: Алгоритм на странице 247 только один способ переупаковка и просто один в этом. Как упоминает Кнут в параграфе чуть выше текста алгоритма:

Несколько способов сделать переупаковку предлагают сами; ... Начнем с предоставления простейшего из методов, и рассмотрим некоторые альтернативы.

Позже Кнут описывает метод переупаковки, который учитывает более раннюю переупаковку, что делает процесс несколько адаптивным.