Программирование игр и головоломок
Шрифт:
Мы обнаруживаем, что в нашем случае мы не можем объединить два условия с помощью операции И: если i не удовлетворяет условию, что i не больше n, то нельзя поставить вопрос относительно a[i]. Обрисуем трудность подходящим образом:
— нужно либо добавить в таблицу а поле, которое содержит какую-нибудь несущественную для нас величину (мы к этой величине не обращаемся);
— либо нужно допустить, что операция И не коммутативна. Для вычисления t и u мы вычисляем t, и если результат есть ЛОЖЬ, то все кончено и притом с результатом ЛОЖЬ. В противном случае результат есть значение условия u.
Тогда можно использовать наше преобразование:
Первый цикл движется по таблице а, пока обнаруживается, что элементы равны между собой. Более точно, р и i изменяются одинаково, так что разность i– р остается постоянной. Все элементы a[i] сравниваются с одним и тем же элементом, и величина x остается постоянной, равной этому элементу, на протяжении всего цикла.
Второй цикл изменяет i до тех пор, пока не обнаружится пара элементов, отстоящих на р + 1.
Уточним ситуацию выхода из первого внутреннего цикла. Мы собираемся найти конец равнины, которая лучше всех предыдущих, мы фиксируем ее длину р и ее значение х, a i обозначает первый элемент после этой равнины. Мы можем надеяться найти пару j, j– р с
a[j] = a[j– р]
только пока j– р остается на равнине, которую мы собираемся пройти. Наименьшее соответствующее i значение j удовлетворяет условию j– р = i, или j = i + р.
Следовательно, можно увеличивать i от р в обоих циклах, не меняя действия программы, что ускоряет ее работу.
Чтобы ускорить и первый внутренний цикл, мы присвоим переменной x ее значение перед циклом и сохраним ее начальное значение в j. Так как i– р остается постоянным, то можно вычислить значение р также и после выхода из цикла. Начальные значения суть i = j и р = р0, а конечные значения i и р удовлетворяют соотношениям i– р = j– р0, откуда р = i + р0– j:
ПОКА i <= n ВЫПОЛНЯТЬ
Вы можете получить эту программу непосредственно, минуя механизм преобразования программ. Но этот способ кажется мне требующим больших умственных усилий,
Может быть, это связано с ходом мыслей, который я приобрел, преподавая [30] .
Головоломка 35.
Хорошенько учтите то, что вы знаете: обозначим через и таблицу, которая дает последние элементы наилучших возрастающих последовательностей для (всех возможных) длин от 1 до m.
30
Прочтя весь этот ужас, я решил провести решение, основанное на методике из курса программирования механико-математического факультета МГУ.
Каждой последовательности чисел {a1, а2, …, ai} (i >= 1) сопоставим число lmax, равное максимальной длине равнинного участка этой последовательности. Очевидно, что lmax ({a1}) = 1. Пусть мы знаем lmax ({a1, а2, …, ai}). Как вычислить величину lmax ({a1, …, ai, ai+1})? Добавление элемента ai+1 к последовательности {a1, а2, …, ai} не затрагивает равнинных участков этой последовательности, кроме, быть может, последнего. Если ai+1 = ai, то длина этого последнего участка — назовем ее llast ({a1, …, ai}) — увеличивается на единицу. Если величина llast ({a1, …, ai, ai+1}) окажется при этом больше величины lmax ({a1, а2, …, ai}), то это значит, что последний равнинный участок в последовательности {a1, а2, …, ai, ai+1} по крайней мере на 1 длиннее всех предыдущих, и, значит, lmax ({a1, а2, …, ai, ai+1}) = llast ({a1, а2, …, ai, ai+1}).
Введем четыре величины:
i — число рассмотренных членов последовательности,
lmax — максимальная длина равнинного участка для рассмотренных элементов,
llast — длина последнего равнинного участка для рассмотренных элементов,
xlast — последний рассмотренный элемент последовательности (он равен а[i]).
Теперь приведем без пояснений программу, которая вычисляет lmax ({a1, …, an}) по индукции.
Подробнее об этой индуктивной методике можно прочитать в книге: А. Г. Кушниренко, Г. В. Лебедев. Программирование для математиков. — М.: Наука, 1988. — Примеч. ред.