3.3 ПОЛ/ПОТОЛОК: РЕКУРРЕНТНОСТИ

Полы и потолки обеспечивают широкий простор для изучения рекуррентных соотношений. Для начала рассмотрим рекуррентность

Так, например, есть а сама последовательность начинается с чисел Один из авторов этой книги с присущей ему скромностью решил назвать их числами Кнута.

В упр. 25 предлагается подтвердить или опровергнуть, что при любом Несколько только что перечисленных первых К-чисел действительно удовлетворяют этому неравенству, так что имеется некоторое основание считать, что оно справедливо и в общем случае. Попробуем доказать его по индукции. База индукции при вытекает непосредственно из определения рекуррентности. Для индуктивного перехода предположим, что данное неравенство выполняется вплоть до некоторого фиксированного неотрицательного и попробуем показать, что По определению рекуррентности нам известно, что а по индуктивному предположению — что Однако может быть равным самое меньшее может быть равным самое меньшее Самое большее, что можно извлечь из нашего индуктивного предположения, это что явно не дотягивает до неравенства .

Теперь у нас появилось основание усомниться в справедливости неравенства поэтому попытаемся его опровергнуть. Если мы сумеем найти такое, что либо либо -другими словами, такое, что

то получим Возможно ли такое? Но здесь нам лучше воздержаться от ответа, чтобы не испортить упр. 25.

Рекуррентные соотношения, включающие в себя полы и/или потолки, часто возникают в задачах информатики, поскольку алгоритмы, основанные на важном принципе „разделяй и властвуй", зачастую сводят задачу размера к решению тех же задач меньших размеров, являющихся целочисленными долями Например, один из способов сортировки записей при состоит

в том, чтобы разделить их на две примерно равные части: одну — размера а другую — размера . (Кстати, обратите внимание, что

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

Решение этой рекуррентности приводится в упр. 34.

В задаче Иосифа из гл. 1 фигурирует сходная рекуррентность, которой можно придать следующий вид:

Теперь мы располагаем уже большим числом приемов по сравнению с тем, что имели в гл. 1, поэтому рассмотрим более достоверную задачу Иосифа, в которой уничтожается каждый третий, а не каждый второй. Если для решения этой более сложной задачи воспользоваться теми же методами, которые срабатывали в гл. 1, то дело закончится рекуррентностью вида

где — это функция, которой мы вскоре займемся, и или — соответственно при или 2. Но к этой рекуррентности страшно даже подступиться.

Существует другой подход к задаче Иосифа, который приводит к более благоприятной ситуации. Всякий раз, когда один из людей остается нетронутым, ему можно присвоить новый номер. Таким образом, 1-й и 2-й человек становятся а 3-й подвергается казни; 4-й и 5-й человек становятся а 6-й подвергается казни; 2-й человек становятся 3-й подвергается казни и так далее до тех пор, пока человек не подвергнется казни (или не останется в живых). Вот пример перенумерации при

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

Если то жертва с номером должна была иметь некий предыдущий номер, который можно установить следующим образом: поскольку или то Но предыдущий номер был соответственно или Это значит, что он был равен Следовательно, номер оставшегося в живых может быть вычислен следующим образом:

пока выполнять

Это не является выражением для в замкнутой форме это даже не рекуррентность. Но, по крайней мере при большом это позволяет вычислить ответ достаточно быстро.

К счастью, имеется возможность упростить этот алгоритм, воспользовавшись переменной вместо (Такая замена переменных соответствует присвоению номеров, уменьшающихся от до 1, вместо номеров, увеличивающихся от 1 до подобно обратному отсчету времени.) Тогда усложненное правило присвоения значений переменной становится таким:

и предыдущий алгоритм можно переписать следующим образом:

пока выполнять

Ага! Это выглядит гораздо привлекательнее, поскольку очень просто входит в вычисления. Фактически, рассуждая аналогично, можно показать, что если уничтожается каждый человек, то номер уцелевшего может быть вычислен следующим образом:

пока выполнять

В случае который нам столь хорошо знаком, переменная возрастает до при следовательно, . Годится.

В (3.19) реализован способ вычисления последовательности целых чисел, которая может быть определена рекуррентно как

Эти числа, по-видимому, не связаны каким-нибудь простым способом с какими-нибудь известными функциями, за исключением случая следовательно, им вряд ли можно придать привлекательный замкнутый вид. Но если мы согласимся принять последовательность за „известную", то задача Иосифа допускает простое описание: номер уцелевшего равен где к — наименьшее возможное число, такое, что .