«Красная шапочка» оказалась сложной сказкой для наших читателей. Но ближе всего к истине были программы Дины КОНОВАЛОВОЙ, г. Владивосток: Маши КВАНТАЛИАНИ, г. Тбилиси; Нади ЧУБЛОВОЙ, г. Тюмень; Маши ШКОЛЬНИК, г. Москва.

МОЛОДЦЫ!

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

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

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

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

Король с тоской оглядел огромные клумбы, усыпанные отборными цветами. Выбрать самую красивую из двух роз он еще сумел бы, но из тысячи... Если каждую из тысячи роз сравнить с каждой другой, это сколько же будет... тысяча раз по тысяче?..

— Билл, сколько это будет — тысячу раз по тысяче? — спросил он садовника, который вертелся рядом, не зная, как помочь королю.

— Не знаю, ваше величество, а только до завтрака не управимся!

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

— Ну, как, — Чип прервал свой рассказ и подмигнул Сереже, — можешь помочь королю? Нет? Тогда слушай дальше...

«В королевском саду наступила тяжелая пауза, которую прервал скрипучий голос Гусеницы:

ЕСЛИ розу выбираешь, ту, что лучше(всех иных),

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

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

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

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

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

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

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

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

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

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

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

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

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

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