Игры с Чипом

ТО ты первую сличаешь с той, что лучше (остальных).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ОТ РЕДАКЦИИ:

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

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

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

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

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