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

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), Внимание: в чем состоит головоломка: каждый член последовательности должен вычисляться, исходя из данных значений предыдущих счастливых чисел. У вас есть