Игры с Чипом

Сережа задумался: «Прежде чем посылать мальчика на вторую яблоню, надо составить план. Вот полезет он на яблоню и вдруг — развилка. Тут надо действовать по порядку, чтобы ничего не спутать. Залез на одну ветку — обери ее до конца и уж только потом переходи к следующей. А на той ветке, где яблок уже не осталось, ниточку повяжи. Тогда хоть десять веток у тебя на развилке — все равно не перепутаешь. Спустился, например, с седьмой ветки, повязал ее у ствола ниточкой и оглядись: сколько еще не повязанных веток на этой развилке осталось. Ага, вот эти три, возьми любую и лезь на нее да яблоки собирай.

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

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

Выбравшись из телевизора, Чип гордо заметил: «Все-таки не зря я тебя учил рекурсивным сказкам и стишкам».

— А при чем тут они? — удивился Сережа. — Я просто составил план: добраться до первой развилки и по такому же плану просмотреть каждую ветку.

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

Чип смущенно покашлял, принял торжественную позу и продекламировал:

Рекурсивный стих-подпрограмма

ОБИРАЕШЬ (ветку)

По стволу ты полезай, видишь яблоко — хватай.

На развилку вылез вдруг — ОБИРАЕШЬ (каждый сук).

Яблоки собрал — ВОЗВРАТ: лезешь по стволу назад.

Здесь все дело во второй строчке. Если ветка разветвляется, то и строчку тоже надо разветвить: заменить слова ОБИРАЕШЬ (каждый сук) на весь стишок для каждого сучка. Сколько сучков, столько и стишков. Если и те разветвятся, то и стишки размножатся. Вот смотри, как это нарисовал художник.

— Знаешь, — продолжал Чип, — после цикла «дерево» — самое важное в программировании. Конечно, не яблоня и не дуб, а «дерево», как схема выбора. Подпрограмма, которую мы составили, так и называется во всех учебниках: «обход дерева». Все программы, которые управляют сложными процессами, например, ведут воздушный бой или играют в шахматы, перебирают варианты, как и при сборе яблок с дерева. А компьютеры будущего, ученые называют их компьютеры пятого поколения, смогут сами перебирать варианты. Скажешь им: «Собери все яблоки», — и они будут автоматически обходить все ветки, не пропуская ни одной.

Ну ладно, — закончил свои объяснения Чип, — небо-то прояснилось, надо тебе и погулять.

ОТ РЕДАКЦИИ:

Ребята, сегодня Чип вам дает задание составить рекурсивную подпрограмму для сбора плодов с дерева манго.

Представьте тропический лес, деревья, опутанные лианами, усыпанные гнездами попугаев. Лианы спускаются на землю, свисают над водой, а где-то оказывается, что это не лианы даже, а змеи...

Как собрать с дерева все плоды и не набрать в корзинку птичьих гнезд?

Один шаг Чип вам подскажет:

«Если сполз по ветке на землю, снова иди к дереву».

Лучшие подпрограммы будут напечатаны. На конверте напишите название задания: «ПРИКЛЮЧЕНИЕ В ДЖУНГЛЯХ».

Как уговорить маму купить жирафа

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

— Ну как ты моешь пол?! То тут, то там машешь тряпкой без толку, а вода остывает. Вот этот угол ты уже третий раз трешь, а про тот забыл.

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

— Пожалуйста, вот тебе рекурсивная подпрограмма:

ВЫМОЙ (пол).

Если пол вымыт, то возврат.

Протри тряпкой полоску от левого дальнего до правого дальнего от двери угла.

ВЫМОЙ (оставшуюся часть пола).

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

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

— Составить-то можно, а вот как она будет работать, это еще надо посмотреть. Ну вот что бы ты хотел?

— Скажем, я хотел бы, чтобы мама мне купила жирафа!

— А что. — задумался Чип. — под окном привяжешь, у вас второй этаж, можно прямо через окно кормить. Словом, никаких хлопот и море удовольствия. Осталось только маму уговорить. Да, тут нужна очень хорошая программа. Это будет программа для тебя: как ты должен себя вести, чтобы мама купила жирафа. У тебя есть идеи, что может на нее подействовать?

— Ну, скажем, — протянул Сережа, все больше увлекаясь своей шуткой, — скажем, я дождусь, когда она меня будет за что-нибудь ругать, что я руки мыть перед едой забываю или что я поздно спать ложусь, а я тут возьму да и скажу: «А вот спорим, я за всю четверть больше ни разу так не сделаю?» Она скажет: «Свежо предание, да верится с трудом». А я в ответ: «Ну что, спорим?» А она спросит: «А на что?» Я в ответ: «Да хоть на жирафа». А она возьмет и в шутку согласится!

— Ну, а где же вы его возьмете, этого жирафа?

— А я поступлю в кружок юннатов при зоопарке, и, когда маленький жирафенок будет болеть, я с ним ночи не буду спать, выхожу, а потом...

— Слушай, Сережа, а у меня другая идея: давай предложим всем ребятам эту задачу. Пусть наши читатели попробуют составить программу, как уговорить маму купить жирафа. У всех разные мамы, и каждый придумает свой способ. Все дело в том, чтобы записать его в виде программы последовательных действий, вроде той, которую мы начали составлять.

— И еще, — подхватил Сережа, — пусть попробуют написать программу для чистки картошки, вроде той, которую ты предложил для мытья пола.

— А последнее — пусть запрограммируют стишок, сказку или считалку по своему выбору, вроде тех, которые мы с тобой раньше сочиняли. Только пусть хорошенько проверят, правильно ли программа работает, прежде чем посылать ее нам. Советуем всем ребятам дождаться следующего номера журнала, где мы с тобой будем разбирать их письма со сказками «Теремок» и «Красная Шапочка», а уже потом присылать свои программы. 

ОТ РЕДАКЦИИ:

Итак, журнал «Пионер» вместе с Чипом и Сережей объявляет конкурс на лучшие программы, составленные нашими читателями самостоятельно, без помощи взрослых. В конкурсе три задачи:

1. Как уговорить маму купить жирафа.