ДРоботландский Университет 
2000/2001 учебный год
Курс 31 "Азы программирования"
-------------------------------------------------
     Р О Б О Т Л А Н Д С К О Е  П Р О Г Р А М М И Р О В А Н И Е

                                   (C) А.А. Дуванов

                                      Под редакцией
                                      Ю.А. Первина

                                      Пособие   распространяется
                                      только в рамках  Роботлан-
                                      дских  Курсов  и  является
                                      объектом авторского права.

Глава 6. Кукарача хочет укусить себя за хвост

6.1. Разговор о рекурсии
   Петя. Вот тебе, Вася, листочек с рисунком среды и программой.
Как Кукарача будет выполнять эту программу?
                 ┌─────────────────────────┐
                 │    1 2 3 4 5 6 7 8 9 10 │
                 │   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ │
                 │ 1 │#│ │ │ │ │ │ │ │ │ │ │
                 │   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤ │
                 │ 2 │ │ │ │ │ │ │ │ │ │ │ │
                 │   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤ │
                 │                         │
                 │   ЭТО До_упора          │
                 │    ВПРАВО               │
                 │    До_упора             │
                 │   КОНЕЦ                 │
                 └─────────────────────────┘

   Вася.  Очень  странная  программа,  она кусает сама  себя  за
хвост!
   Петя. Это все, что ты можешь сказать?
   Вася. Сейчас я  попробую выполнить ее за Кукарачу. Первая ко-
манда ВПРАВО.  Перемещаюсь  в  клетку  (1,2).  Следующая команда
До_упора. Укус за хвост!  Программа  вызывает саму себя. Что де-
лать?
   Петя. Исполняй!
   Вася. Хорошо. Команда До_упора состоит из двух команд. Снача-
ла команда ВПРАВО. Кукарача смещается в клетку (1,3). Потом сно-
ва команда До_упора! Все повторяется сначала.
   Петя. Что же произойдет в итоге?
   Вася. Кукарача будет все время смещаться вправо, пока... пока
не остановится у края поля, умоляя: "Не могу"!
   Петя. Такая  программа называется РЕКУРСИВНОЙ. Рекурсия - это
способ программирования, при котором программа вызывает сама се-
бя. Если бы доска не имела границы (скажем, была бы  склеена на-
подобие цилиндра), Кукарача, выполняя программу До_упора, никог-
да бы не остановился. Такая рекурсия называется БЕСКОНЕЧНОЙ.
   А вот пример КОНЕЧНОЙ рекурсии.

     Задача 1. Найти и выбросить с поля букву "А".

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

   Решение состоит из  двух частей: поиска буквы "А" среди пере-
вернутых кубиков во второй строке и  выбрасывании найденного ку-
бика с поля.

       ЭТО А
        Поиск_А
        Выброс_А
       КОНЕЦ

   Поиск будем  делать  так. Толкаем кубик, он переворачивается.
Если на кубике обнаружена буква "А", поиск закончен. В противном
случае продвигаемся  вперед  и  начинаем все сначала (рекурсия):
толкаем кубик, выполняем проверку и так далее, пока  кубик с "А"
не будет найден.
             ЭТО Поиск_А   ──┐
              ВНИЗ            │
              ЕСЛИ НЕ А       │
                ТО Шаг───┐    │
             КОНЕЦ       │    │      Косвенная рекурсия
                         │    │
             ЭТО Шаг   ─┘    │
              ВВЕРХ           │
              ВПРАВО          │
              Поиск_А ────────┘
             КОНЕЦ

             ЭТО Выброс_А
              ПОВТОРИ 8 ВНИЗ
             КОНЕЦ

   Рекурсия кончается,  когда  будет  найдена  буква  А. Однако,
программа Поиск_А не  сама вызывает себя, а через программу Шаг.
Поиск_А вызывает  программу  Шаг,  программа  Шаг снова вызывает
программу Поиск_А и так далее.
   Такая рекурсия,  при  которой  программа  вызывает себя через
