Игры с Чипом

— Ваше величество, я, конечно, человек темный, но эту Гусеницу я знаю — она слов на ветер зря не бросает. Ей-богу, она нам дельный совет дала, да только как его разгадать — ума не приложу.

— А я говорю, что все это вздор! — Король не на шутку разгневался. — Во-первых...»

— Постой, постой, — закричал Сережа, — я понял, понял! Это же конкурс поросят! Которые песенки поют! А я-то слушаю, уши развесил, думаю, что же это мне напоминает?

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

Значит, ты понял, что Гусеница прочла не простой стишок, а рекурсивную программу, вернее, подпрограмму «Лучше (среди кого-то)». И что эта подпрограмма уже встречалась нам раньше, в конкурсе поросят.

— Да, и там это называлось «Лауреат (среди поросят)». Там тоже надо было сравнить первого поросенка с лауреатом (среди остальных).

Только   мы   сравнивали   пение   поросят,   а здесь — красоту роз, вот и вся разница.

— Ну, и как же должны король с садовником сравнивать розы по этому алгоритму? Можешь рассказать?

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

— Так, ну, а дальше?

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

— Ну, а если бы мы не знали заранее, как сравнивать между собой три розы? Ведь именно это остановило короля — он не знал, как сравнивать 999 роз, и потому считал совет Гусеницы вздорным.

— Погоди, мы это, помнится, тоже разбирали с поросятами. Если мы не знаем, как выбирать лучшую из какого-то числа роз, то мы все равно должны откладывать первую в сторону и пытаться выбирать из оставшихся с тем, чтобы потом сравнить лучшую с отложенной. Значит, они будут откладывать 998 роз, пока не останется только две, которые король сможет сравнить. Потому он лучшую из первых двух сравнит с 998-й, лучшую из этих — с 997-й и так далее. За 999 сравнений и 998 откладываний они найдут самую красивую розу в подарок королеве. И вовсе не надо сравнивать тысячу тысяч раз... Чип, что же это получается — они срежут всю клумбу, чтобы выбрать лучшую розу? А как на это посмотрит королева?

— Королева? Гм-гм... — Чип был явно смущен. — Ну, во-первых, они могут не срезать и не откладывать, а, скажем, повязывать на розы номерки, а во-вторых, во-вторых. Гусеница могла и не знать про привычки королевы!

— Чип, во-первых, если король и садовник будут повязывать на розы номерки, они провозятся весь день. А во-вторых, Гусеница, конечно, могла и не знать привычки королевы, но ты-то прекрасно знал это условие. Эх ты, Чип!

ОТ РЕДАКЦИИ:

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

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

А как решить ту же задачу, если розы растут не на клумбе, а в один ряд вдоль садовой дорожки?

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

Литературный экскурс в историю счетных машин

— Расскажи мне какую-нибудь историю, пострашней и потаинственней, — попросил Сережа. — Лучше всего про Шерлока Холмса и доктора Уотсона.

— Потаинственней? — Чип  задумался  и  начал зловещим голосом:

«Доктор Уотсон протянул озябшие руки к камину и повторил:

— Нет. Холмс, это не человек, это сам дьявол! Человек не может не оставлять следов и не делать ошибок.

Холмс ничего не ответил. Полузакрыв глаза, он сидел, вытянув длинные ноги, и как будто дремал. Только пальцы, нервно барабанящие по каминной полке, выдавали, что лучший ум Лондона напряженно работает над новой задачей.

Неожиданно он вскочил. Глаза его лихорадочно блестели.

— Едемте, Уотсон, нельзя терять ни минуты!

— Но куда?

— Объясню по дороге. Эй, кеб! Кебмен, нам нужно попасть в Сохо не позднее полуночи. Вот вам соверен, гоните! Уотсон, вам доводилось слышать о леди Лавлейс?

— Ада Лавлейс? Дочь великого Байрона! Уж не хотите ли вы сказать, что она замешана в этой серии дерзких преступлений? Грабительница-аристократка, дочь поэта? Я верно рассуждаю, Холмс?

— О нет, дорогой друг, ваше воображение не в меру разыгралось. Ада Лавлейс замешана в этом деле, но не так, как вы думаете.

— Но как же, Холмс? Я теряюсь, вы говорите загадками.

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

Холмс откинулся в глубину кеба и увлек за собой Уотсона. Вынырнув из тумана, на большой скорости приближался черный экипаж. Возница в плаще и маске нахлестывал лошадей. С первым ударом Биг-Бена в доме напротив внезапно отворилось окно, из него вылетел сверток и тяжело звякнул о булыжную мостовую. Из притормозившего экипажа высунулась рука, чтобы подхватить сверток... Но Холмс оказался проворнее.

— Ни с места, Мориарти! — закричал он громовым голосом, осаживая лошадей. Подоспевший Уотсон распахнул дверцу и приставил револьвер к виску неуловимого профессора Мориарти — некоронованного короля Лондонского преступного мира...

— И все-таки, Холмс, я никак не могу взять в толк, при чем же здесь почтенная леди Лавлейс? — Уотсон с наслаждением отхлебнул горячего кофе, устроился поудобнее у камина и вопросительно поглядел на Шерлока Холмса. — Вы же знали, что это Мориарти, не так ли?

— Напротив, мой друг, я и не подозревал об этом до самой последней минуты. Мои мысли шли по другому пути, на который натолкнули меня вы.

— Я? Но чем же? Я, право, в полнейшем замешательстве.

— А помните, вы давеча сказали, что человек не может не ошибаться? Вы оказались правы, Уотсон, никакой человек, даже пресловутый Мориарти, не смог бы так точно и аккуратно работать, как машина Бэббиджа.

— Машина Бэббиджа? Позвольте, позвольте, это тот чудак, который насмешил все лондонское общество лет тридцать назад? Какая-то дурацкая машина, которая складывала два и два дольше, чем это сделал бы самый тупой сыщик из Скотленд-Ярда? Ах, теперь мне понятно, почему вы вспомнили о леди Лавлейс. Она пыталась поддержать несчастного изобретателя, даже написала трактат о думающих машинах. Но о нем все быстро забыли.

— Леди Лавлейс была умнейшей женщиной, Уотсон, — Холмс помешал кочергой угли и добавил с