Жак Арсак - Программирование игр и головоломок
Название: | Программирование игр и головоломок | |
Автор: | Жак Арсак | |
Жанр: | Литература ХX века (эпоха Социальных революций), Советские издания, Программирование игр | |
Изадано в серии: | неизвестно | |
Издательство: | Наука. Гл. ред. физ.-мат. лит. | |
Год издания: | 1990 | |
ISBN: | 5-02-013959-9 | |
Отзывы: | Комментировать | |
Рейтинг: | ||
Поделись книгой с друзьями! Помощь сайту: донат на оплату сервера |
Краткое содержание книги "Программирование игр и головоломок"
Рассматриваются способы программирования различных занимательных игр и головоломок с числами, геометрическими фигурами и др. Изложение большинства игр и головоломок ведется в несколько этапов. Сначала разъясняется сама постановка задачи и требования, предъявляемые к алгоритму ее решения.
В следующем разделе книги обсуждается сам алгоритм и возможные пути его реализации.
В конце книга по многим играм и головоломкам даются наброски их программной реализации. Используемый при этом язык типа Паскаля допускает перевод на другие широко распространенные языки программирования.
Для начинающих программистов, студентов вузов и техникумов.
Читаем онлайн "Программирование игр и головоломок". [Страница - 88]
Ваша программа должна сохранять симметричную роль обеих цепочек. Не начинайте проверять результат пробега цепочки а, не пробежав цепочки b, и изучайте обе цепочки разом.
Возьмем общую ситуацию:
а пройдена вплоть до i включительно;
b пройдена вплоть до j включительно;
обе части совпадают с точностью до пробелов.
ВЫПОЛНЯТЬ
продвинуть i на следующий символ в а, не являющийся пробелом;
продвинуть j на следующий символ в b, не являющийся пробелом;
ЕСЛИ таких нет в а И таких нет в b ТО
r := ИСТИНА;
КОНЧЕНО КОНЕЦ_ЕСЛИ;
ЕСЛИ таких нет в a ИЛИ таких нет в b ТО
r := ЛОЖЬ;
КОНЧЕНО КОНЕЦ_ЕСЛИ;
ЕСЛИ a[i] ≠ b[j] ТО r := ЛОЖЬ;
КОНЧЕНО КОНЕЦ_ЕСЛИ;
ВЕРНУТЬСЯ
Эта программа совершенно симметрична относительно а и b…
Головоломка 33.
Нужно работать по модулю n. Удобнее всего пронумеровать элементы вектора от 0 до n − 1. Все элементы спускаются вниз на m по модулю n. Элемент, который переходит в 0, имеет номер m; элемент, который переходит в m, имеет номер 2m по модулю n; элемент, который переходит в 2m, имеет номер 3m по модулю n… Таким образом, мы получаем цепочку чисел, кратных m по модулю n. Весь вопрос в том, чтобы узнать, порождает ли последовательность чисел, кратных m по модулю n, последовательность всех целых от 0 до n − 1.
Это так, если m и n взаимно просты. В противном случае пусть с наибольший общий делитель m и n:
m = m'с, n = n'c,
n' * m = n' * m' * с = m' * n = 0 по модулю n.
Эта цепочка возвращается в 0 за n' = n/с операций. При этом пробегается не весь вектор, а только его элементы, сравнимые с 0 по модулю с.
Беря в качестве исходных элементов различных циклов последовательно целые числа от 0 до c − 1, вы разместите все элементы вектора, причем каждый из них будет перемещаться в точности один раз…
Головоломка 34.
Рассмотрите более общую задачу, что заставит вас открыть одно из этих знаменитых «преобразований программы», столь полезных, когда желательно улучшить уже существующие программы. Обозначим через t и u два условия, а через a и b — две последовательности инструкций. Вот простой цикл:
ПОКА t ВЫПОЛНЯТЬ
ЕСЛИ u ТО a ИНАЧЕ b
КОНЕЦ_ЕСЛИ
ВЕРНУТЬСЯ
Последовательность операций следующая:
— проверяется условие t,
— если оно истинно, то проверяется u,
— если u истинно, то выполняется a, и все возобновляется.
Допустим, что условия t и u таковы, что я имею возможность проверить u, даже если проверка условия t дает значение ЛОЖЬ[29]. Тогда, пока условия t и u истинны, в цикле выполняется а.
Вот другая последовательность, которая может встретиться:
— проверяется условие t,
— если оно истинно, то проверяется u,
— если u ложно, то выполняется b, и все возобновляется.
Таким образом, мы приходим к форме, для которой можно доказать, что она всегда эквивалентна исходной (с точностью до ограничения, что должна существовать возможность вычисления и даже в случае, когда t ложно).
ПОКА t ВЫПОЛНЯТЬ
ПОКА t И u ВЫПОЛНЯТЬ а ВЕРНУТЬСЯ
ПОКА t И НЕ u ВЫПОЛНЯТЬ b ВЕРНУТЬСЯ
ВЕРНУТЬСЯ
Мы перепишем программу для определения равнин, чтобы придать ей форму ПОКА, заключенного в скобки ЕСЛИ:
i := 1; р : = 0;
ПОКА i ≤ n ВЫПОЛНЯТЬ
ЕСЛИ a[i] = a[i − р]
ТО x := a[i]; р := р + 1; i := i + 1
ИНАЧЕ i := i + 1
КОНЕЦ_ЕСЛИ
ВЕРНУТЬСЯ
Мы обнаруживаем, что в нашем случае мы не можем объединить два условия с помощью операции И: если i не удовлетворяет условию, что i не больше n, то нельзя поставить вопрос относительно a[i]. Обрисуем трудность подходящим образом:
— нужно либо добавить в таблицу а поле, которое содержит какую-нибудь несущественную для нас величину (мы к этой величине не обращаемся);
— либо нужно допустить, что операция И не коммутативна. Для вычисления t и u мы вычисляем t, и если результат есть ЛОЖЬ, то все кончено и притом с результатом ЛОЖЬ. В противном случае результат есть значение условия u.
Тогда можно использовать наше преобразование:
i := 1; р := 0;
ПОКА i ≤ n ВЫПОЛНЯТЬ
ПОКА --">Книги схожие с «Программирование игр и головоломок» по жанру, серии, автору или названию:
Ээро Хювёнен, Йоуко Сеппянен - Мир Лиспа. Том 1. Введение в язык Лисп и функциональное программирование Жанр: Литература ХX века (эпоха Социальных революций) Год издания: 1990 Серия: Мир Лиспа |
Г. Джоунз - Программирование на языке Оккам Жанр: Другие языки и системы программирования Год издания: 1989 |
У. Клоксин, К. Меллиш - Программирование на языке Пролог Жанр: Руководства и инструкции Год издания: 1987 Серия: Математическое обеспечение ЭВМ |
С. Чери, Г. Готлоб, Л. Танка - Логическое программирование и базы данных Жанр: Базы данных Год издания: 1992 |