другую программу, называется КОСВЕННОЙ.

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

                    "Литературная" бесконечная рекурсия
┌────────────────────────┐
│ У попа была собака,    │                  ЭТО  Стишок
│ Он ее любил.           │  Основная          Основная_часть
│ Она съела кусок мяса - │  часть             Стишок
│ Он ее убил.            │                  КОНЕЦ
│ Убил и закопал.        │
│ И надпись написал:     │
└────────────────────────┘
       У попа была собака,
       Он ее любил...

                    "Телевизионная" бесконечная рекурсия

 ┌─────────────────────────────┐            ЭТО Рисунок
 │Телезритель, который видит в │Основная       Основная_часть
 │телевизоре ...               │часть          Уменьши_размеры
 └─────────────────────────────┘               Рисунок
  телезрителя,                              КОНЕЦ
  который видит в телевизоре...

                   Конечная косвенная рекурсия
   Алгоритм наполнения бочки с водой:
           ЭТО Налей_бочку
             ЕСЛИ бочка не полна
               ТО Наливай
           КОНЕЦ

           ЭТО Наливай
             НАЛЕЙ_СТАКАН
             Налей_бочку
           КОНЕЦ
   (Программа составлена для исполнителя,  который  умеет выпол-
нять команду НАЛЕЙ_СТАКАН и проверять условие "бочка не полна")
   В этом примере можно легко написать и нерекурсивный алгоритм:
           ЭТО Налей_бочку
             ПОКА бочка не полна НАЛЕЙ_СТАКАН
           КОНЕЦ
   Нерекурсивный алгоритм здесь даже предпочтительнее, поскольку
он проще.

6.2. Рекурсивный  практикум
   Вася. Все, что ты мне рассказал вроде бы понятно, но уж очень
непривычно.
   Петя. Давай порешаем еще задачи.  К  рекурсии,  ты прав, надо
привыкнуть.
   Задача 2. Проведите  Кукарачу по диагонали до буквы К. Распо-
ложение   буквы    К   на   диагонали   заранее   не   известно.
(<<task601.coc>>)
                    1 2 3 4 5 6 7 8 9 1
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
                 1 │#┼┐│ │ │ │ │ │ │ │ │
                   ├─┼┼┼─┼─┼─┼─┼─┼─┼─┼─┤
                 2 │ │└┼┐│ │ │ │ │ │ │ │
                   ├─┼─┼┼┼─┼─┼─┼─┼─┼─┼─┤
                 3 │ │ │└┼┐│ │ │ │ │ │ │
                   ├─┼─┼─┼┼┼─┼─┼─┼─┼─┼─┤
                 4 │ │ │ │└┼┐│ │ │ │ │ │
                   ├─┼─┼─┼─┼┼┼─┼─┼─┼─┼─┤
                 5 │ │ │ │ │└┼┐│ │ │ │ │
                   ├─┼─┼─┼─┼─┼┼┼─┼─┼─┼─┤
                 6 │ │ │ │ │ │└┼┐│ │ │ │
                   ├─┼─┼─┼─┼─┼─┼┼┼─┼─┼─┤
                 7 │ │ │ │ │ │ │К│ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
                 8 │ │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
                 9 │ │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
                 10│ │ │ │ │ │ │ │ │ │ │
                   └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘

   Вася. Эту задачу  можно легко решить при помощи команды ПОКА:
нужно шагать по диагонали, пока не встретится буква К.

    ЭТО Поиск_К
      Шаг
      ПОКА НЕ К Шаг
    КОНЕЦ

    ЭТО Шаг
     ВПРАВО
     ВНИЗ
    КОНЕЦ

   Петя. Верно! А теперь попробуй обойтись без ПОКА, написав ре-
курсивный вариант.
   Вася. Попробую.

        ЭТО Поиск_К
          Шаг
          ЕСЛИ НЕ К
            ТО Поиск_К
        КОНЕЦ

        ЭТО Шаг
          ВПРАВО
          ВНИЗ
        КОНЕЦ

   Петя. Ну вот, видишь, у тебя получилось! Следующая задача, ко-
