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

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

Головоломка для маленького вундеркинда.

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

Я находился в зале для практических занятий с детьми 15–16 лет. Преподаватель предложил им составить программу, бросающую две случайные кости и сообщающую число появлений каждой комбинации (см. упражнение 4). Маленький местный вундеркинд закончил свою довольно простую (не так ли!) программу, и преподаватель предложил ему следующую задачу:

пусть последовательно n раз выбрасывается «орел» или «решка». Сосчитать число случаев появления комбинации «орел» — «орел» — «орел», и число случаев появления комбинации «орел» — «решка» — «орел».

Мальчик очень быстро написал программу, но она не пошла. Поэтому я уселся рядом с ним и предложил ему проверить, это именно не идет. Мы вывели программу на экран. Совершенно непонятно. Плохо вложенные циклы. Поскольку ошибки были, то пришлось делать исправления вплоть до убирания одного GOTO, чтобы заменить его другим GOTO. Я сделал ему замечание, что его программа непонятна, на что он ответил, что это не имеет значения, поскольку он ее понимает. Я возразил ему, что через три месяца он сам ее не поймет: никакой реакции, это его не интересовало… Так что взаимопонимания между нами достичь не удалось. Я вижу только два возможных объяснения этого явления, в конечном счете не исключающих друг друга: многие преподаватели лицеев располагают наблюдениями такого рода.

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

Гораздо более правдоподобно, что этот мальчик (как и подобные ему) встречают естественные затруднения в общении с другими людьми. Он нашел в информатике страну, в которой можно избежать такого общения и где машина принимает все, что он скажет, какова бы ни была форма и структура, лишь бы только синтаксис был соблюден. Именно поэтому феномен «информатических клубов» оказывается опасным. В рамках преподавания информатики нужно, чтобы преподаватель требовал от своих учеников анализа поставленной задачи и словесного выражения на обыденном языке результата этого анализа. Программирование может начаться только после этого. На этом уровне преподаватель заботится о качестве стиля программ, написанных по ясному плану… (Я надеюсь, что и вы работаете именно так, иначе вас нужно остерегаться.) В обстановке, когда подростков недостаточно контролируют и они находятся как бы на самообучении, они могут оказаться свободно предоставленными своим естественным склонностям. Если организованное преподавание помогало бы им учиться выражать и структурировать свои мысли, то всетерпимость к средствам выражения, свойственная машине, позволяет им оставаться в их собственном мирке, и случайные — но настоящие — успехи ошибочно убеждают их, что искать других путей не нужно. Это ли нужно подросткам, испытывающим трудности при общении?

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

* Головоломка 2. Последовательности «орлов» и «решек».

Осуществим n выбрасываний «орла» и «решки» с большим n (например 10000). Сколько раз встретится в ней данная комбинация из m следующих друг за другом выбрасываний (например, 10 раз «орел» или чередование из 10 выбрасываний «орла» и «решки», начиная с «орла»).

Есть много способов решить это упражнение. Они не все равноценны по времени --">