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

Поговорка жителей плоскогорья Высоких Вивар

Некоторое время назад один из постоянных читателей "Информатики" написал нам: "Сама по себе идея рубрики "Книжный шкаф", безусловно, хороша. Но хочется пожелать, чтобы вы не путали книжный шкаф учителя информатики и книжную полку магазина, пусть даже очень хорошего, пусть даже на этой полке стоят книги, посвященные компьютерной тематике. Ведь в книжных шкафах тех, кто не первый год преподает информатику, порой имеются уникальные книги, которые уже давно не встречаются в магазинах (но, к счастью, их вполне можно найти в библиотеках). А наши молодые коллеги о них иногда даже и не слышали".

И мы открыли свой "Книжный шкаф". Надо сказать, что, сколько бы мы ни старались поддерживать в нем относительный порядок, получается он очень уж относительным. Поэтому книги из шкафа мы станем извлекать не в каком-то определенном порядке, а как получится — какая первой упадет на нас при открывании дверцы, о той и расскажем. В этот раз первой упала книга Жака Арсака "Программирование игр и головоломок", которая вышла в 1990 году в издательстве "Наука" (во Франции книга увидела свет в далеком уже 1985 году).

Книга состоит из трех частей. В первой приведены условия задач. Вторая, озаглавленная "Первая помощь", содержит указания к решениям. В этой части обсуждаются алгоритмы решения задач и возможные пути их реализации. И, наконец, в третьей части, она называется "И если вы все еще не нашли решения", приведены наброски программной реализации алгоритмов на языке, похожем на Паскаль (неформальное описание конструкций этого языка приводится в начале книги). Данная книга, на наш взгляд, полезна прежде всего тем, что в ней имеется описание множества простых задач — игр и головоломок, которые по силам практически каждому ребенку. При этом учитель может найти как задачи, которые можно использовать при работе с учениками начальной школы, так и более серьезные (но опять же достаточно простые в реализации) игры и головоломки, которые заинтересуют и старшеклассников. Приведем краткое содержание первой части (поскольку именно оно и дает общее представление о книге).

Часть I. Условия задач.

1. Случайные числа.

Генерация случайного числа. Непредсказуемые числовые последовательности. Азартные игры.

Воспроизводимая непредсказуемая последовательность. Другие азартные игры.

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

Арифметические развлечения. Числовые последовательности. Зашифрованные операции. Доказательство теорем. Простые числа. Таинственные программы.

3. Игры без стратегии.

4. Игры со стратегией.

5. Стратегия без игры (выигрывающие стратегии). Ханойские башни. Печальный конец Паскаля младшего.

6. Комбинаторные задачи.

7. Обо всем понемногу.

Необходимо отметить, что в книге можно найти достаточно подробный разбор задач, уже ставших классическими. Это и "Игра Ним", и "Ханойские башни", и некоторые теоремы, в доказательстве которых может помочь компьютер (некоторые из этих задач и теорем рассматривались и на страницах "Информатики"). Чтобы вы получили некоторое представление о задачах, содержащихся в книге, приведем некоторые из них. (Надо сказать, что мы выбирали не самые тривиальные и простые — в книге вы сможете найти задачки и попроще.)

Построим последовательность натуральных чисел следующим образом. Начальный элемент — четырехзначное натуральное число, причем не все его цифры равны между собой Пусть а, b, с, d — цифры числа. Сначала упорядочим их по невозрастанию (слева направо). Это будет первое число Расположив цифры в обратном порядке, получим второе число. И, наконец, вычтем второе число из первого То, что получится, и есть следующий элемент последовательности. Оказывается, что для любого числа указанного вида данная последовательность сходится к числу 6174

Разложим на столе 24 раскрытые карты: все карты с номерами от 1 до 6 обычной колоды, где туз считается за 1. Масти карт несущественны, тройка бубен не отличается от тройки треф Важен только вес карты. Каждый игрок при своем ходе берет со стола карту, и ее значение складывается с суммой значений взятых ранее карт (таким образом, подсчитывается общая сумма карт, взятых игроками). Первый, кто наберет в точности 50 очков, выигрывает. Вынужденный взять карту и превысить 50 очков проигрывает.

Несмотря на то, что книга "Программирование игр и головоломок" вышла десять лет назад (точнее, видимо, благодаря этому), ее вследствие большого тиража — более 300 000 экз. — несложно найти в библиотеках. А может быть, и в книжных шкафах ваших коллег?