Жак Арсак - Программирование игр и головоломок

Чтобы ускорить и первый внутренний цикл, мы присвоим переменной x ее значение перед циклом и сохраним ее начальное значение в j . Так как i − р остается постоянным, то можно вычислить значение р также и после выхода из цикла. Начальные значения суть i = j и р = р 0, а конечные значения i и р удовлетворяют соотношениям i − р = j − р 0, откуда р = i + р 0− 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 .

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

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

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

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

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

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

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