Игры с Чипом
Шрифт:
Сегодня Чип и Сережа предлагают вам забыть про лень и заняться таким делом. Представьте, когда часы бьют, из них выглядывают раз в час петух, а раз в час кукушка. А каждые 12 часов они появляются вместе и хвалят друг друга. Как составить программу для таких электронных часов?
Простой вариант программы: одна кукушка каждый час поет и каждые 12 часов танцует.
Лучшие программы мы напечатаем. Ждем ваших писем. На конверте укажите: «Кукушка и петух».
Приключения
— Знаешь, как меня назвала одна девочка в письме? — гордо сказал Чип в первое теплое майское воскресенье, когда они с Сережей устроились у раскрытого окна. — Ни за что не угадаешь! Электронный мальчик с пальчик, вот как.
— И прекрасно, — подхватил Сережа, — расскажи мне сказку про современного электронного мальчика с пальчик, вроде сказок для роботов Лема.
Чип не заставил себя долго упрашивать, видно, маленькому хвастунишке нравилось рассказывать про себя. Он уселся, поджав ножки, на коробке своего калькулятора, поднял с важным видом палец кверху и начал так:
— В некотором вычислительном центре, в некотором машинном зале жил да был маленький Чип. Он был самым младшим в семье. Шестеро его старших братьев и его родители день и ночь гнули спину на своего хозяина — Центрального Процессора. Работа перепадала и Чипу, да какой с маленького прок! Поздно вечером, когда работы было поменьше, родители ворчали: «Одна морока с этими малышами, все приходится за них доделывать, без них было легче».
И вот как-то ночью Чип услышал, что родители сговариваются завести его с братьями в Лес Неправильных Программ да там и оставить. А это был страшный лес, там на каждом шагу подстерегали опасности: то бесконечный цикл закрутит, засосет, и не вырвешься; то Двоичное дерево своими ветками-рогатками запутает, затянет — начнешь их обходить и сгинешь без следа, только тебя и видели.
Но страшнее всего в том лесу был огромный великан Гигабайт. Сидел он в своей Директории, окруженный верными слугами — Дисководами, и поджидал неосторожных путников. Ему сотню бит проглотить, как муху, — даже и не заметит. Вот к нему-то и привели братьев жестокие родители.
Великан был сыт, видно, перехватил сотню-другую килобайт на ужин, поэтому он отложил добычу на завтрак, а пока решил развлечься загадками, чтобы нагулять аппетит.
— Эй, мелюзга, видите эти весы? — Он показал на огромные весы с коромыслом и двумя чашками. — Если догадаетесь, как найти самого легкого, не больше шести раз сравнивая вас друг с другом на этих весах, то этого самого легкого я отпущу.
Братья призадумались. Конечно, самый легкий — маленький Чип, но это нужно доказать, всего шесть раз сравнивая братьев друг с другом. Если бы можно было начать с Чипа, то, конечно, шесть раз сравнив его с остальными, можно доказать, что он самый легкий. Но коварный Гигабайт не станет их слушать, начнет с кого захочет и все шесть раз истратит на то, чтобы проверить, что он не самый легкий.
И вдруг маленький Чип звонко крикнул: «Я знаю, я знаю! Только ты не обманешь, отпустишь самого легкого?»
Великан
— Эту загадку не смогли решить уважаемые процессоры на радиолампах, не смогли решить их заслуженные ученики на полупроводниках, а ты, малявка, и подавно не сможешь!
— Ну, а все-таки, — малыш не унимался, — если решу, то отпустишь?
— Да я вас всех отпущу и в дорогу провожатого дам, только, ха-ха, вернее всего, вам дорога будет в котел.
— Ну смотри, Гигабайт, все слышали твое обещание, так чтобы потом тебе обманщиком не прослыть.
Великан побагровел, топнул ногой и взревел:
— Клянусь великим Винером {1} , этот мальчишка выведет меня из себя! Я от своих слов не отступаюсь, я за всю жизнь ни бита неправды не сказал. А ну-ка давай выкладывай свой алгоритм, пока я тебя...
— Итак, слушай, — спокойно сказал маленький Чип. — Берешь первого попавшегося и временно объявляешь его самым легким, а потом по очереди сравниваешь остальных с самым легким. При этом ты после каждого сравнения временно называешь самым легкимтого, кто на этот раз оказался легче.
— Ну-ка, постой, — перебил его великан, — ты мне что-то голову заморочил, я так не понимаю. Давай-ка проверим! — Он схватил двух самых больших братьев и бросил на весы. — Так, этот вроде немного полегче, объявляем его временно самым легким. — Он схватил еще одного из старших братьев. — Ага, этот еще легче, значит, теперь его временно объявляем самым легким. — Он схватил следующего. — А этот тяжелее, значит, самым легким остается предыдущий. — Четвертый раз сравниваем вот с этим, ага, прежний остался самым легким, и... вот ты, мелюзга, оказываешься самым легким. Хм... действительно, за шесть раз нашел. Это, наверно, случайно так получилось — попробуем в другом порядке сравнивать... так... так, опять за шесть раз этот малыш самым легким оказался!
— Ну как, отпускаешь? — весело спросил младший брат.
Великан насупился.
— Я одного обещал отпустить и свое слово сдержу. Иди и помни мою доброту.
— А мои братья? — закричал возмущенный Чип. — Ты их тоже обещал отпустить: провожатого можешь не давать!
— Это ты случайно задачу решил, — возразил Гигабайт. — Вот докажи, что ты на самом деле умный, — найди еще один такой алгоритм, и я отпущу еще одного брата...
Чип прервал свой рассказ и хитро посмотрел на Сережу.
— Ну и как ты думаешь, удалось электронному мальчику с пальчик спасти всех братьев? Составил он еще 6 алгоритмов, как найти самого легкого из 7, шесть раз сравнивая всех попарно на весах? Подскажу тебе, что братьев можно разбить на группы: по двое, по трое и так далее и сначала находить самого легкого в каждой группе, а потом уже сравнивать их между собой.
— Погоди, — спохватился Сережа, — ты же мне не объяснил, что такое алгоритм. Это что, правило взвешивания?
— В этом случае это правило взвешивания, а вообще — такой порядок действий, который всегдаприводит к желаемому результату.