2. Краткое описание Роботландских исполнителей

   В этом разделе приводится краткое описание роботландских ис-
полнителей, на базе которых построены задачи сборника. Этот ма-
териал  нельзя  рассматривать как учебный, но им можно  пользо-
ваться как справочником. Подробные учебные пособия по описанным
ниже исполнителям распространялись для  участников  Олимпиады и
Курсов вместе с методическими рекомендациями, адресованными ру-
ководителям команд.

2.1. Понятие исполнителя

   Исполнителем  называется человек,  коллектив,  животное  или
техническое устройство,  которые  понимают и умеют точно испол-
нять задаваемые им команды из строго определенного списка.
   Набор понятных исполнителю команд называется системой команд
этого исполнителя, или сокращенно СКИ.
   Обстановка, в  которой  работает исполнитель называется  его
средой.
   Различные исполнители получают свои команды по-разному.  Уп-
равляя автомобилем,  например, надо нажимать на педали, дергать
за  рычажки  и  крутить  руль. А исполнитель-курсор  на  экране
компьютера получает  свои  команды  ВЛЕВО, ВПРАВО, ВВЕРХ, ВНИЗ,
когда человек нажимает  на  клавиатуре клавиши со стрелками или
перемещает по коврику манипулятор-мышь.
   Важно знать,  как меняется среда исполнителя, когда исполни-
тель выполняет команды из своей СКИ.
   Управление исполнителем может привести к одной  из двух ава-
рийных ситуаций (отказов),  одна  из них условно называется "Не
понимаю", другая - "Не могу".
   Отказ "Не понимаю" возникает у  всех  исполнителей  в  одном
случае - когда задается команда, не входящая в СКИ.
   Отказ "Не могу"  специфичен для каждой команды из СКИ испол-
нителя - он  возникает, когда условия среды не позволяют испол-
нителю выполнить заданную команду.
   Для знакомства с исполнителем  можно  использовать следующую
схему:
                 СХЕМА ЗНАКОМСТВА С ИСПОЛНИТЕЛЕМ
                         ┌─────────────┐
                         │ ИСПОЛНИТЕЛЬ │
                         └──────┬──────┘
                         ┌──────┴─────┐
                     ┌───┴───┐    ┌───┴───┐
                     │ СРЕДА │    │  СКИ  │
                     └───────┘    └───┬───┘
                             ┌────────┴──────────┐
                             │      КОМАНДЫ      │
                             ├───────────────────┤
                             │ Как задаются      │
                             │ Как выполняются   │
                             │ Когда "Не могу"   │
                             └───────────────────┘


2.2. Понятие алгоритма и программы

   Алгоритм -  это  описание  действий исполнителя, необходимых
для выполнения определенной работы в среде.
   Для того чтобы алгоритм стал понятен исполнителю его записы-
ваю при помощи СКИ. Такая запись  алгоритма называется програм-
мой.
   Для записи  программ  часто  пользуются специальными языками
программирования. В эти языки наряду  с  командами  СКИ  входят
процедуры, описывающие новые команды (команды пользователя),  и
управляющие структуры, предназначенные для более краткой и наг-
лядной записи алгоритма.
   Однако, исполнитель понимает  только  команды из своей СКИ и
выполнить программу, написанную на  языке  программирования са-
мостоятельно  не  может. Для "перевода" текста программы в  СКИ
исполнителя строят новый  исполнитель, называемый интерпретато-
ром (транслятором) языка. Процесс  выполнения  программы, напи-
санной на языке программирования, упрощенно поясняет  следующая
схема:
┌──────────┐     ┌──────────┐     ┌───────────┐     ┌─────────┐
│Программа │     │          │     │           │     │         │
│на языке  │────>│Транслятор│────>│Исполнитель│────>│  Среда  │
│программи-│     │          │     │           │     │         │
│рования   │     │          │     │           │     │         │
└──────────┘     └──────────┘     └───────────┘     └─────────┘


2.3. Буквоед

   Буквоед -  это исполнитель, СКИ которого неизвестно, поэтому
Буквоеда часто называют "черным ящиком".
   Буквоед предназначен  для игры в отгадывание алгоритмов, его
можно представить как робот со специальным разъемом на корпусе
в который устанавливается магнитная карточка с программой.
   Как отгадать алгоритм работы программы? Можно провести серию
опытов: подавать  через  входное устройство Буквоеда (вход) ин-
формацию и наблюдать  за тем, что появляется на выходном устрой-
стве (выход)  в  результате  работы программы. Анализируя опыты,
можно построить догадку (гипотезу) и проверить ее, выполнив но-
вую серию опытов-тестов.

  Пример.

   По результатам  опытов  с Буквоедом была заполнена следующая
