— Ну, как я и думал, ничего непонятно, сплошные загадки, — уныло сказал Сережа.
— На то и загадки, чтобы их отгадывать. Ну, подумай сам, тут говорится про какое-то большое, меньшее и про Н.О.Д. Ты, конечно, догадался, Н.О.Д. — это и есть наибольший общий делитель двух чисел, который мы ищем.
— Ну, наверное, большое — это большее из этих двух чисел, а меньшее это меньшее. — Сережа несколько оживился. — Но потом непонятно: эти три числа меняются местами, делятся друг на друга, я не могу разобраться, что происходит?
— А знаешь, что должен делать программист, столкнувшись с алгоритмом, в котором он не может разобраться?
— Знаю, отложить его в сторону и пойти поиграть в футбол!
— Я сказал «программист, а не футболист»! Для программиста нет большего удовольствия, чем заставить программу работать. Программист отлаживает программу, то есть проверяет, как она работает, на известных ему примерах. Ну, скажем, ты знаешь, чему равен Н.О.Д. 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 коленный вал...