торую я хочу  предложить тебе, похожа  на предыдущую, но  в  ней
есть одно тонкое место.

            3. Головоломное программирование

     Задача 3. (автор  Лилитко  Е.П.). Кукарача находится в вер-
хней строке поля. Где-то под ним (в том же столбце) расположена
буква А.  Требуется спуститься к букве  (где бы она  ни находи-
лась), подвинуть  ее один раз  и вернуться к исходной позиции в
верхнюю  строку.  Сообщение "Не могу" допускается только в  том
случае, если буквы А не оказалось под Кукарачей.
   Вася. Я думаю тонкость заключается в том, что Кукарача должен
вернуться в исходную позицию.
   Петя. Да, ты правильно подметил отличие. Ну и как бы ты напи-
сал решение для этой задачи?
   Вася. Я совершенно не  понимаю,  как вернуть Кукарачу к месту
старта.  Ведь  он должен запомнить, на сколько клеток  спустился
вниз, чтобы  повторить столько же шагов  вверх. Но как  это сде-
лать? Я думаю, что у задачи нет решения.
   Петя. Ты ошибаешься. Вот решение задачи  и,  как  ты  видишь,
очень короткое:
                     ЭТО Прогулка
                       ВНИЗ
                       ЕСЛИ НЕ А
                         ТО Прогулка
                       ВВЕРХ
                     КОНЕЦ
   Вася. Короткое-то,  короткое,  но не очень понятное. Кукарача
найдет букву А и по такой программе:

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

   Твоя программа  отличается  от  моей  только  одной командой
ВВЕРХ. Значит,  выполняя  твою программу, Кукарача найдет букву
А, после чего поднимется на одну клетку вверх. Ясно, что  в об-
щем случае это будет неверное решение. Вот, например, для тако-
го положения Кукарачи и буквы А:
                1 2 3 4 5 6 7 8 9 10
               ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
             1 │ │ │ │#│ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             2 │ │ │ │ │ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             3 │ │ │ │А│ │ │ │ │ │ │
               ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
             4 │ │ │ │ │ │ │ │ │ │ │
нужно для возврата к старту сделать не один шаг вверх, а два.

   Петя. Хорошо, давай проверим мое решение.

   Вася установил Кукарачу и букву,  как  на  рисунке, набрал на
