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

Компьютер анализирует ответ. Если превышено число ходов или ход встречает препятствие, то игрок проигрывает. Если нет — звездочка, изображающая коня, перемещается в новое положение, число оставшихся ходов уменьшается на единицу, и игра продолжается.

Игра 5. Спящая красавица.

Краткое содержание предыдущих эпизодов. Доктор Жабуэ не убил великолепную Жюли, он только приостановил жизненные процессы. Ее мог бы разбудить надлежащий лицевой массаж, но это его не беспокоит, впереди еще много времени. Из замка вывезено все, что имело хоть какую-то ценность: обстановка, картины, произведения искусства… Молодой повеса обнаруживает пустой замок и находит, что он должен быть замечательным треком для мотогонок…

13-й эпизод.

Рыжий Тони входит в темную комнату. Несмотря на грохот мотоцикла, отчетливо воспринимается равномерный храп. Он зажигает фару и обнаруживает безмятежно спящую прекрасную Жюли. Ослепленный ее красотой, он приближается к ней и гладит ее по лицу. Ничего больше и не нужно. Жюли внезапно просыпается и, приходя в сознание с удивительной быстротой, восклицает: «Бежим отсюда скорее, в замке западня, все сейчас взорвется». Тони садится на мотоцикл. Жюли вскакивает на сиденье за Тони и пристегивается к нему. Но уже повсюду гремят взрывы, и огонь охватывает деревянный потолок. Тони мчится зигзагами среди обломков. Обрушиваются куски горящих балок, угрожая раздавить их в любой момент.

Удастся ли им выбраться из замка? Продолжение в следующем эпизоде.

Эта игра является вариантом предыдущей. Вы представляете замок тем же самым прямоугольным пространством, где точки обозначают свободные места, нули — препятствия, а звездочка сообщает местоположение Тони, В начале игры Тони находится в правом нижнем углу, а выход находится в левом верхнем углу. Препятствий вначале крайне мало. После каждого хода Тони компьютер случайным образом формирует новые препятствия и размещает их на игровом поле. Если Тони оказывается на месте одного из них, то он раздавлен и для него все кончено…

Чтобы оставить Тони хоть какой-то шанс, я предпочитаю устанавливать препятствия парами — поочередно вертикальными и горизонтальными. После небольшого наблюдения можно заметить, что движение большей частью идет в тесных коридорах, куда препятствия не могут попасть (нужно по крайней мере два смежных свободных поля, чтобы там могло разместиться препятствие).

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

2. Игры с числами

Арифметические развлечения

Есть много примеров арифметических игр, головоломок и развлечений. Их можно найти в [BAL], [BER], [KUE]. Мы обращаемся и к другим источникам и добавляем некоторые задачи, которые представляют интерес собственно с точки зрения программирования. Многие арифметические головоломки можно сделать вручную: для чего составлять программу? Очень часто вам нужно сделать часть работы на руках, а машина сделает остальное. Это вы должны правильно распределить работу, иначе время вычисления может оказаться чрезмерным. Строгих правил здесь нет. Одна и та же задача может иметь много решений, и методы решения одной и той же задачи могут быть различными. Это и создает игровую ситуацию.

Группировка различных головоломок по темам более или менее условна. Начнем с наиболее простых задач.

ДЛЯ РАЗМИНКИ.

Головоломка 3. Вращающееся число.

Найти такое число, оканчивающееся на 5, что, умножая его на 5, мы получим новое число, полученное из предыдущего вычеркиванием цифры 5 на конце и приписыванием ее в начале.

Это легко…

Та же задача с заменой 5 на 2.

Можно ли заменить здесь 5 какой-нибудь цифрой, отличной от 0?

** Головоломка 4. Квадратный корень.

Извлечь целый квадратный корень с недостатком из очень длинного целого числа (намного более длинного, чем наибольшее целое, которое воспринимается вашим компьютером, например, содержащего 50 или 100 значащих цифр),

Числовые последовательности

Вот две известные в информатике головоломки. Сожалею, что обманываю ожидания своих коллег, которые не найдут здесь ничего нового…

?* Головоломка 5. Последовательность Хэмминга.

Рассмотрим числа, не имеющие других простых делителей, кроме 2, 3 и 5. Расположим их в возрастающем порядке. Это и есть последовательность Хэмминга. Вот ее начало:

