— А если мы все попадем в трясину? — спросил один из братьев.
— Для того я и сказал, чтобы вы дальше трех шагов не отходили. Видишь, дно опускается — сразу назад. Ну а если уж окажется, что во все стороны дно опускается, значит, мы выбрались на бугор, тогда там и останемся до утра...
— Ну и как, — нетерпеливо спросил Сережа, — выбрались они из трясины?
— А тут нечего и гадать, — ответил Чип с гордостью, — если у тебя правильный алгоритм, то рано или поздно ты достигнешь цели.
ОТ РЕДАКЦИИ:
Ребята, а вам такое задание — запишите план мальчика с пальчик, как выбраться из трясины, в виде программы. На конверте укажите: «Поможем мальчику с пальчик».
Чем кончились мучения Евклида
Наступил август, и родители теперь все чаще говорили Сереже, что пора бы ему повторить программу по математике.
Наконец-то в воскресенье Сережа сел за сложение дробей.
5 7
— + — =
16 12
вывел он в тетрадке и задумался.
Сначала нужно было найти наибольший общий делитель обоих знаменателей, потом разделить произведение знаменателей на этот наибольший общий делитель и найти тем самым наименьшее общее кратное, а потом... Впрочем, потом уже было не так трудно, самое трудное было, конечно, найти наибольший общий делитель.
— Точно так же мучился великий Евклид две тысячи лет тому назад, — сказал насмешливо Чип, когда Сережа пожаловался ему на неподатливость наибольшего общего делителя, — и ты знаешь, чем кончились эти мучения? Он нашел свой знаменитый алгоритм, который навсегда избавил от мучений пытливых искателей наибольшего общего делителя.
— Да я небось не пойму этот алгоритм, мы ведь только с 9-го класса начнем изучать информатику.
— А для таких, как ты, робких искателей Н.О.Д. неизвестный поэт воспел алгоритм Евклида в стихах:
— Ну, как я и думал, ничего непонятно, сплошные загадки, — уныло сказал Сережа.
— На то и загадки, чтобы их отгадывать. Ну, подумай сам, тут говорится про какое-то большое, меньшее и про Н.О.Д. Ты, конечно, догадался, Н.О.Д. — это и есть наибольший общий делитель двух чисел, который мы ищем.
— Ну, наверное, большое — это большее из этих двух чисел, а меньшее это меньшее. — Сережа несколько оживился. — Но потом непонятно: эти три числа меняются местами, делятся друг на друга, я не могу разобраться, что происходит?
— А знаешь, что должен делать программист, столкнувшись с алгоритмом, в котором он не может разобраться?
— Знаю, отложить его в сторону и пойти поиграть в футбол!
— Я сказал «программист, а не футболист»! Для программиста нет большего удовольствия, чем заставить программу работать. Программист отлаживает программу, то есть проверяет, как она работает, на известных ему примерах. Ну, скажем, ты знаешь, чему равен Н.О.Д. 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 без алгоритма Евклида, и потом сравним, насколько быстрее ты найдешь его с помощью алгоритма.
ОТ РЕДАКЦИИ:
Ребята, а вы не хотите помочь Сереже и тоже выполнить задание Чипа? Решите с помощью алгоритма Евклида пример:
5 7
— + — = ?
16 12
и найдите Н.О.Д. 256 и 288. Ответы пришлите нам.
В № 10 за прошлый год Чип попросил вас составить программу «Приключений в джунглях». Ни одной правильной программы мы не получили. А из всех программ, что вы прислали для рекурсивной пословицы «Иван и Петр», правильная только программа Алисы Левандовской, ученицы 4 «А» класса школы № 45 г. Москвы.
«Я составила рекурсивную программу по образцу рекурсивной арабской сказки. Иван попал в рекурсивную ситуацию.
Рекурсивная ситуация.
Если в нее попал Иван, то Игорь — это Петр, Саша — это Иван.
Если в нее попал Петр, то Игорь — это Иван, Саша — это Петр.
Саша кивает на Игоря. Игорь попадает в рекурсивную ситуацию.
Возврат.
Есть более короткий вариант этой программы:
Рекурсивная ситуация.
Иван кивает на Петра. Петр кивает на Ивана.
Иван попадает в рекурсивную ситуацию.
Возврат».
А можно было и так.
Рекурсивная подпрограмма КИВАЕТ (Иван Петру).
Иван кивает на Петра;
в ответ КИВАЕТ (Петр Ивану).
ВОЗВРАТ.
А чтобы эта программа не зациклилась, то есть не повторяла одно и то же без конца, можно вставить после первой строчки «Иван кивает на Петра» новую команду:
СТОП! Их обоих гнать пора!
Команда «СТОП», вставленная в любом месте, останавливает всю работу. Хорошо бы и в жизни так можно было прервать любое бесполезное занятие.
Двадцать спичек и монета
Сережа с Чипом играли в увлекательную игру «Двадцать спичек и монета». Кладутся подряд 20 спичек и 21-й — монетка. Дальше играющие по очереди берут спички, рассчитывая так, чтобы последним ходом забрать монетку. Надо только соблюдать два правила: во-первых, монетку нельзя брать первым ходом, а, во-вторых, если противник взял сколько-то спичек, то следующим ходом ты не можешь взять больше, чем это удвоенное число. Например, если он взял 5 спичек, то ты не можешь взять больше 10.