Жак Арсак - Программирование игр и головоломок

для молодых людей от 14 до ? (а до скольких?). Я знаю многих взрослых, любящих играть (и сам люблю). У меня много коллег, для которых программирование и есть игра — как для меня. Я написал эту книгу для всех молодых людей от 14 до 77 лет, которые любят играть с компьютером или которые любили бы это делать, если бы средство для этого им было предоставлено.

Серьезные журналы публикуют математические развлечения для «порядочных людей». Продаются книги с логическими головоломками. Продаются обзоры стратегий. Применение компьютеров полностью обновило весь этот круг вопросов. Всем тем, кто интересуется головоломками, я предлагаю здесь новую форму головоломок: задача, решение которой нужно найти на компьютере, — это настоящая головоломка. Они бывают трех основных типов:

некоторые головоломки интересно программировать (например, зашифрованные операции, господин S и господин P, пентамино…);

некоторые задачи имеют очень простой вид, но доведение решения до программы является настоящей головоломкой (например, переставить две части вектора, найти наибольший белый прямоугольник в решетке кроссворда). Это — совершенно новый тип задач, тесно связанный с компьютером;

наконец, последний тип — настолько трудный, что я уменьшил набор его примеров, выбрав их из поистине неисчислимого множества, — связан с тем, что я говорил в начале. Вам дана программа (в нашей книге — написанная настолько хорошо, насколько это возможно), но без комментариев. Скажите, что она делает.

Трудность головоломки обозначается вопросительными знаками. Есть головоломки с довольно простыми решениями, но деликатным программированием: «?***», и есть ужасные головоломки с легким программированием: «???». Выбирайте!

Эта книга будет полезна и всем тем, кто занимается подготовкой подростков по информатике: преподавателям лицеев и колледжей, руководителям клубов или каникулярных занятий.

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

Первый раздел — немного особенный. Каковы бы ни были ваши склонности — начните с него; он даст вам инструмент, необходимый для почти всех игр и немалого числа головоломок (формирование ситуаций случайным образом).

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

Я сказал все. Теперь — вам ИГРАТЬ, вам СОЗДАВАТЬ…

Обозначения

Вот конструкции, используемые в программах этой книги.

Оператор присваивания. В нем используется знак «:=»

i := i + 1

Вот его аналоги на других языках:

Бейсик: LET I = I + 1

LSE: I ← I + 1

Паскаль: I := I + 1

Условный оператор имеет вид

ЕСЛИ условие ТО последовательность операторов

КОНЕЦ_ЕСЛИ

При работе условного оператора вначале проверяется условие. Если оно имеет значение ИСТИНА, то выполняется последовательность операторов, заключенная между ТО и КОНЕЦ_ЕСЛИ. КОНЕЦ_ЕСЛИ играет роль закрывающей скобки, избавляющей от применения разделителей DEBUT FIN, как на LSE, или BEGIN END, как в языке Паскаль. При работе оператора

ЕСЛИ условие ТО последовательность операторов

  ИНАЧЕ последовательность операторов

КОНЕЦ_ЕСЛИ

вначале проверяется условие. Если оно имеет значение ИСТИНА, то выполняется последовательность операторов, заключенная между ТО и ИНАЧЕ, а если условие имеет значение ЛОЖЬ, то выполняется то, что содержится между ИНАЧЕ и КОНЕЦ_ЕСЛИ. Снова, как и выше, нет нужды в DEBUT FIN.

Цикл

ПОКА условие ВЫПОЛНЯТЬ

  последовательность операторов

ВЕРНУТЬСЯ

выполняет последовательность операторов, заключенную между скобками ВЫПОЛНЯТЬ — ВЕРНУТЬСЯ, пока условие справедливо. Он эквивалентен циклу LSE

FAIRE номер строки ПОКА условие

  последовательность операторов

n замыкающая строка

или циклу на языке Паскаль

WHILE условие DO

  BEGIN последовательность операторов END

Цикл

ВЫПОЛНЯТЬ

  последовательность операторов, содержащая слово КОНЧЕНО

ВЕРНУТЬСЯ

работает так:

Последовательность инструкций, заключенная между скобками операторов ВЫПОЛНЯТЬ — ВЕРНУТЬСЯ, --">