Шрифт:
Второй цикл изменяет 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. — Примеч. ред.
Покажем сначала, что ui < ui+1. Предположим, что это не так: пусть существует такая последовательность длины i + 1, у которой последний элемент не больше ui. Так как эта последовательность возрастает, то ее предпоследний элемент меньше ui+1 и потому меньше ui. Тогда, удаляя последний элемент этой последовательности, мы получили бы последовательность длины i с последним членом, меньшим ui, что противоречило бы предположению, что ui — последний элемент последовательности длины i с наименьшим возможным последним элементом.
Рассмотрим теперь следующий элемент x нашего вектора. Разместим его в упорядоченной таблице u. Может случиться, что x > um. Тогда элемент x можно присоединить к концу последовательности длины m; тем самым получилась бы (впервые) возрастающая последовательность длины m + 1, которая вследствие своей единственности была бы оптимальна.