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