2 3 4 5 6 8 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50…

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

?** Головоломка 6. Счастливые числа.

Унтер-офицер собирает своих людей, чтобы решить, кого отправить в наряд на картошку.

«Постройтесь гуськом и рассчитайтесь, начиная с 2». Первый из стоящих говорит 2, следующий — 3, следующий — 4 и т. д.

«Первый в ряду, выйди из строя. Ты освобожден от наряда. Какой у тебя номер?»

«Второй», — отвечает солдат.

«Начиная со второго, рассчитаться по два; тем, кому не выпадет 2, выйти из строя; они пойдут в наряд».

И процесс возобновляется. Первый из вышедших из строя имеет номер 3, и он счастлив: он освобожден от наряда. Теперь рассчитываются по трое, начиная с 3 — с того, кто первым вышел из строя за нарядом…

Составьте программу, выписывающую n первых счастливых чисел для большого n (100, даже 500), Внимание: в чем состоит головоломка: каждый член последовательности должен вычисляться, исходя из данных значений предыдущих счастливых чисел. У вас есть i первых, вычислите следующее. В таблице-то легко вычеркивать… Вот первые счастливые числа:

2 3 5 7 11 13 17 23 25 29

Счастливые числа — не обязательно простыв, а простые числа — не обязательно счастливые…

??? Головоломка 7. Дьявольская последовательность.

Марк Твен описал в своих рассказах жуткую историю. Человек прочел глупые стихи вроде

Кондуктор, отправляясь в путь, Не рви билеты как-нибудь, Стриги как можно осторожней. Чтоб видел пассажир дорожный: Синий стоит восемь центов, Желтый стоит девять центов, Красный стоит только три. Осторожней режь, смотри! Припев: Режьте, братцы, режьте! Режьте осторожно! Режьте, чтобы видел пассажир дорожный!

(Я цитирую по памяти, но дух соблюден.) Он был порабощен ритмом этих стихов, что стало настоящим наваждением. Если он начинал писать, его перо выводило «Режьте, братцы, режьте». Если он встречал кого-нибудь, он не здоровался с ним, а говорил «Режьте, братцы».

Он пробовал управлять собой, но это подрывало его здоровье. Он решил обратиться к своему священнику и объяснить ему, в чем дело, и читал ему это маленькое стихотворение, подчеркивая его ритм, пока пастор не выучил его наизусть. Ушел он исцеленный.

Но в воскресенье пастор начал проповедь словами «Режьте, братцы, режьте». Что бы ни было в гимне, который он запевал, слова были одни — «Режьте, братцы, режьте…» Его жизнь стала адом. Он не мог исцелиться, пока в один прекрасный день ему не удалось злодейски обучить этому стихотворению одного профессора университета…

Нижеследующее и есть «режьте, братцы, режьте». Оно преследует меня долгие годы. Я потерял массу времени на размышления о нем без сколько-нибудь значительного успеха. Но ничто меня не занимает в большей степени. Моя единственная надежда освободиться от него — это то, что вы им заинтересуетесь…

Последовательность определяется следующим образом: первый член этой последовательности есть произвольное нечетное число, отличное от единицы. Следующее за числом p равно

p/2, если p четно,

Зp + 1, если p нечетно.

Последовательность заканчивается, когда в ней встречается значение 1.

Вот последовательность, которую мы получим, исходя из 7:

7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Нет никакой надежды, что вам удастся доказать, что для любого нечетного числа в качестве начального значения последовательность достигает единицы.

Но в высшей степени увлекательно составить эту крошечную программу и посмотреть, как она работает. Испытайте число 27 в качестве начального значения: вы получите очень длинную последовательность, среди элементов которой есть 9232. Если вы изучите ряды чисел, получаемые для начальных значений, взятых среди нечетных целых от 3 до 99, вы получите довольно много патологических последовательностей, не всегда сильно отличающихся. Все это очень смущает. Ни один специалист по теории чисел еще не смог Доказать, что такая последовательность принимает значение 1 для любого начального значения. Не больше известно и о том, почему некоторые из этих последовательностей — короткие, а другие — слишком длинные…

Эта программа замечательно иллюстрирует то, что называется «проблемой остановки». Существуют простейшие программы, относительно которых нет уверенности, что они остановятся…

