Программирование игр и головоломок - [53]

Шрифт
Интервал

− 1 и, следовательно, сохраняет только k − 2 первых ферзей, что вызывает необходимость уменьшить k на 1. Может случиться, что это приведет нас к k = 0, т. е. может случиться, что все места на строке 1 уже исследованы и, следовательно, работа закончена, что мы обозначим как состояние Я, конец программы.

>СБ: k := k − 1;

>  ЕСЛИ k = 0 ТО Я

>    ИНАЧЕ найти место i ферзя k; освободить k, i;

>    найти первое свободное поле на строке k, расположенное правее i, и придать значение этого поля величине i;

>    ЕСЛИ нет таких полей ТО СБ

>    ИНАЧЕ СОК >КОНЕЦ_ЕСЛИ

>  КОНЕЦ_ЕСЛИ

Когда 8 ферзей уже размещены, нужно записывать решение. Бесполезно искать другое место для восьмого ферзя, потому что если на восьмой строке и есть свободное место, то только одно. Таким образом, строка 8 оказывается полностью исследованной и нужно снова размещать 7 предыдущих ферзей. А состояние, в котором строка 8 полностью исследована, — это состояние СБ с k = 8.

>С8: выписать решение;

>  найти место i ферзя 8;

>  освободить 8, i;

> k := 8; СБ

Остается пустить этот процесс в ход. В начале ни один ферзь в игре не участвует и, следовательно, k − 1 = 0. Нужна инициализация, которая бы это открыто провозглашала:

>ПРОГРАММА: k := 1; инициализировать игру; С

Объединим куски. Мы получим программу, реализующую автомат, как мы уже видели в игре 12. Вы можете рассматривать имена, написанные прописными буквами (С, СБ, СОК, С8, ПРОГРАММА) как метки, позволяющие отсылать к части программы, в начале которой стоят эти имена со знаком «:» после них, и как инструкцию ПЕРЕЙТИ К, если они указаны в конце последовательности операций. Поэтому все это непосредственно переводится на совершенно любой язык.

>ПРОГРАММА: k := 1; инициализировать игру; С

>С: ЕСЛИ k = 9 ТО С8

>  ИНАЧЕ искать первое свободное поле на строке k и придать значение этого поля величине i;

>  ЕСЛИ нет таких полей ТО СБ

>  ИНАЧЕ СОК КОНЕЦ_ЕСЛИ

>КОНЕЦ_ЕСЛИ

>>СОК: занять k, i; k := k + 1; С

>СБ: k := k − 1;

>  ЕСЛИ k = 0 ТО Я

>    ИНАЧЕ найти место i ферзя k; освободить k, i;

>    ИСКАТЬ первое свободное поле на строке k, расположенное правее i, и придать значение этого поля величине i;

>    ЕСЛИ нет таких полей ТО СБ

>    ИНАЧЕ СОК >КОНЕЦ_ЕСЛИ

>  КОНЕЦ_ЕСЛИ

>С8: выписать решение;

>  найти место i ферзя 8;

>  освободить 8, i;

> k := 8; СБ

Мы можем улучшить эту программу. Неприятно иметь необходимость находить заново место ферзя в строке, тем более, что знание этого места необходимо дли вывода на экран полученного решения. Заменим i номером c[k] столбца, где расположен ферзь k. Тогда искать место этого ферзя больше не нужно. Именно операция «занять k, i» и будет давать величине c[k] значение i. У нас есть два похожих отрывка в программе:

— в СБ:

>искать первое свободное поле на строке k, расположенное правее i, и придать значение этого поля величине i;

>ЕСЛИ таких полей нет ТО СБ

>ИНАЧЕ СОК КОНЕЦ_ЕСЛИ

— в С:

>искать первое свободное поле на строке k и придать значение этого поля величине i;

>ЕСЛИ таких полей нет ТО СБ

>ИНАЧЕ СОК КОНЕЦ_ЕСЛИ

Второй отрывок идентичен первому, если вместо того, чтобы искать первое свободное поле (что подразумевается как начальный ход), мы потребуем искать первое свободное поле после i, где i придано значение 0. Эту общую последовательность команд мы назовем И (от «искать»). Вот новая программа:

>ПРОГРАММА: k := 1; инициализировать игру; С

>С: ЕСЛИ k = 9 ТО С8

>  ИНАЧЕ c[k] := 0; И

>КОНЕЦ_ЕСЛИ

>КОНЕЦ_ЕСЛИ

>И: искать первое свободное поле на строке k после c[k]

>  и придать значение этого поля величине c[k];

>  ЕСЛИ таких полей нет ТО СБ

>  ИНАЧЕ СОК КОНЕЦ_ЕСЛИ

>>СОК: занять k, c[k]; k := k + 1; С

>СБ: k := k − 1;

>  ЕСЛИ k = 0 ТО Я

>    ИНАЧЕ освободить k, c[k]

>      И

>  КОНЕЦ_ЕСЛИ

>С8: выписать решение;

> k := 8; освободить k, c[k], СБ

Мы можем еще немного выиграть. Значение 9 для k не может быть достигнуто иначе как после размещения ферзя на строке 8 с помощью СОК. Вместо того, чтобы проверять справедливость соотношения к = 9 в С, можно сделать это в СОК. Если нужно разместить восьмого ферзя, то бесполезно требовать «занять k, i» с тем, чтобы сразу после этого освободить указанное поле. Отсюда — новая, еще более простая программа.

>ПРОГРАММА: k := 1; инициализировать игру; С

>С: c[k] := 0; И

>И: искать первое свободное поле на строке k после c[k]

>  и придать значение этого поля величине c[k];

>  ЕСЛИ таких полей нет ТО СБ

>  ИНАЧЕ СОК КОНЕЦ_ЕСЛИ

>>СОК: ЕСЛИ k = 8 ТО записать решение; СБ

>>  ИНАЧЕ занять k, c[k]; k := k + 1; С

>СБ: k := k − 1;

>  ЕСЛИ k = 0 ТО Я

>    ИНАЧЕ освободить k, c[k];

>  КОНЕЦ_ЕСЛИ

Дальше можно выиграть не так уж много, и мы в своих преобразованиях, направленных на улучшение программы, остановимся здесь. Читатель мог бы и удивиться моему способу работать: почему нельзя сразу дать хорошую программу? Потому что, по моему мнению, ее трудно получить сразу. Я мог бы с помощью мелких замечаний представить ее вам без каких-либо промежуточных рассуждений. Читатель был бы восхищен моей сноровкой, но, может быть, заявил бы, что программы такого рода ему самому недоступны, и отказался бы и от этого упражнения, в от остальных упражнений из этого семейства. Если, напротив, читатель находит последнюю программу очевидной, то это потому, что его интуиция намного богаче моей, и он выходит из этой работы ободренный: он еще более ловок, чем автор, браво! И во всех случаях я выигрываю.


Рекомендуем почитать
Изучаем Java EE 7

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


Геймдизайн. Рецепты успеха лучших компьютерных игр от Super Mario и Doom до Assassin’s Creed и дальше

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


Обработка событий в С++

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


MFC и OpenGL

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


Симуляция частичной специализации

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


Питон — модули, пакеты, классы, экземпляры

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