— Ну, как я и думал, ничего непонятно, сплошные загадки, — уныло сказал Сережа.
— На то и загадки, чтобы их отгадывать. Ну, подумай сам, тут говорится про какое-то большое, меньшее и про Н.О.Д. Ты, конечно, догадался, Н.О.Д. — это и есть наибольший общий делитель двух чисел, который мы ищем.
— Ну, наверное, большое — это большее из этих двух чисел, а меньшее это меньшее. — Сережа несколько оживился. — Но потом непонятно: эти три числа меняются местами, делятся друг на друга, я не могу разобраться, что происходит?
— А знаешь, что должен делать программист, столкнувшись с алгоритмом, в котором он не может разобраться?
— Знаю, отложить его в сторону и пойти поиграть в футбол!
— Я сказал «программист, а не футболист»! Для программиста нет большего удовольствия, чем заставить программу работать. Программист отлаживает программу, то есть проверяет, как она работает, на известных ему примерах. Ну, скажем, ты знаешь, чему равен Н.О.Д. 12 и 30?
— Шести, — ответил Сережа, немного подумав, — 12 — это 2 х 6, а 30 — это 5 x 6.
— Итак, начинаем применять алгоритм Евклида. Малое — это 12, оно больше нуля, значит, повторяем: Н.О.Д. - 12, затем делим 30 на 12, получаем 2 и в остатке 6, значит, объявляем малым 6. Большим объявляем Н.О.Д., то есть 12, и возвращаемся к началу. Малое — это 6, оно больше 0, значит, повторяем снова: Н.О.Д. = 6, делим большое, то есть 12, на малое, то есть на 6, получаем ровно 2. Объявляем малым остаток, то есть малое теперь равно нулю. А большим объявляем Н.О.Д., то есть 6, и возвращаемся к началу. Но теперь малое равно нулю, а значит, повторять ничего не надо, мы уже нашли Н.О.Д. — это 6.
— Что-то не слишком быстро ты нашел ответ, — ехидно заметил Сережа, — я и то меньше думал.
— Долго было объяснять каждое действие, — сердито возразил Чип, — а потом любой алгоритм полезен только в достаточно сложных случаях. Вот посмотрим, как ты найдешь Н.О.Д. 256 и 288 без алгоритма Евклида, и потом сравним, насколько быстрее ты найдешь его с помощью алгоритма.
Однажды Клара подарила
Ему коробку из-под мыла;
Подумав, Карл послал в ответ
Пустой кулек из-под конфет.
Тогда смягчившаяся Клара
Послала 2 воздушных шара,
А Карл послал ей, подобрев,
3 новых карты масти треф.
И с благодарностью от Клары
Пришли 5 варежек без пары;
Как символ дружбы, Карл в ответ
Шлет 8 разных сандалет.
Растрогавшись, послала Клара
13 труб для самовара,
И, прослезившись, Карл послал
21 коленный вал...
Говорят, они стали добрыми друзьями и все время шлют друг другу подарки. И каждый из них, не желая уступить другому в щедрости, прибавляет к своему последнему числу подарков последнее число подарков, полученных от друга. Так и получаются числа Фибоначчи.
— Замечательное стихотворение, Чип, но я все-таки не понимаю, как ты меня обыгрывал с помощью этих чисел Фибоначчи.
— Предположим для начала, что у нас 2 спички и монетка. Тогда начинающий проигрывает, согласен? Он не может сразу взять монетку, и ему приходится брать 1 спичку, после чего противник одним ходом берет оставшуюся спичку вместе с монеткой. Вот мы и нашли первое спасительное число 3. Если ты оставил противнику это число, он проиграл.
— Ага, а если было 4 предмета — 3 спички и монетка, то можно убрать 1 спичку, и противник проиграет, — подхватил Сережа, — ведь он не сможет взять больше двух спичек.
— Правильно, значит, 4 не спасительное число, если я дам его противнику, он может выиграть. Идем дальше: если начинать с 5, то первым ходом можно взять только одну спичку, иначе противник сможет ответным ходом дотянуться до монетки. Но если ты возьмешь 1 спичку, то ты тоже проиграешь, потому что противник может, взяв 1, оставить тебе проигрышную позицию, которую мы только что разобрали.
— Значит, 5 — спасительное число. Действительно, получаются числа Фибоначчи, но пока я не уловил общего правила — как надо играть, чтобы всегда выигрывать, даже если ты дал противнику спасительное число Фибоначчи. Например, противник начинает с 8. Мне нужно сделать так, чтобы ему досталось число 5, верно?
— Да, но смотри, ты уже решал эту задачу раньше. От 8 до 5 как раз 3 шага. А для трех предметов ты уже все знаешь: если он берет 1, ты — 2, а если он — 2, ты — 1. Ведь числа Фибоначчи устроены так, что интервалы между соседними числами тоже являются числами Фибоначчи. Ты пытаешься посадить противника на ближайшее число Фибоначчи, а если не можешь, то прибавляешь к этому числу позапрошлое число Фибоначчи. Скажем, от 21 ты должен сажать противника на 13, но этого ты сделать не можешь, значит, прибавляешь к 13 позапрошлое число, то есть 5 (13 + 5 = 18), и стремишься дать противнику число 18. Это просто, так как от 18 до 21 как раз 3 шага — снова число Фибоначчи. Заставил его взять 18 — и тебе осталось 5 шагов до 13, а как проходить 5 шагов, ты тоже знаешь. Вот и все!
— Чип, и все равно это трудно, нужно все время считать и не ошибаться.
— Это трудно вам, людям, а нам нетрудно безошибочно считать. Зато в тех играх, где вариантов слишком много для расчета, например, в шахматах, люди пока обыгрывают компьютеры. Но мы быстро совершенствуемся, так что я не удивлюсь, если чемпионом мира по шахматам 2000 года будет компьютер.
— А чего же вам не хватает сейчас, если вы лучше нас считаете?
— Быстрее — еще не значит лучше. Нам не хватает вашей интуиции, умения без вычислений предвидеть последствия ходов. Интуиция основана на знаниях и опыте, а компьютеры пока не умеют копить знания и набирать опыт. Это будут уметь компьютеры следующего, пятого поколения, которые появятся в начале 90-х годов.
— Чип, а какое задание мы дадим ребятам на этот раз?
— Так как мы сегодня говорили об играх, пусть попробуют придумать сюжет электронной игры, в которую им было бы интересно играть. Не программу, а просто сюжет вроде мультфильма. Автора лучшей игры ждет сюрприз.
Пятьсот двенадцать рыцарей собрались на турнир,
Чтоб самого достойного узнал волшебный мир.
Они сразились по двое, и до исхода дня
Из каждой пары рыцарей один упал с коня.
И если будут рыцари все так же продолжать,
То сколько дней осталось им друг с другом воевать?
— Знаешь, дорогой, это определенно должно нам помочь, ведь тут тоже 512 рыцарей, как и у нас. Вот только непонятно, как они сражались и сколько времени занял турнир. Может быть, спросим у наших рыцарей? И того, кто отгадает, объявим победителем турнира.
— Ах, что ты, во-первых, им ни за что не отгадать, а во-вторых, они специально сюда приехали, чтобы подраться, и без боя не уедут. Послушай, а что, если спросить Алису?
— Эту скверную девчонку с дурными манерами? — вмешалась возмущенная герцогиня. — Она и крокетного фламинго толком держать не умеет!
— Да, вы правы, милая герцогиня, но нельзя при этом отрицать, что пару раз она нам помогла. Позвать сюда Алису!
— Только и всего? — рассмеялась Алиса, услышав стишок. — Но тут же ясно сказано, как надо сражаться: по двое, все одновременно, а проигравший выбывает. И займет это... дайте подумать...»
— А пока Алиса думает, — продолжал Чип, — мне хотелось бы показать тебе одно письмо. Нас ругает сердитый семиклассник из города Свалява Закарпатской области, который не указал своего имени и обратного адреса, наверное, чего-то испугался. Он пишет: «Ваши темы не заинтересуют даже ученика третьего класса. Нужно сначала выучить язык, какую-нибудь паршивенькую «Рапиру» хотя бы знать досконально, а потом уж разглагольствовать. Моя десятилетняя сестра знает БЕЙСИК, изучает ФОРТРАН 77. Она написала программы для решения уравнений — квадратных, линейных и так далее. Ей смешно читать про «Теремок», про «Красную шапочку», я не говорю уже о себе».