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

4 5 6

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

4 5 6 7

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

Новый рассматриваемый элемент изучается с точки зрения возможности его присоединения к концу подпоследовательности длины k , чтобы превратить ее в подпоследовательность длины k + 1. Покажите, что если это возможно, то эта новая последовательность лучше, чем предыдущая подпоследовательность длины k + 1. Может случиться также, что этот новый член оказывается меньше элемента, образующего подпоследовательность длины 1. Тогда он дает лучшую, чем предыдущая, подпоследовательность длины 1.

Таким образом, вы получаете алгоритм, в котором для любого элемента рассматриваемого вектора нужно искать в таблице последние элементы наилучших подпоследовательностей, и размер этой таблицы равен m . Покажите, что эта таблица упорядочена. Осуществите в ней поиск места рассматриваемого элемента вектора с помощью дихотомического поиска [27] См. головоломку 29. — Примеч. пер. и вы получите алгоритм порядка n In n .

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

Вы можете вдохновиться решением предыдущей задачи. Нужно пробежать одну из двух цепочек символ ea символом. Предположим, что мы ее пробежали до некоторого i включительно. Нужно осуществить регистрацию лучших из наиболее длинных слов в порядке возрастания длин, содержащихся в пройденном куске рассматриваемой цепочки и во второй цепочке в целом. Как определить наилучшее слово длины k ? Скажем, что это — такое слово, которое имеет наибольшие шансы оказаться продолжаемым, следовательно, такое слово, у которого положение последнего символа во второй цепочке минимально. Это приводит к рассмотрению того, насколько важно знать положение символов во второй цепочке и, следовательно, к заданию наилучших слов списком из положений в цепочке (например, с помощью конкатенации совпадающих с ними символов во второй цепочке).

Бесспорной выглядит трудность, связанная с тем, что одна и та же буква может встречаться во второй цепочке несколько раз. Их нужно рассмотреть все, но их нельзя смешивать между собой. Я уверен, что это вас надолго не задержит.

Больше я вам ничего не сообщаю. Ищите дальше сами…

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

Вы можете рассмотреть задачу самым простым способом. Пусть задан прямоугольник — координатами x 1, y 1и x 2, y 2верхней левой и нижней правой вершины соответственно. Мы выясняем, является ли этот прямоугольник белым (нет ли внутри черной клетки), и если да, то измеряем его площадь.

Мы проделываем это для x 1, y 1, пробегающих все игровое поле, а x 2, y 2должны удовлетворять неравенствам x 2≥ x 1, y 2≥ y 1и пробегать часть игрового поля, удовлетворяющую этим неравенствам.

Так как для каждого прямоугольника вы должны пробежать его по всей его площади целиком, то порядок роста программы есть n 4. Но вы можете улучшить программу уже здесь, не рассматривая такие точки x 1, y 1, которые не могут дать площади прямоугольника, превосходящей уже найденный максимум (это — близкие к правому краю или к нижнему краю точки игрового поля).

Вы можете сделать еще лучше, задав лучшую информацию. Предположим, например, что у вас есть вектор размерности n , — скажем вектор l такой, что l [ i ] есть число последовательных белых полей на строке i , начиная со столбца l . Тогда вы можете легко найти площади белых прямоугольников, одна из вершин которых находится в точке x 1= j , y 1= i . Нисколько не более трудно перейти и от вектора l для столбца j к вектору, связанному со столбцом j + 1.

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