табличка:
               ┌────┬─────┐
               │Вход│Выход│
               ├────┼─────┤
               │0   │1    │
               │1   │1    │
               │кот │3    │
               │лето│4    │
               │x1  │2    │
               │234 │3    │
               └────┴─────┘
   По какому алгоритму работает программа?

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


2.4. Плюсик

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

               ┌───────┐   ┌───────────┐
               │ Стек  │   │Вычислитель│
               └───────┘   └───────────┘

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

   Вычислитель предназначен для  выполнения арифметических опе-
раций над целыми неотрицательными числами.

                               СКИ

ЗАПОМНИ число - Число, записанное в команде отправляется на хра-
                нение в стек.
 СЛОЖИ        │ Все  эти  команды  работают одинаково: Из  стека
 ВЫЧТИ        │ последовательно извлекаются два  числа и отправ-
 УМНОЖЬ       │ ляются в вычислитель для выполнения соответству-
 ДЕЛИ         │ ющей арифметической  операции. Результат помеща-
              │ ется в стек. Последнее извлеченное из стека чис-
              │ ло вычислитель  считает первым операндом  опера-
              │ ции, а первое - вторым. Ситуация  отказа "Не мо-
              │ гу" возникает  тогда,  когда в стеке меньше двух
              │ чисел, или  результат вычислений - отрицательное
              │ число, или выполняется деление на 0. Команда ДЕ-
              │ ЛИ выполняет деление нацело.
ОЧИСТИ        - Выполнение этой команды приводит к  автоматичес-
                кому удалению всех чисел из стека.

   Плюсик позволяет познакомиться с непривычной записью арифме-
тического выражения, которую часто используют при  проектирова-
нии трансляторов.  Это так  называемая обратная польская за-
пись:
  обычная запись выражения:  a + b * (c + d/e)/f
  обратная польская запись того же выражения: abcde/+*f/+

Сравните:
  обычная запись выражения:  2 + 5 * (10 + 134/12)/7
  программа для Плюсика:
                         ЗАПОМНИ 2
                         ЗАПОМНИ 5
                         ЗАПОМНИ 10
                         ЗАПОМНИ 134
                         ЗАПОМНИ 12
                         ДЕЛИ
                         СЛОЖИ
                         УМНОЖЬ
                         ЗАПОМНИ 7
                         ДЕЛИ
                         СЛОЖИ

   Для преобразования обычного выражения в программу для Плюсика
можно просматривать выражение последовательно слева направо, за-
писывая команды
                      ЗАПОМНИ число
   Если после  очередной  записи команды ЗАПОМНИ выяснится, что
над последними двумя числами в стеке  можно выполнить арифмети-
ческую операцию, записывается соответствующая команда.

   Пример.

   Выражение: 28*(36-700/5)+15    (*)

   Составление программы для Плюсика:

   Просматриваем запись  (*) слева направо и записываем команды
ЗАПОМНИ:

ЗАПОМНИ 28   (нельзя выполнить операцию)
ЗАПОМНИ 36   (нельзя выполнить операцию)
ЗАПОМНИ 700  (нельзя выполнить операцию)
ЗАПОМНИ 5    (можно выполнить деление)
ДЕЛИ         (700/5, можно выполнить вычитание)
ВЫЧТИ        (36-700/5, можно выполнить умножение)
УМНОЖЬ       (28*(36-700/5), нельзя выполнить операцию)
ЗАПОМНИ 15   (можно выполнить сложение)
СЛОЖИ        (28*(36-700/5)+15)


2.5. Кукарача

  Средой исполнителя является клетчатое поле размером 10x10:
              1  2  3  4  5  6  7  8  9  10
             ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
           1 │¤ │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           2 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           3 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           4 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           5 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           6 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           7 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           8 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           9 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           10│  │  │  │  │  │  │  │  │  │  │
             └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘

   На рисунке  символом "¤" изображен исполнитель. Кукарача мо-
жет переползать из  клетки в клетку вверх, вниз, влево, вправо,
но не по  диагонали. Выход исполнителя за пределы поля запрещен
(ситуация "Не могу!"). Кроме самого исполнителя в каждой клетке
может находиться кубик  с нанесенным на его грань символом. Ку-
карача, перемещаясь по  полю,  может толкать один или несколько
кубиков перед собой и даже "сбрасывать" кубики за пределы поля.
   Некоторые кубики на поле могут иметь "скрытые" надписи: счи-
тается, что такие кубики расположены в  клетке "надписью вниз".
Толкая скрытый кубик, Кукарача перемещает его в следующую клет-
ку по ходу движения и переворачивает.
   Толкая кубик,  исполнитель  в  состоянии прочитать символ на
