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

Но это не все. Не позволяйте обмануть себя видимостью. Обе эти программы пробегают вектор элемент за элементом. Если вы составляете вашу программу на Бейсике или LSE, используя операторы ПЕРЕЙТИ К, а не циклы ДЛЯ или FOR, то вы убедитесь, что эти два решения почти неотличимы, а второе решение требует двукратного написания теста, сравнивающего r и p, так что едва ли не чаще эта вторая программа оказывается хуже.

Но есть третья стратегия. Восстановим общую ситуацию: мы прошли часть вектора до номера i включительно и определили наилучшую равнину длины p с общим значением ее элементов, равным x. Точка остановки произвольна.

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

В начале ничего не пройдено: i = 0, и нет ни одного повторения: p = 0.

i := 0; p := 0

ВЫПОЛНЯТЬ

  ЕСЛИ i = n ТО КОНЧЕНО

  КОНЕЦ_ЕСЛИ

  i := i + 1

  ЕСЛИ a[i] = a[i - p] ТО x := a[i]; p := p + 1

  КОНЕЦ_ЕСЛИ

ВЕРНУТЬСЯ

Красиво, не правда ли?

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

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

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

Воспользуемся снова той же самой техникой. Пусть мы прошли вектор вплоть до некоторой точки. Пусть мы получили соответствующие результаты, но, поскольку мы еще не знаем, в какой форме они нужны, мы оставим их на некоторое время неопределенными. В любом случае выглядит вероятным, что мы знаем наибольшую по длине возрастающую подпоследовательность пройденной части, без которой мы как будто лишены возможности добраться до конца вектора… Как и выше, поставим вопрос: насколько изменяет ситуацию появление нового элемента? Он может продолжить известную нам наиболее длинную последовательность, если он может быть поставлен в ее конец, и, следовательно, если он больше последнего элемента этой последовательности. А если зто не так, то эту наиболее длинную подпоследовательность он изменить не может. Но он может продолжить более короткую подпоследовательность, которая постепенно может стать более длинной, если она медленнее растет.

Рассмотрим, например, последовательность

4 5 3 8 2 6 1 7

Если ограничиться тремя первыми элементами, то наиболее длинная возрастающая подпоследовательность — это

4 5

Добавим четвертый элемент, 8. Он может быть присоединен к концу этой подпоследовательности и дает возрастающую подпоследовательность длины 3:

4 5 8

Следующий элемент — 2 — ничего не меняет. Следующий — 6 — не может быть присоединен к концу последовательности длины 3, но он может быть присоединен к концу последовательности длины 2 — последовательности 4 5 — чтобы дать другую подпоследовательность длины 3:

4 5 6

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

4 5 6 7

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

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

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