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

  ВЕРНУТЬСЯ

ВЕРНУТЬСЯ

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

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

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

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

Покажем сначала, что 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.

Для столбца j нужно найти максимум этой величины, когда i₁ меняется от 1 до n − 1 (n — число строк), а i₂ — от i₁ + 1 до n.

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

В центральном цикле любое введение нового члена может только уменьшить значение минимума.

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

Рассмотрим значения S для строк i и i' > i. Очевидно

S (i, j) = S (i, i' − 1) + S (i', j).

Если S (i, i' − 1) положительно, то S (i, j) > S (i', j) и строка i остается строкой, которая может содержать максимум.

Но если S (i, i' − 1) < 0, то S (i, j) < S (i', j).

Максимум нужно тогда искать либо среди S (i, j) для j < i', либо среди S (i', j) для j ≥ i'.

Заметим, что S (i', i') = а[i'].

Мы собираемся пробежать строку S (1, …) вплоть до первого индекса i₁ , для которого S становится отрицательным. Тогда мы начнем пробегать строку S (i₁ + 1, …), и т. д.

Отсюда следует, что в каждый данный момент нужно знать максимальную подпоследовательность в уже пройденной части; эта подпоследовательность задается номером начала r, номером конца q и своей суммой m. С другой стороны, нужно знать наилучшую заключительную подпоследовательность S (k, i − 1), предполагая, что вектор пройден вплоть до поля i − 1. Обозначим через s значение суммы этой заключительной подпоследовательности. Пусть k — номер отроки, дающий этой сумме максимальное значение, а s — сумма всех членов, начиная с k.

Если сумма s положительна, то она и образует максимум на строке с номером k. При переходе к i число a[i] добавляется к s. Если s отрицательно, то новый элемент с номером i и становится оптимальной строчкой, и нужно взять s = а[i].