его грани независимо от того, была ли надпись обычной или скры-
той.
   Модифицированный исполнитель Кукарача-97 расширяет описанную
выше среду  за  счет  возможного увеличения размеров клетчатого
поля до величины 99x99 клеток. Реальный  размер клетчатого поля
становится частью условия задачи и, по умолчанию, остается, как
и прежде, 10x10  клеток. Кроме того, Кукарача-97 может иметь не
одно клетчатое поле, а  несколько.  Они "сложены" в стопку друг
на друга.  Исполнитель может перемещаться  с поля на поля в со-
седние клетки, расположенные выше или ниже текущей. По-прежнему
запрещено движение по диагонали.  Количество  полей Кукарачи-97
может достигать числа 99.

                               СКИ

ВПРАВО - сместиться на одну клетку вправо на поле
ВЛЕВО  - сместиться на одну клетку влево на поле
ВВЕРХ  - сместиться на одну клетку вверх на поле
ВНИЗ   - сместиться на одну клетку вниз на поле
ВПЕРЕД - сместиться вниз в соседнее поле, не меняя своего по-
         ложения внутри полей (только для Кукарачи-97)
НАЗАД  - сместиться вверх в соседнее поле, не меняя своего по-
         ложения внутри полей (только для Кукарачи-97)
СТОЯТЬ - "пустая" команда, исполнитель не выполняет никаких
         действий (только для Кукарачи-97)

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

           Язык программирования для Кукарачи

   1) Программа представляет собой последовательность процедур,
записанных в любом порядке в программном  окне компьютерной мо-
дели исполнителя. Имя процедуры может быть использовано наравне
с командой из  СКИ Кукарачи. В программе должна быть предусмот-
рена одна  "главная"  процедура:  с  нее  начинается выполнение
программы, в процессе работы которой могут  вызываться по своим
именам другие процедуры и команды из СКИ исполнителя.

   2) Описание каждой процедуры должно иметь вид:
             ┌────────────────┬───────────────────┐
             │     Вид        │      Описание     │
             ├────────────────┼───────────────────┤
             │ЭТО имя         │начало процедуры   │
             │ список команд  │тело процедуры     │
             │КОНЕЦ           │конец процедуры    │
             └────────────────┴───────────────────┘
3) Комментарии (только в Кукараче-97)

     Комментарии могут  располагаться  как  в процедурах, так и
между ними. Комментарий имеет вид:

             // начало комментария и до конца строки

4) Разделители слов языка
   В  качестве  разделителей слов языка служат пробелы и  концы
строк.

5) Команды.
     Команды бывают простые и составные.

5.1) Составная команда (только в Кукараче-97)
     Составная команда имеет структуру:
             ┌────────────────┬───────────────────┐
             │     Вид        │      Описание     │
             ├────────────────┼───────────────────┤
             │{               │начало составной   │
             │ список команд  │тело составной     │
             │}               │конец составной    │
             └────────────────┴───────────────────┘
5.2) Простые команды
5.2.1) Команда из СКИ исполнителя
          ┌────────┬─────────────────────────────────┐
          │Вид     │             Описание            │
          ├────────┼─────────────────────────────────┤
          │ ВЛЕВО  │Сместиться влево на одну клетку  │
          │ ВПРАВО │Сместиться вправо на одну клетку │
          │ ВВЕРХ  │Сместиться вверх на одну клетку  │
          │ ВНИЗ   │Сместиться вниз на одну клетку   │
          │ ВПЕРЕД │Сместиться вниз на одно поле     │
          │ НАЗАД  │Сместиться вверх на одно поле    │
          │ СТОЯТЬ │Стоять на месте                  │
          └────────┴─────────────────────────────────┘

5.2.2) Вызов процедуры
   Для вызова процедуры в программе записывается ее имя.

5.2.3) Цикл ПОВТОРИ
            ┌───────────────────┬───────────────────┐
            │     Вид           │      Описание     │
            ├───────────────────┼───────────────────┤
            │ПОВТОРИ n команда  │Выполнение  команды│
            │                   │повторяется  безус-│
            │                   │ловно n раз.       │
            └───────────────────┴───────────────────┘
     Здесь n - целое неотрицательное число.

5.2.4) Цикл ПОКА
        ┌────────────────────┬───────────────────────────────┐
        │    Вид             │            Описание           │
        ├────────────────────┼───────────────────────────────┤
        │ПОКА условие команда│Пока выполнено условие,  выпол-│
        │                    │няется  команда.  Если  условие│
        │                    │ложно изначально, то команда не│
        │                    │выполнится ни разу.            │
        └────────────────────┴───────────────────────────────┘