компьютере программу Пети  и  после запуска с удивлением обнару-
жил, что Кукарача, выполнив  работу,  вернулся в клетку (1,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 │ │ │ │А│ │ │ │ │ │ │
  │ВВЕРХ│<───────┐    │ЕСЛИ НЕ А     │
  └─────┘        │    │  ТО Прогулка │
КОНЕЦ            │    └──┬───────────┘
                 │       │
                 │    ┌──┴──┐
                 └────┤ВВЕРХ│
                      └─────┘
                    КОНЕЦ

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


Вопросы и задания
  1. На одном из перевернутых  кубиков  (не на первом!) - буква
"И". Найдите ее и составьте слово  ТИГР.  Используйте  кубик  с
буквой "М" для определения положения Кукарачи.
(<<task602.coc>>)

              1  2  3  4  5  6  7  8  9  10
             ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
           1 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           2 │# │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           3 │? │? │? │? │? │? │? │? │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           4 │  │  │  │  │  │  │  │  │  │М │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           5 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           6 │  │  │  │  │  │Т │  │Г │Р │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           7 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           8 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           9 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
          10 │  │  │  │  │  │  │  │  │  │  │
             └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘

     2. Исполнитель располагается  в  левом  верхнем углу поля.
Кубики с буквами стоят ниже него по одному в каждом столбце (их
расположение в столбце произвольно, но не  выше второй строки).
Написать программу, которая  перемещает  все эти кубики на одну
строку ниже. (<<task603.coc>>)
              1  2  3  4  5  6  7  8  9  10
             ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
           1 │# │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           2 │Ж │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           3 │  │Ж │  │Ж │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           4 │  │  │Ж │  │Ж │  │  │  │  │Ж │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           5 │  │  │  │  │  │Ж │  │  │Ж │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           6 │  │  │  │  │  │  │Ж │Ж │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           7 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           8 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           9 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
          10 │  │  │  │  │  │  │  │  │  │  │
             └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘

     3. Исполнитель располагается  в  клетке  (2,2) поля внутри
коридора неизвестной длины. Внизу коридора нижняя стенка слома-
на. Починить коридор  и  вернуть исполнителя в исходное положе-
ние. (<<task604.coc>>)

              1  2  3  4  5  6  7  8  9  10
             ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
           1 │  │  │Ж │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           2 │Ж │# │  │Ж │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           3 │  │Ж │  │  │Ж │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           4 │  │  │Ж │  │  │Ж │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           5 │  │  │  │Ж │  │  │Ж │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           6 │  │  │  │  │Ж │  │  │Ж │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           7 │  │  │  │  │  │Ж │  │  │Ж │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           8 │  │  │  │  │  │  │Ж │Ж │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           9 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
          10 │  │  │  │  │  │  │  │  │  │  │
             └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘

     4. Исполнитель находится  в  левом верхнем углу. Во второй
строке, начиная с первой  позиции  записано слово не длиннее 7
символов. Поставить Кукарачу в строку, номер которой равен дли-
не этого слова. (<<task605.coc>>)
              1  2  3  4  5  6  7  8  9  10
             ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
           1 │# │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           2 │к │о │р │о │в │а │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤
           3 │  │  │  │  │  │  │  │  │  │  │
             ├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤

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

     6. (автор Лилитко Е.П.). Требуется построить нового  испол-
нителя, "управляемого  данными",  поведение  которого будет пол-
ностью зависеть от расположения букв  на  поле,  а именно: Изна-
чально Кукарача движется вниз до тех пор, пока  не встретит одну
из букв "В", "Н", "Л", "П"  или "С". Встретив одну из этих букв,
он продолжает движение соответственно "вверх", "вниз",  "влево",
"вправо" или  немедленно останавливается. На дальнейшем пути Ку-
карачи может вновь повстречаться одна  из  приведенных  букв,  и
тогда он  вновь изменяет направление вышеописанным способом. Для
нового исполнителя создайте программу (установите в нужные места
буквы-команды и  Кукарачу),  заставляцщую ходить его по расширя-
ющейся спирали. (<<task607.coc>>)

     7. Кукарача расположен в нижнем левом углу поля. Прямо над
ним в расположена строка из букв Г, заканчивающаяся знаком "-".
Буквы Г начинаются с первого столбца и их не больше семи. Напи-
сать программу, выполняя которую Кукарача построит лесенку (как
на рисунке) и  после завершения своих трудов остановится в пра-
вом верхнем углу поля. (<<task608.coc>>)

   1 2 3 4 5 6 7 8 9 10         1 2 3 4 5 6 7 8 9 10
  ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐        ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
1 │ │ │ │ │ │ │ │ │ │ │      1 │ │ │ │ │ │ │ │ │ │#│
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤        ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
2 │ │ │ │ │ │ │ │ │ │ │      2 │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤        ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
3 │ │ │ │ │ │ │ │ │ │ │      3 │ │ │ │ │ │ │-│ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤        ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
4 │ │ │ │ │ │ │ │ │ │ │      4 │ │ │ │ │ │Г│ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤        ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
5 │ │ │ │ │ │ │ │ │ │ │ ──>  5 │ │ │ │ │Г│ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤        ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
6 │ │ │ │ │ │ │ │ │ │ │      6 │ │ │ │Г│ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤        ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
7 │ │ │ │ │ │ │ │ │ │ │      7 │ │ │Г│ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤        ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
8 │ │ │ │ │ │ │ │ │ │ │      8 │ │Г│ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤        ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
9 │Г│Г│Г│Г│Г│Г│Г│-│ │ │      9 │Г│ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤        ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
10│#│ │ │ │ │ │ │ │ │ │      10│ │ │ │ │ │ │ │ │ │ │
  └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘        └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘

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

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