Теперь, когда вы уже познакомились с этой последовательностью, получите предмет головоломки. Заметим сначала, что если p нечетно, то мы переходим к Зp + 1 — числу, отличному от 1. Очевидно, что непосредственно предшествующий шаг есть деление на 2. Поэтому можно изменить правило построения последовательности описанным ниже образом: следующее за числом p равно

p/2, если p четно,

(Зp + 1)/2, если p нечетно,

Это вычеркивает некоторые члены предыдущей последовательности, не меняя проблемы остановки:

7 11 17 26 13 90 10 5 8 4 2 1

Вы можете пойти еще дальше в том же направлении, объединяя вместе все последовательные шаги, действующие по правилу (Зp + 1)/2, и все следующие за ними шаги, состоящие в делении на два. Вы получите два новых правила перехода, гораздо более уплотненные. Свяжите их и пустите в ход. Для числа 7 вы должны без задержки получить последовательность

7 13 5 1

Это позволяет рассматривать обобщения задачи. Пусть k — нечетное число. Возьмем в качестве правил перехода следующие:

p/2, если p четно,

k * p + k − 2, если p нечетно.

Возможно уплотнение, аналогичное предыдущему. Для k = 5 следующее за числом 3 есть 3, и существуют исходные точки, для которых программа не останавливается. Для k = 7 она идет точно так же. Так что проблема остановки связана со свойством числа k. Я бы здесь… Впрочем, мало ли чего я хочу!

Зашифрованные операции

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

Головоломка 8. SEND MORE MONEY.[4]

Это — лаконичная телеграмма английского студента своему отцу. История умалчивает о том, как отец это принял и были ли отправлены деньги…

SEND + MORE = MONEY

Программа очень легкая. Время вычисления короткое. Едва ли это головоломка. Как раз для тренировки…

Головоломка 9. HELP THE YOUNG.[5]

Конечно, конечно. Почему бы не послать им еще денег? Та же задача:

HELP + THE = YOUNG

Отметим разницу с предыдущей задачей. Предыдущая использовала не все цифры от 0 до 9. В этой участвуют все. Можете ли вы воспользоваться этим?

DEVOIR, LEÇON, ÉLÈVE.[6]

Есть аналогичные зашифрованные сложения по-французски. Например, такая:

ÉLÈVE + LEÇON = DEVOIR

? Головоломка 10. Зашифрованное умножение.

Довольно сложений, это становится скучным. Вот зашифрованное умножение:

ABCDE * 9 = FGHIJ

Здесь 10 букв представляют 10 различных цифр, так что одна из них равна 9. Можно сразу кое-что сказать о возможных значениях букв, но чтобы получить решение, придется идти буквально ощупью. Столько же придется искать и компьютеру.

?* Головоломка 11. Забавное число.

Число 123456789 обладает забавными свойствами:

123456789 * 2 = 246913578

Как и исходное, удвоенное число образовано всеми девятью цифрами, кроме 0.

123456789 * 4 = 493827156

Результат снова образован девятью цифрами, отличными от 0.

123456789 * 5 = 617283945

По-прежнему 9 цифр.

123456789 * 7 = 864197523

Опять 9 цифр, и это еще не все.

123456789 * 8 = 987654312

Но это не работает ни для 3, ни для 6. Это не может работать и для 9, потому что в результате больше 9 цифр,

Тем не менее есть много чисел, образованных всеми 9 цифрами (кроме 0), которые после умножения на 3 дают результат, образованный теми же девятью цифрами. Можете ли вы дать список всех таких чисел, оканчивающихся на 9? И также список тех, которые кончаются на 3?

Можно ли распространить использованный метод на случай умножения на 6?

Доказательства теорем

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

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

Внимание: вы должны бороться с проблемой сложности. Если вы не будете принимать никаких мер предосторожности, число подлежащих исследованию случаев может сказаться невероятно большим и работа компьютера станет невозможной: ведь перед вами не вечность… Равновесие между подготовительной работой (доказательством палых теорем) и работой компьютера оценивается в зависимости от ваших возможностей, одновременно в области математических доказательств и в ресурсах вашего микрокомпьютера. К сожалению, не говорите: эта программа отнимает уйму времени, я перепишу ее на ассемблере. Это — худшее из решений. Все, что я вам предлагаю, осуществимо на Бейсике за разумное время. Если ваша программа требует уйму времени, значит, она плохо придумана.

Головоломка 12. Теорема 153.