5.2.5) Условная команда
        ┌────────────────┬─────────────────────────────┐
        │    Формат      │           Описание          │
        ├────────────────┼─────────────────────────────┤
        │ЕСЛИ  условие   │В  зависимости  от истинности│
        │ ТО     команда1│условия выполняется  команда1│
        │ ИНАЧЕ  команда2│после ТО или  команда2  после│
        │                │ИНАЧЕ. Ветвь  ИНАЧЕ может от-│
        │                │сутствовать.                 │
        └────────────────┴─────────────────────────────┘

6) Условие
     Ниже перечислены допустимые конструкции условий:
   "символ" -  условие  истинно, если исполнитель толкнул кубик
со знаком "символ" на нем;
   ПУСТО -  условие  истинно,  если  исполнитель переместился в
пустую клетку (в ней не было кубиков).
   Условия можно использовать с ключевым словом НЕ.
   Исполнитель способен проверить условие в своей среде в любой
момент. Изначально, когда  Кукарача  еще не толкал кубиков, ис-
тинным считается условие ПУСТО.

   Пример программы.

Задача. Помогите Кукараче взобраться по лесенке.
              1  2  3  4  5  6  7  8  9  10
             ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
           1 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           2 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           3 │  │  │  │  │  │  │┌─┼─ │  │  │
             ├──┼──┼──┼──┼──┼──┼┼─┼──┼──┼──┤
           4 │  │  │  │  │  │┌─┼┘ │А │  │  │
             ├──┼──┼──┼──┼──┼┼─┼──┼──┼──┼──┤
           5 │  │  │  │  │┌─┼┘ │К │  │  │  │
             ├──┼──┼──┼──┼┼─┼──┼──┼──┼──┼──┤
           6 │  │  │  │┌─┼┘ │Н │  │  │  │  │
             ├──┼──┼──┼┼─┼──┼──┼──┼──┼──┼──┤
           7 │  │  │┌─┼┘ │Е │  │  │  │  │  │
             ├──┼──┼┼─┼──┼──┼──┼──┼──┼──┼──┤
           8 │  │┌─┼┘ │С │  │  │  │  │  │  │
             ├──┼┼─┼──┼──┼──┼──┼──┼──┼──┼──┤
           9 │┌─┼┘ │Е │  │  │  │  │  │  │  │
             ├┼─┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
          10 │¤ │Л │  │  │  │  │  │  │  │  │
             └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘

 Решение.

ЭТО Лесенка
    ПОВТОРИ 7 Ступень
КОНЕЦ

ЭТО Ступень
  ВВЕРХ
  ВПРАВО
КОНЕЦ


2.6. Корректор

   Корректор работает  с  длинной  лентой,  которая  разбита на
клетки или  ячейки (в компьютерной реализации Кукарачи-97 лента
имеет 80 клеток). В ячейку может быть записан один символ. Сим-
вол - это буква, цифра, знак  "+" или что-нибудь еще в этом ро-
де. допускающее ввод с клавиатуры. Полный набор допустимых сим-
волов составляет алфавит исполнителя.
   Считается, что лента склеена  в  кольцо и спрятана в непроз-
рачный для  Корректора  футляр. Исполнитель может видеть только
одну ячейку ленты через  специальное  окно в футляре, и записы-
вать в "оконную" ячейку любые  символы  из  своего алфавита. Он
может также перемещать окно вправо и влево вдоль ленты и, таким
образом, записывать символы в любые ячейки на ней.
   Еще робот имеет ящик - специальную  ячейку  памяти.  В  ящик
Корректор может снимать копию с той клетки ленты, которая видна
через окно.


                        ┬─┬
                        │т│               - ящик Корректора
                        ┴─┴
                                                                                                                       │
┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
│░│░│░║т║е│к│с│т│ │н│а│ │л│е│н│т│е│░│░│░│ - лента Корректора
┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴
       │
       └── "окно" на ленте

   Ниже приводится полный  набор  команд Корректора и его алфа-
вит.

                               СКИ
 ВПРАВО      - Переместить окно на одну клетку ленты вправо.
 ВЛЕВО       - Переместить окно на одну клетку ленты влево.
 ПИШИ символ - Записать указанный символ в клетку на ленте.
 ЯЩИК+       - Копировать символ с ленты в ящик.
 ЯЩИК-       - Копировать символ из ящика на ленту.
 ОБМЕН       - Поменять местами  содержимое  ящика  и  "оконной"
               ячейки ленты.
 ПЛЮС        - Заменить символ на ленте  символом,  следующим по
               порядку в алфавите Корректора. Команда приводит к
               отказу (ситуация "Не могу"), когда в оконной ячей-
               ке перед ее выполнением записан последний  символ
               алфавита (символ "@").
 МИНУС       - Заменить символ на ленте символом, предыдущим  по
               порядку в алфавите Корректора. Команда приводит к
               отказу (ситуация "Не могу"), когда в оконная ячей-
               ка пуста (в ней записан символ ПУСТО).
 СТОЯТЬ      - пустая команда; ее выполнение не вызывает
               никаких изменений в среде Корректора.

                     Алфавит Корректора
      ПУСТО 0 1 2 3 4 5 6 7 8 9 а б в г д е ж з и й к л
      м н о п р с т у ф х ц ч ш щ ъ ы ь э ю я   - + / *
      = < > ( ) [ ] { } . , ! ? ; : ' " # | $ % ~ @

   Для управления Корректором можно использовать программы, ко-
