Программирование игр и головоломок

Второй цикл изменяет i до тех пор, пока не обнаружится пара элементов, отстоящих на р + 1.

Уточним ситуацию выхода из первого внутреннего цикла. Мы собираемся найти конец равнины, которая лучше всех предыдущих, мы фиксируем ее длину р и ее значение х, a i обозначает первый элемент после этой равнины. Мы можем надеяться найти пару j, j– р с

a[j] = a[j– р]

только пока j– р остается на равнине, которую мы собираемся пройти. Наименьшее соответствующее i значение j удовлетворяет условию j– р = i, или j = i + р.

Следовательно, можно увеличивать i от р в обоих циклах, не меняя действия программы, что ускоряет ее работу.

Чтобы ускорить и первый внутренний цикл, мы присвоим переменной x ее значение перед циклом и сохраним ее начальное значение в j. Так как i– р остается постоянным, то можно вычислить значение р также и после выхода из цикла. Начальные значения суть i = j и р = р₀, а конечные значения i и р удовлетворяют соотношениям i– р = j– р₀, откуда р = i + р₀– j:

 i := 1; р := 0

ПОКА i <= n ВЫПОЛНЯТЬ

  x := а[i]; j := i
  ПОКА i <= n И а[i] = x ВЫПОЛНЯТЬ
  i := i + 1
  ВЕРНУТЬСЯ
  р := i + р–  j; i := i + p
  ПОКА i <= n И а[i] /= a[i–  р] ВЫПОЛНЯТЬ
  i := i + 1
  ВЕРНУТЬСЯ
 ВЕРНУТЬСЯ

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

Может быть, это связано с ходом мыслей, который я приобрел, преподавая [30] .

Головоломка 35.

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

30

Прочтя весь этот ужас, я решил провести решение, основанное на методике из курса программирования механико-математического факультета МГУ.

Каждой последовательности чисел {a₁, а₂, …, a_i} (i >= 1) сопоставим число lmax, равное максимальной длине равнинного участка этой последовательности. Очевидно, что lmax ({a₁}) = 1. Пусть мы знаем lmax ({a₁, а₂, …, a_i}). Как вычислить величину lmax ({a₁, …, a_i, a_i+1})? Добавление элемента a_i+1 к последовательности {a₁, а₂, …, a_i} не затрагивает равнинных участков этой последовательности, кроме, быть может, последнего. Если a_i+1 = a_i, то длина этого последнего участка — назовем ее llast ({a₁, …, a_i}) — увеличивается на единицу. Если величина llast ({a₁, …, a_i, a_i+1}) окажется при этом больше величины lmax ({a₁, а₂, …, a_i}), то это значит, что последний равнинный участок в последовательности {a₁, а₂, …, a_i, a_i+1} по крайней мере на 1 длиннее всех предыдущих, и, значит, lmax ({a₁, а₂, …, a_i, a_i+1}) = llast ({a₁, а₂, …, a_i, a_i+1}).

Введем четыре величины:

i — число рассмотренных членов последовательности,

lmax — максимальная длина равнинного участка для рассмотренных элементов,

llast — длина последнего равнинного участка для рассмотренных элементов,

xlast — последний рассмотренный элемент последовательности (он равен а[i]).

Теперь приведем без пояснений программу, которая вычисляет lmax ({a₁, …, a_n}) по индукции.

 i := 1; lmax := 1; llast := 1; xlast := a[1]
 нц покаi < n
  x := a[i + 1]
  если x = xlast то llast := llast + 1
  иначе llast := 1 кесли
  если llast > lmax то lmax := llast кесли
  xlast := x
  i := i + 1
  кц
 вывод lmax

Подробнее об этой индуктивной методике можно прочитать в книге: А. Г. Кушниренко, Г. В. Лебедев. Программирование для математиков. — М.: Наука, 1988. — Примеч. ред.

Покажем сначала, что u_i < u_i+1. Предположим, что это не так: пусть существует такая последовательность длины i + 1, у которой последний элемент не больше u_i. Так как эта последовательность возрастает, то ее предпоследний элемент меньше u_i+1 и потому меньше u_i. Тогда, удаляя последний элемент этой последовательности, мы получили бы последовательность длины i с последним членом, меньшим u_i, что противоречило бы предположению, что u_i — последний элемент последовательности длины i с наименьшим возможным последним элементом.

Рассмотрим теперь следующий элемент x нашего вектора. Разместим его в упорядоченной таблице u. Может случиться, что x > u_m. Тогда элемент x можно присоединить к концу последовательности длины m; тем самым получилась бы (впервые) возрастающая последовательность длины m + 1, которая вследствие своей единственности была бы оптимальна.

Если x меньше u₁, то им следует заменить для построения новой наилучшей последовательности с длиной 1. Если же, наконец, оказывается, что u_i < x < u_i+1, то x можно присоединить к концу последовательности с длиной i + 1, чтобы получить последовательность с длиной i + 1, которая лучше уже известной, и поэтому u_i+1 следует заменить на х. Так как и упорядочена, то вы можете разместить в ней x с помощью дихотомического поиска.

Эта операция требует порядка log₂ m действий для m, не превосходящих n. Так как вам требуется n обращений к таблице, то вы получаете верхнюю границу числа действий порядка n log₂ n, что чрезмерно завышено.

Головоломка 36.

Предположим, что вы уже прошли первую цепочку вплоть до индекса i– 1 и получили наилучшие слова длины р, меняющейся от 1 до m. Вы рассматриваете символ в положении i и ищете его в другой цепочке. Его первое положение j₁ может быть поставлено в конце некоторого слова — скажем, слова длины р₁ — и даст слово длины р₁ + 1, которое окажется лучшим, чем предыдущее: действительно, если j₁ можно поставить после слова длины p₁, то это значит, что его значение больше положения последнего символа в наилучшем слове длины р₁, но меньше положения последнего символа в слове длины p₁ + 1, Рассмотрим теперь второе появление того же символа во второй цепочке: j₂ > j₁. Его нельзя поставить в конце елова длины p₁ + 1, хотя j₂ и больше j₁, потому что это — другое появление того же символа, и их не нужно смешивать. Поэтому достаточно ограничиться по поводу этого появления символа обращением к таблице в ее части от p₁ + 2 до m.

Головоломка 37.

Рассмотрим прямоугольник пробелов, вертикальная граница которого расположена в столбце j и располагающийся вправо от этого столбца в строках от i₁ до i₂. Его основание равно inf (l[i₁ : i₂]), а его площадь есть произведение этого основания на его высоту i₂– i₁ + 1.