Игры с Чипом

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

— Готово! — весело крикнул Чип с экрана. — Теперь-то мы с тобой поиграем на славу! [5] Ребята, Чип действительно может сделать такое чудо. Многие из вас видели электронные игры-приставки к телевизору. Этими играми управляют такие же маленькие чипы, что и сидят в компьютерах. Вот этот маленький человечек будет за тебя. — Чип показал на смешного, карикатурного мальчика рядом с собой. Тот помахал Сереже рукой и улыбнулся до ушей. — Управлять ты им будешь с помощью ручек настройки телевизора. Поверти их и увидишь, что человечек будет двигаться, куда ты захочешь. А уж говори за него сам.

Сережа повертел ручки и скоро понял, как управлять мальчиком и как двигать его руками.

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

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

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

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

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

Чип обернулся к Сереже, открыл рот, чтобы что-то сказать, но сторож так погрозил пальцем, что Чип прикусил язык и только умоляюще смотрел: не подкачай, мол.

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

«Так, — подумал Сережа, — полезем налево, там, помнится, было больше яблок. Только бы потом не забыть и про правую ветку».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ОТ РЕДАКЦИИ:

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

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

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

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

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

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

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