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