Игры с Чипом

Прекрасный пример рекурсивной программы! Эта программа особенно понравилась Чипу, который вообще неравнодушен к рекурсивным программам и считает, что за ними будущее.

А Сереже больше понравилась программа Игоря про жирафа. Он прислал даже два варианта программы. Первый такой:

1. Если вам уже купили жирафа, то конец,

иначе продолжайте дальше.

2. Сейчас N = 1.

3. Принеси домой N кошек.

4. Если мама тебя отругала или выбросила кошек на улицу, увеличь N в два раза.

5. Попроси маму купить жирафа.

6. Если мама купила жирафа, то конец,

иначе переходи к строке 3.

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

— А смотри, что пишет про жирафа Кирилл:

Рекурсивная программа ЖИРАФ.

Чуть-чуть подумай.

Если не понял, почему не надо покупать жирафа, то ЖИРАФ,

а если понял, то КОНЕЦ.

По этой программе ты будешь думать, пока не поймешь, почему не надо покупать жирафа.

Они еще долго спорили и пришли к выводу, что обе эти работы заслуживают первого приза, но работа Кирилла чуть лучше, поскольку он свободно пишет рекурсивные программы и двойные циклы (это он сделал в своей сказке про зайца, которого выгнала из избушки лиса).

Поэтому было решено наградить их обоих калькуляторами: Кириллу дарит калькулятор британская фирма «Джеральд компьютерс», а Игорь получит советский калькулятор «Электроника». Вот фотографии победителей.

Остальные призеры награждены почетными грамотами. Ну, а те, кому на этот раз не удалось получить первый приз, пусть не вешают носа. Готовьтесь к конкурсу 1987 года!

Как угадать день рождения друга и вывести братьев из Болота Ошибок

Сережа с Чипом болтали о всякой всячине, когда Чип неожиданно спросил:

— Кстати, а когда у тебя день рождения?

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

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

— Ну, и сколько ты будешь гадать? До вечера-то успеешь?

— Месяц отгадаю после трех вопросов, а день — самое большее после четырех. Спорим? Тогда я начинаю. Июнь?

— Недолет!

— Сентябрь?

— Недолет!

— Ноябрь?

— Недолет!

— Значит, декабрь. Теперь день. 16-е?

— Недолет!

— 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 секунды. Насколько легче было бы считать нам, компьютерам, ведь мы основаны на двоичной системе.