Программирование игр и головоломок - [74]
:= i + 1
> ИНАЧЕ i := i + 1
> КОНЕЦ_ЕСЛИ
>ВЕРНУТЬСЯ
Мы обнаруживаем, что в нашем случае мы не можем объединить два условия с помощью операции И: если i не удовлетворяет условию, что i не больше n, то нельзя поставить вопрос относительно a[i]. Обрисуем трудность подходящим образом:
— нужно либо добавить в таблицу а поле, которое содержит какую-нибудь несущественную для нас величину (мы к этой величине не обращаемся);
— либо нужно допустить, что операция И не коммутативна. Для вычисления t и u мы вычисляем t, и если результат есть ЛОЖЬ, то все кончено и притом с результатом ЛОЖЬ. В противном случае результат есть значение условия u.
Тогда можно использовать наше преобразование:
>i := 1; р := 0;
>ПОКА i ≤ n ВЫПОЛНЯТЬ
> ПОКА i ≤ n И а[i] = a[i − р] ВЫПОЛНЯТЬ
> x := а[i]; р := р + 1; i := i + 1
> ВЕРНУТЬСЯ
> ПОКА i ≤ n И а[i] ≠ a[i − р] ВЫПОЛНЯТЬ
> i : = i + 1
> ВЕРНУТЬСЯ
>ВЕРНУТЬСЯ
Первый цикл движется по таблице а, пока обнаруживается, что элементы равны между собой. Более точно, р и i изменяются одинаково, так что разность i − р остается постоянной. Все элементы a[i] сравниваются с одним и тем же элементом, и величина x остается постоянной, равной этому элементу, на протяжении всего цикла.
Второй цикл изменяет i до тех пор, пока не обнаружится пара элементов, отстоящих на р + 1.
Уточним ситуацию выхода из первого внутреннего цикла. Мы собираемся найти конец равнины, которая лучше всех предыдущих, мы фиксируем ее длину р и ее значение х, a i обозначает первый элемент после этой равнины. Мы можем надеяться найти пару j, j − р с
a[j] = a[j − р]
только пока j − р остается на равнине, которую мы собираемся пройти. Наименьшее соответствующее i значение j удовлетворяет условию j − р = i, или j = i + р.
Следовательно, можно увеличивать i от р в обоих циклах, не меняя действия программы, что ускоряет ее работу.
Чтобы ускорить и первый внутренний цикл, мы присвоим переменной 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>2m действий для m, не превосходящих n. Так как вам требуется n обращений к таблице, то вы получаете верхнюю границу числа действий порядка n log>2n, что чрезмерно завышено.
Головоломка 36.
Предположим, что вы уже прошли первую цепочку вплоть до индекса i − 1 и получили наилучшие слова длины р, меняющейся от 1 до m. Вы рассматриваете символ в положении i и ищете его в другой цепочке. Его первое положение j>1 может быть поставлено в конце некоторого слова — скажем, слова длины р>1 — и даст слово длины р>1 + 1, которое окажется лучшим, чем предыдущее: действительно, если j>1 можно поставить после слова длины p>1, то это значит, что его значение больше положения последнего символа в наилучшем слове длины р>1, но меньше положения последнего символа в слове длины p>1 + 1, Рассмотрим теперь второе появление того же символа во второй цепочке: j>2 > j>1. Его нельзя поставить в конце елова длины

Java Enterprise Edition (Java EE) остается одной из ведущих технологий и платформ на основе Java. Данная книга представляет собой логичное пошаговое руководство, в котором подробно описаны многие спецификации и эталонные реализации Java EE 7. Работа с ними продемонстрирована на практических примерах. В этом фундаментальном издании также используется новейшая версия инструмента GlassFish, предназначенного для развертывания и администрирования примеров кода. Книга написана ведущим специалистом по обработке запросов на спецификацию Java EE, членом наблюдательного совета организации Java Community Process (JCP)

Что такое ГЕЙМДИЗАЙН? Это не код, графика или звук. Это не создание персонажей или раскрашивание игрового поля. Геймдизайн – это симулятор мечты, набор правил, благодаря которым игра оживает. Как создать игру, которую полюбят, от которой не смогут оторваться? Знаменитый геймдизайнер Тайнан Сильвестр на примере кейсов из самых популярных игр рассказывает как объединить эмоции и впечатления, игровую механику и мотивацию игроков. Познакомитесь с принципами дизайна, которыми пользуются ведущие студии мира! Создайте игровую механику, вызывающую эмоции и обеспечивающую разнообразие.

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

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

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

Python - объектно-ориентированный язык сверхвысокого уровня. Python, в отличии от Java, не требует исключительно объектной ориентированности, но классы в Python так просто изучить и так удобно использовать, что даже новые и неискушенные пользователи быстро переходят на ОО-подход.