торые записываются на том же самом  языке программирования, что
и программы для Кукарачи.
   Отличие: другая  СКИ  и  другие условия, которые исполнитель
может проверять в своей среде.
   Обычно в качестве условия  записывают  символ. Интерпретатор
языка  сравнивает  его с тем символом, который Корректор  видит
через  окошко  на ленте. Если они совпадают, условие  считается
выполненным, если отличаются - условие ложно.
   Для обозначения  пробела  и пустого места можно использовать
ключевые слова ПРОБЕЛ и ПУСТО. Эти же ключевые  слова можно ис-
пользовать и в команде ПИШИ.
   При  записи  условия можно применять ключевое слово НЕ.  Это
слово означает,  что интерпретатор языка проверяет условие "на-
оборот": когда символ на  ленте  не совпадает с указанным после
ключевого слова  ЕСЛИ (или ПОКА), условие считается выполненным
(истинным).
   Следующие допустимые условия связаны со сравнением символа в
оконной ячейке ленты с символом, расположенным в ящике:
   Я=Л - условие истинно, если символ в ящике  совпадает с сим-
         волом в оконной ячейке ленты;
   Я#Л - условие истинно, если символ  в  ящике  отличается  от
         символа в оконной ячейке ленты;
   Я>Л - условие истинно, если символ в ящике имеет больший по-
         рядковый номер в  алфавите Корректора  по  сравнению с
         символом в оконной ячейке ленты;
   Я<Л - условие истинно, если символ в ящике имеет меньший по-
         рядковый номер в  алфавите Корректора по  сравнению  с
         символом в оконной ячейке ленты.
   Наконец, в качестве условия можно использовать ключевое сло-
во ЦИФРА. Оно принимает истинное значение,  если  в  окошке  на
ленте записан любой из символов 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Пример программы.

   Задача. На ленте написано трехсимвольное слово,  и в началь-
ный момент окно установлено на его  начало. Написать программу,
которая меняет местами первый и последний символ слова.

                     ┬─┬─┬─╦═╦─┬─┬─┬─┬─┬
                     │░│░│░║к║о│т│░│░│░│
                     ┴─┴─┴─╩═╩─┴─┴─┴─┴─┴
Решение.

ЭТО Перевертыш
 // Поместить первый символ в ящик
 ЯЩИК+
 // Идти в конец слова
 ПОВТОРИ 2 ВПРАВО
 // Обменять местами символы в ящике и на ленте
 ОБМЕН
 // Идти в начало слова
 ПОВТОРИ 2 ВЛЕВО
 // Обменять местами символы в ящике и на ленте
 ОБМЕН
КОНЕЦ


2.6. Рекурсивные приемы программирования

   Исполнители  Кукарача  и Корректор не имеет средств в  своей
среде для выполнения непосредственных арифметических подсчетов.
   Однако, это  не означает, что программируя этих исполнителей,
нельзя "подсчитывать" их действия и использовать эти подсчеты в
программе. На помощь программисту приходит рекурсия!
   Рассмотрим следующую задачу для Кукарачи.

   Задача. (автор  Лилитко  Е.П.). Кукарача находится в верхней
строке поля. Где-то под ним (в том же столбце) расположена бук-
ва А. Требуется спуститься к букве (где бы  она ни находилась),
подвинуть ее один раз и вернуться к исходной  позиции в верхнюю
строку.  Сообщение  "Не могу" допускается только в том  случае,
если буквы А не оказалось под Кукарачей.

   Решение.
   Основная проблема  построения решения заключается в том, что
Кукарача должен вернуться в исходную позицию.  Кажется, что это
просто невозможно сделать.
   Однако, решение  этой  задачи  существует, и оно удивительно
короткое:

ЭТО Прогулка
  ВНИЗ
  ЕСЛИ НЕ А ТО Прогулка
  ВВЕРХ
КОНЕЦ

   На первый  взгляд  кажется,  что  программа неверна: команда
