Игры с Чипом

— Недолет!

— 24-е?

— Перелет!

— 20-е?

— Недолет!

— 22-е?

— Попал! Это тебе повезло, Чип, а то бы ты дольше гадал.

— Наоборот, мне не повезло. Моим методом, вернее, по моему алгоритму, любой месяц угадывается после трех вопросов, а любой день после четырех, но иногда получается быстрее. Например, если бы ты родился 24 ноября, то число и месяц рождения я угадал бы после пяти вопросов, а не после семи, как сейчас, а если бы ты родился 16 июня — то после двух.

— А если бы я родился на день позже, 23 декабря?

— Тогда бы ты ответил: «Недолет», — на последний вопрос, и я уже точно знал бы, что это 23-го, поскольку 24-го был перелет.

— Это что, все предыдущие ответы помнить? Это надо быть компьютером!

— Нет, все помнить не надо, достаточно держать в голове два последних числа. Алгоритм устроен так, что правильное число всегда находится между этими двумя, а интервал каждый раз уменьшается в два раза. Например, когда я угадывал месяц, я сначала попробовал июнь — он ровно посередине года, и по твоему ответу я узнал, что твой месяц находится во второй половине. Тогда я снова нашел середину — это сентябрь и по твоему ответу узнал, что твой месяц находится в третьем квартале. Ну, а дальше, проверив ноябрь, я всегда узнал бы месяц по твоему ответу: перелет, недолет или попал.

— Знаешь, месяц меня не так удивляет, ведь их всего 12, а вот что ты один день из 31 узнал за 4 вопроса, это здорово. Значит, ты сначала проверил середину — это 16, а потом остались три вопроса, и ты угадал один из 16 дней. А, пожалуй, не так уж и странно: 16 делим пополам, это 8, еще раз пополам, это 4, а дальше остаются 3 числа, которые угадываются за 1 вопрос. Получается, что с месяцами твой алгоритм работал не в полную силу: если бы их было 16, тебе тоже хватило бы трех вопросов.

— Да, а с днями хватило бы четырех вопросов, если бы в каждом месяце было по 32 дня. Ты, конечно, узнаёшь эти числа — это степени числа 2. Их помнит каждый программист. Если бы компьютер создавал Землю, он бы сделал так, чтобы в году было 16 месяцев, в месяце — 4 недели по 8 дней, в дне — 16 часов, в часе — 64 минуты, а в минуте — 64 секунды. Насколько легче было бы считать нам, компьютерам, ведь мы основаны на двоичной системе.

— А ты напиши в газету: мол, мы, компьютеры, выполняем за людей всю вычислительную работу, а между тем нас до сих пор заставляют пользоваться вашим дурацким календарем и вашими дурацкими часами. Скажи, мол, переведите все на двоичную систему, и мы вам будем быстрее считать.

— Смеешься? Посмотрим, кто будет смеяться лет через 100, может быть, тогда у компьютеров будут и свои газеты, и свои профсоюзы, чтобы заботиться об условиях их труда. Мы не ленимся, но нам обидно, когда нас заставляют впустую работать.

— Чип, милый, ты что, на меня обиделся? Ну извини, я нечаянно. Расскажи мне что-нибудь еще, ты ведь так интересно рассказываешь. — Сережа знал, что его друг больше всего любит, когда его хвалят.

И действительно, Чип дулся недолго, через несколько минут, порозовевший от Сережиных похвал, он уже весело рассказывал очередную историю.

Это была история о том, как маленький электронный мальчик с пальчик Чип, спасший братьев от великана Гигабайта, вел их домой по страшному Лесу Неправильных Программ. Была темная ночь, туман, и братья сбились с дороги. Сами и не заметили, как оказались в Болоте Ошибок — ноги так и вязнут в трясине, и куда ни ткнись, погружаешься все глубже и глубже.

— Стойте! — закричал братьям маленький Чип. — Мы так все утонем! У меня есть алгоритм, как выбраться из трясины. Я стою на месте, а вы все делаете по три шага, каждый в свою сторону, куда ему кажется лучше. Потом перекликаемся, сравниваем, кто выше всех выбрался, и идем к нему. А чтобы знать, кто выше всех, и заодно чтобы не потеряться, возьмите каждый по веревке, а концы всех веревок будем привязывать к этому колышку. Я останусь возле колышка и по тому, куда идут веревки, буду видеть, кто выше вылез, а кто в трясину попал.

— А если мы все попадем в трясину? — спросил один из братьев.

— Для того я и сказал, чтобы вы дальше трех шагов не отходили. Видишь, дно опускается — сразу назад. Ну а если уж окажется, что во все стороны дно опускается, значит, мы выбрались на бугор, тогда там и останемся до утра...

— Ну и как, — нетерпеливо спросил Сережа, — выбрались они из трясины?

— А тут нечего и гадать, — ответил Чип с гордостью, — если у тебя правильный алгоритм, то рано или поздно ты достигнешь цели.

ОТ РЕДАКЦИИ:

Ребята, а вам такое задание — запишите план мальчика с пальчик, как выбраться из трясины, в виде программы. На конверте укажите: «Поможем мальчику с пальчик».

Наступил август, и родители теперь все чаще говорили Сереже, что пора бы ему повторить программу по математике.

Наконец-то в воскресенье Сережа сел за сложение дробей.

5 7

— + — =

16 12

вывел он в тетрадке и задумался.

Сначала нужно было найти наибольший общий делитель обоих знаменателей, потом разделить произведение знаменателей на этот наибольший общий делитель и найти тем самым наименьшее общее кратное, а потом... Впрочем, потом уже было не так трудно, самое трудное было, конечно, найти наибольший общий делитель.

— Точно так же мучился великий Евклид две тысячи лет тому назад, — сказал насмешливо Чип, когда Сережа пожаловался ему на неподатливость наибольшего общего делителя, — и ты знаешь, чем кончились эти мучения? Он нашел свой знаменитый алгоритм, который навсегда избавил от мучений пытливых искателей наибольшего общего делителя.

— Да я небось не пойму этот алгоритм, мы ведь только с 9-го класса начнем изучать информатику.

— А для таких, как ты, робких искателей Н.О.Д. неизвестный поэт воспел алгоритм Евклида в стихах:

— Ну, как я и думал, ничего непонятно, сплошные загадки, — уныло сказал Сережа.

— На то и загадки, чтобы их отгадывать. Ну, подумай сам, тут говорится про какое-то большое, меньшее и про Н.О.Д. Ты, конечно, догадался, Н.О.Д. — это и есть наибольший общий делитель двух чисел, который мы ищем.

— Ну, наверное, большое — это большее из этих двух чисел, а меньшее это меньшее. — Сережа несколько оживился. — Но потом непонятно: эти три числа меняются местами, делятся друг на друга, я не могу разобраться, что происходит?