Игры с Чипом
Шрифт:
— Что-то не слишком быстро ты нашел ответ, — ехидно заметил Сережа, — я и то меньше думал.
— Долго было объяснять каждое действие, — сердито возразил Чип, — а потом любой алгоритм полезен только в достаточно сложных случаях. Вот посмотрим, как ты найдешь Н.О.Д. 256 и 288 без алгоритма Евклида, и потом сравним, насколько быстрее ты найдешь его с помощью алгоритма.
ОТ РЕДАКЦИИ:
Ребята, а вы не хотите помочь Сереже и тоже выполнить задание Чипа?
и найдите Н.О.Д. 256 и 288. Ответы пришлите нам.
В № 10 за прошлый год Чип попросил вас составить программу «Приключений в джунглях». Ни одной правильной программы мы не получили. А из всех программ, что вы прислали для рекурсивной пословицы «Иван и Петр», правильная только программа Алисы Левандовской, ученицы 4 «А» класса школы № 45 г. Москвы.
«Я составила рекурсивную программу по образцу рекурсивной арабской сказки. Иван попал в рекурсивную ситуацию.
Есть более короткий вариант этой программы:
А можно было и так.
А чтобы эта программа не зациклилась, то есть не повторяла одно и то же без конца, можно вставить после первой строчки «Иван кивает на Петра» новую команду:
Команда «СТОП», вставленная в любом месте, останавливает всю работу. Хорошо бы и в жизни так можно было прервать любое бесполезное занятие.
Двадцать спичек и монета
Сережа с Чипом играли
Сережу этой игре научил Чип и потому все время давал ему первый ход как новичку. И тем не менее каждый раз Сережа проигрывал, хотя он обычно хорошо играл в такие игры. Кое-какие секреты игры он понял: например, что невыгодно брать много спичек первым ходом, а если возьмешь больше 6, то противник берет монетку ответным ходом. Сережа брал по одной спичке, и в ответ Чип брал по одной, иногда по 2. Но выигрывал почему-то все время Чип!
— А знаешь, что делает в таком случае программист? — сказал Чип после 15-го выигрыша подряд. — Если он не может понять, как работает программа с большими числами, он проверяет ее на маленьких.
— Знаю, ты мне это уже говорил, — сердито буркнул Сережа. — Только при чем тут программа? Это же игра, а не алгоритм.
— Это алгоритмическая игра: существует алгоритм выигрыша независимо от хода противника. Но самое удивительное, что выигрывает не тот, кто первым начинает! Так что ты ни в чем не виноват: я заманил тебя в ловушку.
— Как это, начинающий обязательно проигрывает? Так не может быть, у него же лишний ход.
— Ты был бы прав, если бы этим лишним ходом он мог не взять ни одной спички. Тогда он поставил бы противника в свое положение. Но по правилам он обязан в каждый ход сколько-то спичек взять, и как только он это сделает, он уходит от спасительного числа Фибоначчи — 21. А до следующего числа Фибоначчи — тринадцати — ему не дотянуть, тогда противник возьмет монетку ответным ходом.
— Что это еще за числа Фибоначчи?
— О-о, это замечательные числа: 1, 1, 2, 3, 5, 8, 13, 21, 34... Они тянутся до бесконечности, причем каждое следующее получается сложением двух предыдущих. Они так хорошо служат программистам — хотя средневековый итальянский математик Фибоначчи вряд ли мог на это рассчитывать, — что один неизвестный компьютерный поэт прославил числа Фибоначчи в стихах.
— Интересно было бы послушать, — вежливо сказал Сережа, хорошо зная, что Чипа хлебом не корми, а дай почитать свои стихи, которые он обычно приписывал неизвестным авторам.
— Ты знаешь печальную историю о Карле и Кларе?
— Это что, «Карл у Клары украл кораллы, а Клара у Карла украла кларнет»?
— Да, это про них. Грустно, когда друзья ссорятся. Так вот, они решили помириться, и первый шаг сделала Клара.
Однажды Клара подарила Ему коробку из-под мыла; Подумав, Карл послал в ответ Пустой кулек из-под конфет. Тогда смягчившаяся Клара Послала 2 воздушных шара, А Карл послал ей, подобрев, 3 новых карты масти треф. И с благодарностью от Клары Пришли 5 варежек без пары; Как символ дружбы, Карл в ответ Шлет 8 разных сандалет. Растрогавшись, послала Клара 13 труб для самовара, И, прослезившись, Карл послал 21 коленный вал...