ВНИЗ, записанная последней, работает только один раз, и Кукара-
ча в общем случае не вернется в исходное положение на  поле. Но
это не так. Команда ВНИЗ сработает ровно столько же раз, сколь-
ко команда  ВВЕРХ, обеспечивая перемещение исполнителя в исход-
ную точку.
   Поясним ситуацию на примере начального состояния среды:

                1 2 3 4 5 6 7 8 9 10
               ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
             1 │ │ │ │¤│ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             2 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             3 │ │ │ │А│ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             4 │ │ │ │ │ │ │ │ │ │ │

   Отследим работу  программы  по шагам. Первой выполняется ко-
манда ВНИЗ:
                                          1 2 3 4 5 6 7 8 9 10
ЭТО Прогулка                             ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
  ┌─────┐                              1 │ │ │ │ │ │ │ │ │ │ │
  │ВНИЗ │                                ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
  └─────┘                              2 │ │ │ │¤│ │ │ │ │ │ │
   ЕСЛИ НЕ А ТО Прогулка                 ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
  ВВЕРХ                                3 │ │ │ │А│ │ │ │ │ │ │
КОНЕЦ                                    ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
                                       4 │ │ │ │ │ │ │ │ │ │ │

   Затем выполняется условная команда:
                                           1 2 3 4 5 6 7 8 9 10
ЭТО Прогулка                              ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
  ┌────┐                                1 │ │ │ │ │ │ │ │ │ │ │
  │ВНИЗ│                                  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
  └─┬──┘                                2 │ │ │ │¤│ │ │ │ │ │ │
  ┌─┴───────────────────┐                 ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
  │ЕСЛИ НЕ А ТО Прогулка│               3 │ │ │ │А│ │ │ │ │ │ │
  └─────────────────────┘                 ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
  ВВЕРХ                                 4 │ │ │ │ │ │ │ │ │ │ │
КОНЕЦ

   После выполнения условной команды должна выполняться  коман-
да, следующая за ней, то есть команда ВВЕРХ. Но условная коман-
да еще  не закончила свою  работу: так как условие истинно, вы-
полнится копия программы Прогулка:

ЭТО Прогулка
  ┌─────┐                                  1 2 3 4 5 6 7 8 9 10
  │ВНИЗ │                                 ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
  └──┬──┘                               1 │ │ │ │ │ │ │ │ │ │ │
     │                   ЭТО Прогулка     ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
  ┌──┴──────────────────┐  ┌──────┐     2 │ │ │ │ │ │ │ │ │ │ │
  │ЕСЛИ НЕ А ТО Прогулка├─>┤ ВНИЗ │       ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
  └─────────────────────┘  └──┬───┘     3 │ │ │ │¤│ │ │ │ │ │ │
  ВВЕРХ                       │           ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
КОНЕЦ                         │         4 │ │ │ │А│ │ │ │ │ │ │
                           ┌──┴──────────────────┐
                           │ЕСЛИ НЕ А ТО Прогулка│
                           └─────────────────────┘
                           ВВЕРХ
                         КОНЕЦ

   Теперь условие  ложно  и  выполнится  команда  ВВЕРХ в копии
программы Прогулка.

ЭТО Прогулка
  ┌─────┐                                  1 2 3 4 5 6 7 8 9 10
  │ВНИЗ │                                 ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
  └──┬──┘                               1 │ │ │ │ │ │ │ │ │ │ │
     │                   ЭТО Прогулка     ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
  ┌──┴──────────────────┐  ┌──────┐     2 │ │ │ │¤│ │ │ │ │ │ │
  │ЕСЛИ НЕ А ТО Прогулка├─>┤ ВНИЗ │       ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
  └─────────────────────┘  └──┬───┘     3 │ │ │ │ │ │ │ │ │ │ │
  ВВЕРХ                       │           ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
КОНЕЦ                         │         4 │ │ │ │А│ │ │ │ │ │ │
                           ┌──┴──────────────────┐
                           │ЕСЛИ НЕ А ТО Прогулка│
                           └──┬──────────────────┘
                           ┌──┴───┐
                           │ВВЕРХ │
                           └──────┘
                         КОНЕЦ

   Работа копии программы Прогулка завершена и,  тем самым, за-
вершилось  выполнение  условной  команды в оригинале.  Кукарача
приступает к  выполнению последней команды ВВЕРХ и возвращается
в исходное положение:

ЭТО Прогулка
  ┌─────┐                                  1 2 3 4 5 6 7 8 9 10
  │ВНИЗ │                                 ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
  └──┬──┘                               1 │ │ │ │¤│ │ │ │ │ │ │
     │                   ЭТО Прогулка     ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
  ┌──┴──────────────────┐  ┌──────┐     2 │ │ │ │ │ │ │ │ │ │ │
  │ЕСЛИ НЕ А ТО Прогулка├─>┤ ВНИЗ │       ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
  └─────────────────────┘  └──┬───┘     3 │ │ │ │ │ │ │ │ │ │ │
  ┌─────┐                     │           ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
  │ВВЕРХ│<────────┐           │         4 │ │ │ │А│ │ │ │ │ │ │
  └─────┘         │        ┌──┴──────────────────┐
КОНЕЦ             │        │ЕСЛИ НЕ А ТО Прогулка│
                  │        └──┬──────────────────┘
                  │        ┌──┴───┐
                  └────────┤ВВЕРХ │
                           └──────┘
                         КОНЕЦ

   Схемы довольно наглядно показывают, что рекурсия это не ана-
лог GOTO (переход  на начало). Рекурсивный вызов - это выполне-
ние копии  процедуры:  он может порождать "отложенные" команды,
которые начнут  выполняться  после  завершения рекурсии столько
раз, сколько было рекурсивных вызовов.
   Итак, рекурсия с "отложенными" командами - это довольно мощ-
ный инструмент программирования.
   Рассмотрим аналогичный пример в среде Корректора.

   Задача. На ленте записан текст  и  окно  установлено  где-то
внутри него. Требуется поставить в конце текста точку и вернуть
окно в исходное положение. Например, до начала работы лента мо-
жет выглядеть так:

         ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
         │░│░│░│░│я│ │-│ │р│о│б║о║т│░│░│░│░│░│░│░│░│░│
         ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴

   А после выполнения программы лента должна иметь вид:

         ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
         │░│░│░│░│я│ │-│ │р│о│б║о║т│.│░│░│░│░│░│░│░│░│
         ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴

 Решение.

ЭТО Точка
 ВПРАВО
 ЕСЛИ ПУСТО
  ТО ПИШИ .
  ИНАЧЕ Точка
 ВЛЕВО // Отложенная команда. Она  выполнится
       // столько раз, сколько раз выполнится
       // команда ВПРАВО.
КОНЕЦ


2.7. Подводные камни рекурсии

   Рекурсия порой очень сильно упрощает программирование, делая
текст программы удивительно коротким.
     Все же, по-прежнему,  основным  инструментом программиста
остается цикл  ПОКА. Эта управляющая структура нагляднее рекур-
сии, проще в использовании и часто  эффективнее при выполнении.
Поэтому, если задача решается при помощи цикла ПОКА, то не надо
стрелять из пушки по воробьям. Хотя,  конечно, маленькие рекур-
сивные безумства выглядят просто потрясающе.
   Сказанное совсем не означает, что рекурсия находится на зад-
ворках человеческой мысли. Рекурсия - безусловно  мощный и кра-
сивый инструмент  математики и, конечно, информатики. Часто ре-
курсивные описания  настолько легки и красивы, насколько тяжелы
и громоздки  попытки  обойтись  без этого аппарата. Посмотрите,
например, как  лаконично описывается при помощи рекурсии после-
довательность чисел Фибоначчи:

           f(1)  = 1, f(2)  = 1,
           f(n)  = f(n-1)+f(n-2) , для всех n > 2

            Напоминание о числах Фибоначчи
   Числа Фибоначчи определяются  следующей бесконечной последо-
вательностью целых чисел: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
   Каждый n-й элемент этой последовательности, начиная с треть-
его, равен сумме двух непосредственно предшествующих элементов.
Первые два члена последовательности равны единице.
   Эти числа  являются  решением  следующей задачи (итальянский
математик Фибоначчи сформулировал ее в 1202 году):
   "Каждый месяц самка из пары кроликов приносит двух детенышей
(самца и самку). Через два месяца новая самка сама приносит па-
ру кроликов.  Нужно найти число кроликов  в конце года,  если в
начале года была одна новорожденная пара, и в течение этого го-
да кролики не умирали."
   Ответ:  к  концу  года  число пар кроликов  достигнет  числа
f(12)=144, то есть,  поголовье  возрастет до 288 кроличьих еди-
ниц.
   Однако, надо  заметить,  что  на  практике такое размножение
кроликов  ни  к чему хорошему не приведет. Родственные  "браки"
повлекут быстрое вырождение потомства. Когда-то в детстве автор
разводил кроликов и, не имея соответствующего образования, при-
шел к этому  выводу на практике.  И потом, насколько  я  помню,
крольчихи вступают в половую  зрелость  не через 2 месяца после
рождения, а через три.  Последнее  замечание наводит на мысль о
новой задаче:  описать и построить последовательность для реше-
ния  задачи  о  кроликах  при условии, что кролики  вступают  в
"брак" через 3  месяца после рождения. Сколько кроликов будет в
крольчатнике к концу  года, если колония начала плодиться с од-
ной кроличьей пары?
   Заядлые крольчатники сделают еще одно замечание: очень редко
самка  приносит  только двух детенышей. Обычный приплод -  6-12
кроликов (однажды крольчиха подарила мне 18 ушастиков!). И кро-
ме того,  опытные  кролиководы  не позволяют самкам становиться
мамами более 4 раз в год. Это еще один повод  формулировать но-
вые рекурсивные задачи.

   Еще несколько примеров рекурсивных описаний.
1) Факториал.
              0! = 1
              n! = n*(n-1)!
2) Сумма последовательности.
    Пусть дана бесконечная последовательность чисел
               а1, a2, ..., an, ...
   Если обозначить через  S(n) - сумму n членов этой последова-
тельности, то
                 S(1) = a1
                 S(k) = S(k-1) + ak

3) Бинарное дерево.
        o - есть бинарное дерево (называемое пустым деревом);
        если b1 и b2 - бинарные деревья, то объект
                               o
                             /   \
                            b1    b2
        тоже является бинарным деревом.

 4) Решение задачи о ханойских башнях.
   Пусть H(n,  i, j, k) описывает  алгоритм переноса n  колец с
i-го стержня на j-ый,  используя  k-ый стержень как рабочий (i,
j, k принимают значения из множества {1, 2, 3} и различны между
собой).


Тогда:
                 H(1, i, j, k)   = i -> j

                                  | H(n-1, i, k, j)
                 H(n, i,  j, k) = | i -> j
                                  | H(n-1, k, j, i)

   Замечание.  Операция  -> введена  для  обозначения  переноса
кольца с одного  стержень на другой.  Например, запись 1  ->  3
обозначает перенос кольца с первого стержня на третий.

   Однако, использование рекурсии таит в себе подводные камни.

   Первый. Использовать  рекурсию  разумнее  всего тогда, когда
природа задачи  сама по себе рекурсивна. Искусственно построен-
ная рекурсия  (как  альтернатива циклу) редко бывает оправдана.
Например,  для суммирования  членов  последовательности,  лучше
применить цикл, а  не рекурсию. В чем заключается опасность ре-
курсии при машинных вычислениях? Дело в том, что при каждом ре-
курсивном вызове расходуется дополнительно часть машинной памя-
ти (в ней сохраняется адрес  возврата  и  локальные  переменные
процедуры, если язык допускает  использование  переменных). При
"глубоких" рекурсивных вызовах вся доступная память  компьютера
может быстро исчерпаться.
   Но даже в некоторых естественно-рекурсивных задачах рекурсию
использовать не  всегда  разумно. В качестве примера рассмотрим
упоминаемую выше последовательность чисел Фибоначчи.
   Каждое обращение к f(n) при n > 2 приводит к  двум рекурсив-
ным обращениям.  Посмотрите,  как  быстро  растет число вызовов
процедуры f при рекурсивном вычислении чисел Фибоначчи:
                                 f
                  ┌──────────────┴───────────────┐
2         ┌───────f────────┐             ┌───────f────────┐
4     ┌───f────┐      ┌────f───┐     ┌───f────┐       ┌───f───┐
8   ┌─f─┐    ┌─f─┐  ┌─f─┐    ┌─f─┐ ┌─f─┐    ┌─f─┐   ┌─f─┐   ┌─f─┐
16  f   f    f   f  f   f    f   f f   f    f   f   f   f   f   f

   Число рекурсивных вызовов растет как степень двойки, то есть
так же быстро, как размножаются кролики!
   Числа Фибоначчи лучше вычислять при помощи цикла ПОКА:

    ЭТО f(n)
     i:= 1          // i - счетчик чисел Фибоначчи
     x:= 1          // x - сумматор
     y:= 0          // y - вспомогательная переменная
     ПОКА i < n
     {
       x:= x + y    // суммируем два предыдущих значения
       y:= x - y    // первое из них запоминаем в y
       i:= i + 1
     }
    ВЕРНУТЬ x
    КОНЕЦ

   Второй.  Использовать  рекурсию  как замену отсутствующей  в
языке конструкции  GOTO  еще  вреднее, чем использование самого
GOTO. Рассматривать  рекурсию  как  переход  в начало процедуры
неправильно: ведь рекурсия  это  не переход, а выполнение копии
процедуры; выполнение без всякого перехода, в  том самом месте,
где стоит рекурсивный вызов.

   Третий. Прямая  рекурсия всегда предпочтительнее  косвенной.
Косвенная рекурсия - это замаскированная форма прямой, а всякая
маскировка действий ухудшает как проектирование программы,  так
и ее  отладку, не говоря уже  о попытках разобраться  в текстах
программы постороннему глазу (и даже глазу автора программы че-
рез неделю после написания текста).
