Жак Арсак - Программирование игр и головоломок
2. Пусть p дано; тогда p/n лежит между 0 и 1. И элемент, следующий за p, можно определить формулой
p := целая_часть (n * ale (p/n)),
Здесь элемент, следующий за p, полностью определен числом p, и эта последовательность неизбежно оказывается периодической. В наиболее удачных случаях она дает n различных значений (n целых от 0 до n − 1), после чего возвращается к уже встретившемуся в последовательности числу, и — так как каждое из чисел имеет однозначно определенное следующее за ним число — мы повторяем уже построенную часть последовательности. Но чаще всего этим способом получаются слишком короткопериодические последовательности.
?? Головоломка 1. Периодическая последовательность.
Построим последовательность целых чисел в промежутке (0, n − 1) только что описанным способом. Предположим, что n достаточно велико (например 10000). Написать программу, определяющую период этой последовательности. Ограничение: вы не имеете права запоминать в таблице последовательные значения элементов последовательности (вы не имеете права запоминать их и в любой другой форме). Именно поэтому n предполагается достаточно большим: не может быть и речи о сохранении всех полученных значений, чтобы смотреть, встречается ли каждое новое значение среди предыдущих. Нужен другой метод. Вам предлагается обнаружить один из них…
Головоломка для маленького вундеркинда.
В прессе — как американской, так и французской — часто появляются восторженные сообщения о детях, которые обучаются работе с компьютером за несколько часов и затем объясняют своим родителям, как это делается. Разрастаются клубы по информатике, где дети пишут программы, заставляющие бледнеть профессионалов. Подающие надежды Эйнштейны информатики… Я бы никогда и не предлагал следующую головоломку, если бы не был жестоко ущемлен одним из них. Понятно, что я не скажу, ни где, ни когда.
Я находился в зале для практических занятий с детьми 15–16 лет. Преподаватель предложил им составить программу, бросающую две случайные кости и сообщающую число появлений каждой комбинации (см. упражнение 4). Маленький местный вундеркинд закончил свою довольно простую (не так ли!) программу, и преподаватель предложил ему следующую задачу:
пусть последовательно n раз выбрасывается «орел» или «решка». Сосчитать число случаев появления комбинации «орел» — «орел» — «орел», и число случаев появления комбинации «орел» — «решка» — «орел».
Мальчик очень быстро написал программу, но она не пошла. Поэтому я уселся рядом с ним и предложил ему проверить, это именно не идет. Мы вывели программу на экран. Совершенно непонятно. Плохо вложенные циклы. Поскольку ошибки были, то пришлось делать исправления вплоть до убирания одного GOTO, чтобы заменить его другим GOTO. Я сделал ему замечание, что его программа непонятна, на что он ответил, что это не имеет значения, поскольку он ее понимает. Я возразил ему, что через три месяца он сам ее не поймет: никакой реакции, это его не интересовало… Так что взаимопонимания между нами достичь не удалось. Я вижу только два возможных объяснения этого явления, в конечном счете не исключающих друг друга: многие преподаватели лицеев располагают наблюдениями такого рода.
Можно представить себе, что успешный диалог между человеком и машиной разрушительно действует на диалог между людьми. Это было бы катастрофой. Но эту столь пессимистическую гипотезу ничто реально не подкрепляет,
Гораздо более правдоподобно, что этот мальчик (как и подобные ему) встречают естественные затруднения в общении с другими людьми. Он нашел в информатике страну, в которой можно избежать такого общения и где машина принимает все, что он скажет, какова бы ни была форма и структура, лишь бы только синтаксис был соблюден. Именно поэтому феномен «информатических клубов» оказывается опасным. В рамках преподавания информатики нужно, чтобы преподаватель требовал от своих учеников анализа поставленной задачи и словесного выражения на обыденном языке результата этого анализа. Программирование может начаться только после этого. На этом уровне преподаватель заботится о качестве стиля программ, написанных по ясному плану… (Я надеюсь, что и вы работаете именно так, иначе вас нужно остерегаться.) В обстановке, когда подростков недостаточно контролируют и они находятся как бы на самообучении, они могут оказаться свободно предоставленными своим естественным склонностям. Если организованное преподавание помогало бы им учиться выражать и структурировать свои мысли, то всетерпимость к средствам выражения, свойственная машине, позволяет им оставаться в их собственном мирке, и случайные — но настоящие — успехи ошибочно убеждают их, что искать других путей не нужно. Это ли нужно подросткам, испытывающим трудности при общении?
Вернемся к нашим баранам. Если кто-то из молодых людей и обломает на этой задаче свои зубы, то это, может быть, и правда головоломка. Пора перейти к формулировке задачи.
* Головоломка 2. Последовательности «орлов» и «решек».
Осуществим n выбрасываний «орла» и «решки» с большим n (например 10000). Сколько раз встретится в ней данная комбинация из m следующих друг за другом выбрасываний (например, 10 раз «орел» или чередование из 10 выбрасываний «орла» и «решки», начиная с «орла»).
Есть много способов решить это упражнение. Они не все равноценны по времени вычисления. Я взял большое n и относительно большое m, чтобы прояснить явление. Ваша программа не должна работать долгие часы…
Другие азартные игры
* Игра 3. Покер — М — С.
Я не уверен, что это следует писать. Я знаю эту игру только по услышанной мною радиопередаче какой то периферийной радиостанции (угадайте какой?). Тасуем карточную колоду. Разыгрывается некоторая сумма. Верен верхнюю карту из пачки и требуем от игрока, чтобы он угадал, является ли следующая карта младшей или старшей по отношению к только что взятой. Учитывается только число очков, а не масть карты. Валет всегда больше девяти, король больше валета, туз больше всех. Если игрок угадал правильно, сумма в игре возрастает (я не знаю точно, добавляется ли при этом некоторое фиксированное количество или сумма удваивается, но это не так уж важно. В любом случае ваш компьютер не имеет связи с распределителем банковских билетов. Жаль, быть может…). Если он не угадывает, он теряет все, В конце некоторого фиксированного числа бросаний (кажется 6; я слушал недостаточно внимательно, я прошу прощения у упомянутой станции) игрок, если он всегда оказывался прав, присваивает сумму игры.
Составьте программу, которая позволит вам быть игроком, а компьютер пусть будет всем остальным (за исключением того, что вы называете и сумму игры). На мой взгляд, хотя я могу и ошибаться, единственная трудная задача — перетасовать карты…
?** Игра 4. Лабиринт для шахматного коня.
Лабиринты являются очень высоко ценимыми головоломками. Почему не использовать компьютер и генератор случайных чисел для построения случайных лабиринтов, которые вы затем будете пытаться пройти? Но мой микрокомпьютер не имеет графических возможностей. К тому же если у вашего такие возможности есть, то я не уверен, что желание нарисовать обычный лабиринт приводит к хорошему упражнению по программированию. Внимание часто в большей мере поглощается графическими задачами, чем более фундаментальной задачей порождения лабиринта. Тем не менее, если вам так подсказывает сердце, не стесняйтесь: , стройте от случая к случаю такой лабиринт, чтобы у него был хотя бы один путь от начала к концу, и играйте с ним.
Чтобы освободиться от графических задач, рассмотрим другую форму лабиринта. Его создание составляет головоломку, а использование — игру. Пусть дана прямоугольная область, образованная n строками с p полями на каждой из них. На моем компьютере, где приходится учитывать формат экрана, числа n = 12 и p = 20 дают хорошие результаты. Занятые места считаются препятствиями (обозначенными здесь 0), пусть как-то помечены свободные места (здесь — точкой), пусть значок * обозначает всадника. Конь перемещается, как конь в шахматах: два шага в одном направлении и еще один шаг перпендикулярно предыдущему направлению. Конь может перемещаться только с одного свободного места на другое, В начальный момент он находится в правом нижнем углу. Он должен попасть в верхний левый угол (который, таким образом, тоже должен быть свободным). Число ходов игры ограничено. На рис. 1 изображен типичный пример лабиринта.
Составьте программу для компьютера для создания этого лабиринта и попытки его пройти. Так как должен существовать какой-то путь, проходящий из правого нижнего угла в правый верхний угол, то я предлагаю вам действовать следующим образом:
