4.2. Решения и комментарии

                      История Кукарачи
   Исполнитель Кукарача (первое имя Таракан) родился на Дальнем
Востоке в 1984 году. Роботландии тогда еще не было, а был ново-
сибирский  Муравей,  придуманный  Г.А.Звенигородским  вместе  с
группой исследователей (в нее входил и  Ю.А.Первин, будущий ди-
ректор Роботландии).
   Второй участник грядущей Роботландии, А.А.Дуванов, в то время
работал преподавателем  в Благовещенском пединституте.  Интерес
благовещенцев к пионерским работам новосибирцев был  достаточно
велик. Настолько, что Дальний Восток приехал в Сибирь пообщать-
ся с умными людьми, увидеть  уникальную  работу  школьников  на
компьютерах  своими  глазами.  По трагическому стечению  обсто-
ятельств как раз в это время от обычного гриппа умер Г.А.Звени-
городский. Ему  было 32 года. Он  даже не увидел  издание своей
книги, которая  вышла уже после его смерти (Г.А.Звенигородский.
Первые уроки  программирования.  Библиотечка  Квант. Выпуск 41.
Москва. Наука. 1985).
   Разговор состоялся с Юрием Абрамовичем Первиным. Был показан
школьный  урок  в младших классах за компьютерами "Агат".  Была
подробная содержательная  беседа  о новосибирском опыте, в час-
тности, об исполнителе Муравей.
   В Благовещенске закипела работа. В группу энтузиастов, кото-
рую возглавил А.А.Дуванов, вошли: О.Г.Какакулин, В.В.Немилости-
ва, Ю.В.Прашкович, О.Д.Десятириков.
   Появилась идея: взяв за основу среду  Муравья, придумать та-
кую ее модификацию и такой учебный язык программирования, кото-
рые, с одной стороны, были бы предельно просты и доступны самым
маленьким, а, с другой - предельно полны, и  позволили бы пред-
ставить все основные управляющие структуры.
   Так появился Таракан, который позже, после поездки А.А.Дува-
нова на Кубу, был переименован в Кукарачу.
   Заканчивая краткий исторический обзор насекомых от  програм-
мирования, можно сказать,  что России их не хватало. Тараканы и
Муравьи начали свой победный марш по нашим широким просторам. В
качестве примера  можно  указать  самарскую работу: Г.Н.Гутман,
О.М.Карпилова. Муравьиные сказки. Книга  для  учащихся. Москва.
Просвещение. 1993.
   Самарский Муравей больше  походит  на Кукарачу (хотя в книге
ссылки на роботландского исполнителя нет), чем  на своего ново-
сибирского однофамильца. Однако, кукарачинский  язык  в Самаре,
на наш  взгляд, неоправданно усложнен введением переменных, пе-
речисляемым циклом,  подпрограммой  с параметрами и другими до-
полнениями,  которые,  с одной стороны, сводят на нет  первона-
чальную простоту, а  с другой - плохо вписываются в примитивную
клетчатую среду и СКИ исполнителя.
   Правда, у самарского Муравья хорошая возможность  редактиро-
вания среды:  наряду с кубиками-символами можно расставлять ку-
бики-картинки и создавать общий фон-картинку в среде исполните-
ля.
   Кукарача вошел в  состав  курса Роботландии с самого начала.
Алгоритмические структуры по своей сути - вещь житейская, обще-
образовательная и  необходимая  для  изучения  именно в младших
классах, когда  формируется  стиль мышления ребенка. Именно по-
этому, а не с целью  подготовки  юных  программистов,  Кукарача
внедрился в общеобразовательные школы. Среда, понятная ребенку,
предельно простая СКИ и структурный процедурный  язык (без вся-
ких GOTO) адекватно соответствовали поставленной задаче.
   Однако, исполнитель имел недостатки, по поводу которых неод-
нократно высказывался  Я.Н.Зайдельман  - еще один активный член
коллектива, один из авторов Роботландии.
   В частности, Яков Наумович говорил, что исполнитель плох по-
тому, что алгоритмы, записанные для него, не обладают свойством
массовости. Исполнитель работает с единственным набором входных
данных  (начальным  расположением кубиков на поле), в то  время
как "настоящие"  алгоритмы пишутся для целого класса однотипных
задач.
   Соглашаясь с этим недостатком, А.А.Дуванов доказывал, что он
не так важен для поставленных целей:  привить ребенку структур-
ный (ниспадающий) подход  к решению задачи и показать ему прин-
ципы работы основных управляющих  конструкций  (процедура, вет-
вление, цикл).
   Споры  были  долги и безутешны. В настоящий момент  Кукарача
испытывает  новый  подъем.  Проклятие "массовости" снято  целым
фейерверком принципиально новых  задач. Первотолчком, закрутив-
шим Кукарачу на новых оборотах, стали задачи Е.П.Лилитко, кото-
рые он придумал для своей дочки и любезно  передал нам: большая
их часть вошла  в  материалы сетевой роботландской Олимпиады 97
года. Потом было много других задач, неожиданно радостных нахо-
док.
   Многие задачи из книги, по  которой  работали  участники  на
Курсах, и  задачи  турнира  (кроме  первой) безусловно обладают
свойством  массовости.  Программа  создается не для  конкретной
конфигурации кубиков на поле, а для целого класса возможных ус-
тановок. Еще  более  важным  (и, соответственно, приближенным к
реалиям программистской практики) становится процесс тестирова-
ния программ.
   (В скобках можно заметить, что первоначально язык Кукарачи не
содержал составную  команду. Предполагалось, что она будет про-
воцировать неструктурный стиль  программирования. Однако, такое
"насильственное" структурирование, когда для любых действий Ку-
карачи, не вмещающихся  в  одну команду СКИ, приходилось писать
отдельную процедуру,  вызвало бурный протест Якова Наумовича, и
автор Кукарачи ввел в язык составную команду. Итоги турнира по-
казали, что с  одной стороны опасения "провокации" были не нап-
расны,  но  не столь уж серьезны: большинство детских  программ
спроектированы довольно грамотно. В этом, конечно, большая зас-
луга учителей, руководителей команд. По поводу составной коман-
ды, как способа  избавления  от маленьких, не улучшающих струк-
турность программы конструкций, у Якова Наумовича есть дополни-
тельные возражения, но это тема для отдельного разговора.)
   Почти  все  руководители отмечали  азарт  детей  и  даже  их
"злость" на упорную  задачу.  Ну и, понятно, огромное моральное
удовлетворение, когда задача,  наконец, поддалась человеческому
разуму и "раскололась"  как орех. Это чувство всем нам знакомо,
и оно дорого  стоит для самоутверждения. Тем более, для самоут-
верждения ребенка,  которому так полезно испытывать трудности и
учиться их преодолевать.
   В приведенном  ниже анализе приводятся полные тексты "образ-
цовых" программ даже  тогда, когда это не обязательно для пони-
мания идеи автора.
   Автор сборника  позволил себе кое-где подправить внешний вид
программ участников  (добавить  структурные отступы, там где их
не было,  заменить  имена  процедур, записанных одними большими
буквами...). Все это "шлифовочное" редактирование было  сделано
для улучшения  читаемости программы и, соответственно, ее пони-
маемости. С этой же целью были  внесены микроскопические правки
в тексты участников, описывающих алгоритмы.

     Задача 1.

   Эта  задача  - самая простая в конкурсе.  Ее  особенность  -
единственная конфигурация начального состояния среды исполните-
ля, заданная в  условии задачи. Вообще говоря, эту задачу можно
решить  только  командами  из  СКИ исполнителя, не  прибегая  к
структурам языка программирования.  Однако, предполагалось, что
хорошее решение использует свойство повторения частей предпола-
гаемой траектории  движения  исполнителя,  и программа содержит
соответствующие процедуры и циклы.
   Вот как решил эту задачу Гуреев Денис из  команды 05, г.Сне-
жинска:
   Описание алгоритма. В программе Прогулка используются проце-
дуры Дуга1 и Дуга2 для повторения одинаковых действий.

ЭТО Прогулка
 ПОВТОРИ 2 Дуга1
 ПОВТОРИ 9 ВПРАВО
 ПОВТОРИ 2 Дуга2
 ВВЕРХ
КОНЕЦ

ЭТО Дуга1
 ПОВТОРИ 3 ВПРАВО
 ПОВТОРИ 2 ВНИЗ
 ПОВТОРИ 3 ВЛЕВО
 ПОВТОРИ 2 ВНИЗ
КОНЕЦ

ЭТО Дуга2
 ПОВТОРИ 2 ВВЕРХ
 ПОВТОРИ 3 ВЛЕВО
 ПОВТОРИ 2 ВВЕРХ
 ПОВТОРИ 3 ВПРАВО
КОНЕЦ

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

   Неожиданное решение этой задачи мы нашли в пакете той же ко-
манды 05. Хитрый Игорь Мурдасов решил "поднырнуть" под основное
поле и  привести исполнителя к цели  без всяких помех.  Вот его
решение.
   Описание алгоритма.  В  программе  я  (Игорь Мурдасов) решил
"придраться" к  условию.  Зачем  проходить  лабиринт, если есть
второе поле?

ЭТО Работа
 ВПЕРЕД
 ПОВТОРИ 9 ВПРАВО
 ВВЕРХ
 НАЗАД
КОНЕЦ                                  

   Мы предполагали в первых семи задачах  "плоские" решение, но
так как  это не было явно  оговорено в условиях,  решение Игоря
имеет право  на  существование.

   Задача 2.

   Задача решается  при  помощи  цикла ПОВТОРИ и переключателя,
который вызывает одну из 8 процедур для обработки цифр 3, 4, 5,
6, 7, 8, 9 и пробела.
   Образцом идеального решения можно считать программу  Дубини-
ной Кати и Липиной Насти из  команды  13  г.Иркутска.  Обратите
внимание, как  изящно  решена  проблема  десятого столбца. Ведь
после  установки  цифры в нем смещаться вправо  уже  нельзя  (в
стандартном поле 10x10 это приведет к отказу "Не могу")!

Описание алгоритма.
   Программа разбита на две части:
   - 9 раз  повторяем  выполнение процедуры Работа со смещением
вправо;
   - один раз выполняем процедуру Работа для  10-го столбца без
смещения в следующий столбец.
   Процедура Работа содержит переключатель для установки  цифры
в нужную строку и  возврата  исполнителя в исходное положение в
первой строке.

ЭТО Цифры_на_место
 ПОВТОРИ 9 { Работа ВПРАВО }
 Работа
КОНЕЦ                                  

ЭТО Работа
  ВНИЗ
  ЕСЛИ ПУСТО ТО ВВЕРХ
  ИНАЧЕ ЕСЛИ 3 ТО Цифра_3
  ИНАЧЕ ЕСЛИ 4 ТО Цифра_4
  ИНАЧЕ ЕСЛИ 5 ТО Цифра_5              
  ИНАЧЕ ЕСЛИ 6 ТО Цифра_6
  ИНАЧЕ ЕСЛИ 7 ТО Цифра_7
  ИНАЧЕ ЕСЛИ 8 ТО Цифра_8
  ИНАЧЕ ЕСЛИ 9 ТО Цифра_9
КОНЕЦ

ЭТО Цифра_3
  ВВЕРХ                                
КОНЕЦ                                  

ЭТО Цифра_4
 ВНИЗ
 ПОВТОРИ 2 ВВЕРХ
КОНЕЦ

ЭТО Цифра_5
 ПОВТОРИ 2 ВНИЗ                        
 ПОВТОРИ 3 ВВЕРХ                       
КОНЕЦ

ЭТО Цифра_6
 ПОВТОРИ 3 ВНИЗ
 ПОВТОРИ 4 ВВЕРХ                       
КОНЕЦ

ЭТО Цифра_7
 ПОВТОРИ 4 ВНИЗ                        
 ПОВТОРИ 5 ВВЕРХ
КОНЕЦ

ЭТО Цифра_8
 ПОВТОРИ 5 ВНИЗ
 ПОВТОРИ 6 ВВЕРХ
КОНЕЦ

ЭТО Цифра_9                            
 ПОВТОРИ 6 ВНИЗ                        
 ПОВТОРИ 7 ВВЕРХ                       
КОНЕЦ


   Задача 3.

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

ЭТО Сложение
 // Поиск знака +
 ВВЕРХ
 ПОКА НЕ + Поиск                       
 // Удаление знака + с поля
 ВВЕРХ
 ВНИЗ                                  
 // Поиск конца примера
 Поиск
 ПОКА НЕ ПУСТО Поиск
 // Уплотнение записи
 ВВЕРХ                                 
 ВЛЕВО                                 
КОНЕЦ                                  

ЭТО Поиск
 ВНИЗ
 ВПРАВО                                
 ВВЕРХ                                 
КОНЕЦ                                  

   Заметьте, что  программа  правильно  обрабатывает и сложение
нулевых палочных чисел:
                 1)   ||||+   т.е., 4+0
                 2)   +||||   т.е., 0+4
                 3)   +       т.е., 0+0


     Задача 4.

   Можно предложить несколько алгоритмов решения этой задачи.

   1) Убирать поочередно палочки слева и справа в записи приме-
ра до тех пор, пока справа они не  закончатся. Оставшееся число
палочек на поле изобразит результат.
   2) Сначала  палочки,  изображающие вычитаемое  поместить под
палочками, изображающие уменьшаемое:

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

   Затем "очистить"  столбцы, содержащие парные  (расположенные
друг под другом) палочки.

   3) Удалить с поля палочки, составляющие вычитаемое. При выб-
росе каждой  палочки  "запомнить"  при помощи отложенных команд
(расположенных за  рекурсивным  вызовом)  число выбросов (число
палочек в вычитаемом). Отложенные команды должны быть спроекти-
рованы так, чтобы каждое  их  выполнение убирало одну палочку в
уменьшаемом.  Тогда,  после  завершения рекурсии в  уменьшаемом
убирается столько палочек, сколько их было в вычитаемом.
   4) Модификации алгоритма 3. Алгоритм  3  допускает несколько
непринципиальных модификаций, например,  такую: запомнить число
палочек в  вычитаемом,  используя при "подсчете" механизм отло-
женных команд. Затем  "слить"  два числа (уменьшаемое и вычита-
емое) в одно. Отложенная группа команд должна быть такой, чтобы
обеспечить сокращение числа на две палочки.

   Скочилов Роман  (команда 05, г.Снежинск) построил свое реше-
ние по алгоритму 4). Вот его решение.
   Описание алгоритма. В процедуре Вычитание Кукарача с помощью
команды ПОКА ищет знак "-", выталкивает его с  поля и переходит
к выполнению  процедуры Вычитаемое. Эта процедура проверяет ку-
бики-палочки и для каждой из них оставляет невыполненной коман-
ду ПОВТОРИ 2  ВЛЕВО в процедуре Запомни. Эти отложенные команды
начинают работать,  когда Кукарача обнаружит конец примера. Они
сбросят с поля нужное число лишних палочек.

ЭТО Вычитание
 ВВЕРХ ПОКА НЕ - Дальше
 ПОВТОРИ 2 ВВЕРХ
 ПОВТОРИ 3 ВНИЗ
 ВПРАВО
 Вычитаемое
КОНЕЦ

ЭТО Дальше
 ВНИЗ
 ВПРАВО
 ВВЕРХ
КОНЕЦ

ЭТО Вычитаемое
 ВВЕРХ
 ЕСЛИ |
   ТО    Запомни
   ИНАЧЕ { ВВЕРХ ПОВТОРИ 2 ВЛЕВО }
КОНЕЦ

ЭТО Запомни
 ВНИЗ
 ВПРАВО
 Вычитаемое
 ПОВТОРИ 2 ВЛЕВО
КОНЕЦ                 


   Калинин Игорь из команды 32 г.Находки  построил свое решение
по схеме алгоритма 1).

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

ЭТО Вычитание
 До_минуса
 Минус1
КОНЕЦ

ЭТО До_минуса
 ВВЕРХ
 ПОКА НЕ -
 {
   ВНИЗ
   ВПРАВО
   ВВЕРХ
 }
 ПОВТОРИ 2 ВВЕРХ
 ПОВТОРИ 3 ВНИЗ
КОНЕЦ

ЭТО Минус1
 ВПРАВО
 ВВЕРХ
 ЕСЛИ НЕ ПУСТО ТО
 {
   ПОВТОРИ 2 ВВЕРХ
   ПОВТОРИ 3 ВНИЗ
   ПОВТОРИ 2 ВЛЕВО
   ПОВТОРИ 3 ВВЕРХ
   ПОВТОРИ 3 ВНИЗ
   ПОВТОРИ 3 ВПРАВО
 }
 ВВЕРХ
 ЕСЛИ НЕ ПУСТО ТО Минус2
КОНЕЦ

ЭТО Минус2
 ПОВТОРИ 2 ВВЕРХ
 ПОВТОРИ 3 ВНИЗ
 ПОВТОРИ 4 ВЛЕВО
 ПОВТОРИ 3 ВВЕРХ
 ПОВТОРИ 3 ВНИЗ
 ПОВТОРИ 5 ВПРАВО
 ВВЕРХ
 ЕСЛИ НЕ ПУСТО ТО Минус3
КОНЕЦ

ЭТО Минус3
 ПОВТОРИ 2 ВВЕРХ
 ПОВТОРИ 3 ВНИЗ
 ПОВТОРИ 6 ВЛЕВО
 ПОВТОРИ 3 ВВЕРХ
КОНЕЦ

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

   Ялышев Влад (команда 09, г.Пермь) использовал  в своей прог-
рамме описанный выше алгоритм 2).

   Описание алгоритма. Алгоритм вычитает числа "столбиком".
   1. Найти знак  "-" в строке символов, "поднимая" уменьшаемое
на строчку вверх.
   2. Вытолкнуть "-" с рабочего поля.
   3. Переместиться на конец примера.
   4. Найти  конец  вычитаемого, опустить его вниз на строку  и
сдвинуть под уменьшаемое (за счет отложенной рекурсии).

ЭТО Вычитание_чисел
 Поиск-
 ВПРАВО
 Опусти_вниз
 ВВЕРХ
 ВЛЕВО
 Вычти
КОНЕЦ

ЭТО Поиск-
 ВВЕРХ
 ПОКА НЕ -
 {
  ВНИЗ
  ВПРАВО
  ВВЕРХ
 }
 ПОВТОРИ 2 ВВЕРХ
 ВНИЗ
КОНЕЦ

ЭТО Опусти_вниз
 ВНИЗ
 ЕСЛИ |
  ТО
  {
    ВВЕРХ
    ВПРАВО
    Опусти_вниз
    ВЛЕВО
  }
  ИНАЧЕ
  {
    ВНИЗ
    ВЛЕВО
  }
КОНЕЦ

ЭТО Вычти
 ВНИЗ
 ПОКА |
 {
   ПОВТОРИ 6 ВНИЗ
   ПОВТОРИ 9 ВВЕРХ
   ПОВТОРИ 2 ВНИЗ
   ВЛЕВО
   ВНИЗ
 }
КОНЕЦ


     Задача 5.

   Основная "изюминка" задачи - уплотнение записи после выброса
с поля каждой  второй палочки.
   Вот, например, решение Калинина Игоря из команды 32 г.Наход-
ки.
   Описание алгоритма. Деление заключается  в  "выбрасывании" с
поля каждой второй палочки. Сложность в том, что необходимо вы-
полнить нужное число  "толчков" записи влево для того, чтобы ее
уплотнить.
   Начинаем с того (процедура Деление), что проверяем существу-
ет ли  палочка во втором столбце, и, если  она есть, то убираем
ее и рекурсивно вызываем процедуру снова.
   Программа Деление выполняется N+1 раз, где N - это число па-
лочек, сброшенных с поля. После сброса  последней палочки Кука-
рача переходит ВПРАВО и ВВЕРХ, а серию на ветви ТО  не выполня-
ет. Процедура Деление выполняется N+1 раз, за это время Кукара-
ча проходит 2(N+1) шагов вправо, и после выхода из рекурсии де-
лает N+1 шагов  влево (при помощи отложенной команды ВЛЕВО) для
v того, чтобы убрать лишние пробелы между палочками ответа.

ЭТО Деление
 ВПРАВО
 ВВЕРХ
 ЕСЛИ НЕ ПУСТО
  ТО
  {
    ВНИЗ
    ВПРАВО
    Деление
   }
 ВЛЕВО
КОНЕЦ

   Небольшое пояснение к программе Игоря. Очень легко доказать,
что отложенная команда ВЛЕВО сработает нужное число раз.

ЭТО Деление
    ВПРАВО     <─────────┐
    ВВЕРХ                │
    ЕСЛИ НЕ ПУСТО        │ рекурсивный цикл
     ТО                  │
     {                   │
       ВНИЗ              │
       ВПРАВО            │
       Деление ──────────┘
      }
    ВЛЕВО    <──────────── отложенная команда
КОНЕЦ // Деление

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

   Елкин Женя из команды  07  (г.Саров) решил задачу без рекур-
сии. Он  рассмотрел  все  возможные  случаи исходного состояния
среды (2,  4, 6 или  8 палочек). Для каждого конкретного случая
он предусмотрел специальную обработку.  Решение,  конечно, пос-
троено не на универсальном алгоритме. В качестве объяснения ал-
горитма Женя приводит его блок-схему.
                                   _________
                                  (  начало )
                                  (_________)
                                  _____|_____
                                 |  идти в   |
                                 |конец чиcла|
                                 |___________|
                                       |
                                      / \
                            ___нет__/  8  \___да__
                           |        \ "|" /       |
                           |          \ /  _______|______
                           |              |   убрать 3   |
                           |              |   палочки    |
                          / \             |______________|
                  __нет_/  6  \__да_              |
                 |      \ "|" /     |             |
                 |        \ /  _____|_____        |
                 |            |  убрать 2 |       |
                 |            |  палочки  |       |
                / \           |___________|       |
        __нет_/  4  \_да_           |             |
       |      \"|"  /    |          |             |
       |        \ / _____|_____     |             |
       |           |  убрать 1 |    |             |
 ______|_____      |  палочку  |    |             |
| оставить 1 |     |___________|    |             |
|  палочку   |           |          |             |
|____________|           |          |             |
       |                 |          |             |
       |-------------------------------------------
                       ____|____
                      (  конец  )
                      (_________)

ЭТО Деление
 ПОВТОРИ 8 ВПРАВО
 ВВЕРХ
 ВЛЕВО
 ЕСЛИ |
  ТО ПОВТОРИ 3 ВЛЕВО
  ИНАЧЕ дел6
КОНЕЦ

// Проверка: число палочек равно 6
ЭТО дел6
 ПОВТОРИ 2 ВЛЕВО
 ЕСЛИ |
  ТО ПОВТОРИ 2 ВЛЕВО
  ИНАЧЕ дел4
КОНЕЦ

// Проверка: число палочек равно 4
ЭТО дел4
 ПОВТОРИ 2 ВЛЕВО
 ЕСЛИ |
  ТО ВЛЕВО
// Иначе делим на 2
  ИНАЧЕ ПОВТОРИ 2 ВЛЕВО
КОНЕЦ

   Программа  Игоря,  построенная на  универсальном рекурсивном
алгоритме, работает и тогда, когда поле расширяется и число па-
лочек увеличивается, например  до  40. Представьте себе, как бы
усложнилась программа Жени для 40 палочек! Для ее блок-схемы не
хватило бы большого листа бумаги. А  вот  программа  Игоря  без
всяких изменений работает и  для  60, и для большего количества
палочек, не увеличившись в длину ни на одну команду.

   Замечание по поводу  блок-схем. Ничего плохого в них нет, но
только в том случае, если они рисуются по структурным правилам.
Структурные  схемы  должны  состоять из структурных  компонент,
каждая из которых имеет только один вход и только один выход.
   Рассмотрим, используемую Игорем компоненту - развилку.  Раз-
вилка может содержать одну или две ветви, но всегда один вход и
один выход. Ее рисунок имеет один из следующих видов:
          вход                                вход
            │                                   │
           / \                                 / \
┌─────── /  ?  \───────┐            ┌─────── /  ?  \───────┐
│        \     /       │            │        \     /       │
│          \ /   ┌─────┴────┐ ┌─────┴─────┐    \ /   ┌─────┴────┐
│                │          │ │           │          │          │
│                └─────┬────┘ └─────┬─────┘          └─────┬────┘
│                      │            │                      │
└───────────О──────────┘            └───────────О──────────┘
            │                                   │
          выход                               выход

   Если посмотреть на блок-схему Игоря, то видно, что она нари-
сована немного неправильно. Ниже приводится исправленный  вари-
ант.
                                    начало
                                 ┌─────┴─────┐
                                 │  идти в   │
                                 │конец чиcла│
                                 └─────┬─────┘
                                       │
                              нет     / \   да
                           ┌────────/  8  \───────┐
                           │        \ "|" /       │
                           │          \ /  ┌──────┴──────┐
                           │               │  убрать 3   │
                           │               │  палочки    │
                   нет    / \  да          └──────┬──────┘
                 ┌──────/  6  \─────┐             │
                 │      \ "|" /     │             │
                 │        \ / ┌─────┴─────┐       │
                 │            │  убрать 2 │       │
                 │            │  палочки  │       │
          нет   / \  да       └─────┬─────┘       │
       ┌──────/  4  \────┐          │             │
       │      \"|"  /    │          │             │
       │        \ /┌─────┴─────┐    │             │
       │           │  убрать 1 │    │             │
┌──────┴─────┐     │  палочку  │    │             │
│ оставить 1 │     └─────┬─────┘    │             │
│  палочку   │           │          │             │
└──────┬─────┘           │          │             │
       │                 │          │             │
       └────────О────────┘          │             │
                │                   │             │
                └─────────О─────────┘             │
                          │                       │
                          └─────────────О─────────┘
                                        │
                                      конец

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

ЭТО Деление                           Деление
    ВПРАВО                               │
    ВВЕРХ                            ┌───┴────┐
    ЕСЛИ НЕ ПУСТО ТО                 │ ВПРАВО │
     {                               └───┬────┘
       ВНИЗ                          ┌───┴────┐
       ВПРАВО                        │ ВВЕРХ  │
       Деление                       └───┬────┘
      }                                  │
    ВЛЕВО                               / \
КОНЕЦ // Деление                      /     \
                                    /   не    \   да
                          ┌───────/            \─────┐
                          │        \  ПУСТО ?  /     │
                          │          \        / ┌────┴─────┐
                          │            \    /   │ ВНИЗ     │
                          │              \/     └────┬─────┘
                          │                     ┌────┴─────┐
                          │                     │ ВПРАВО   │
                          │                     └────┬─────┘
                          │                     ┌────┴─────┐
                          │                     │ Деление  │
                          │                     └────┬─────┘
                          └──────────────О───────────┘
                                    ┌────┴─────┐
                                    │ ВЛЕВО    │
                                    └────┬─────┘
                                       конец

   Однако, наглядность  рекурсивных  блок-схем  невысока. Так и
хочется добавить в блок-схему поясняющую "неструктурную "стрел-
ку:

                           Деление      <────────────────┐
                          ┌───┴────┐                     │
                          │ ВПРАВО │                     │
                          └───┬────┘                     │
                          ┌───┴────┐                     │
                          │ ВВЕРХ  │                     │
                          └───┬────┘                     │
                             / \                         │
                           /     \                       │
                         /   не    \   да                │
               ┌───────/            \─────┐              │
               │        \  ПУСТО ?  /     │              │
               │          \        / ┌────┴─────┐        │
               │            \    /   │ ВНИЗ     │        │
               │              \/     └────┬─────┘        │
               │                     ┌────┴─────┐        │
               │                     │ ВПРАВО   │        │
               │                     └────┬─────┘        │
               │                     ┌────┴─────┐        │
               │                     │ Деление  │  >─────┘
               │                     └────┬─────┘
               └──────────────О───────────┘
                         ┌────┴─────┐
                         │ ВЛЕВО    │
                         └────┬─────┘
                            конец

   Но даже при таком уточнении из  блок-схемы по-прежнему непо-
нятно, почему последняя команда ВЛЕВО выполняется  не один раз.
Дело как раз в том, что наша "неструктурная" стрелка не отража-
ет суть рекурсии: рекурсия это не "GOTO", это  вызов нового эк-
земпляра процедуры Деление, а не  переход  на  начало  старого.
Вряд  ли  стоит для рекурсивных программ рисовать блок-схемы  -
они могут только запутать суть происходящего.

     Задача 6.

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

ЭТО Умножение
 ВВЕРХ
 ЕСЛИ 1 ТО СТОЯТЬ
 ИНАЧЕ ЕСЛИ 2 ТО ЦИФРА
 ИНАЧЕ ЕСЛИ 3 ТО ПОВТОРИ 2 ЦИФРА
 ИНАЧЕ ЕСЛИ 4 ТО ПОВТОРИ 3 ЦИФРА
 ИНАЧЕ ЕСЛИ 5 ТО ПОВТОРИ 4 ЦИФРА
 ИНАЧЕ ЕСЛИ 6 ТО ПОВТОРИ 5 ЦИФРА
 ИНАЧЕ ЕСЛИ 7 ТО ПОВТОРИ 6 ЦИФРА
 ИНАЧЕ ЕСЛИ 8 ТО ПОВТОРИ 7 ЦИФРА
 ИНАЧЕ ЕСЛИ 9 ТО ПОВТОРИ 8 ЦИФРА
КОНЕЦ

ЭТО ЦИФРА
 ВПРАВО
 ВНИЗ
КОНЕЦ


     Задача  7.

   Определить, толкнул  Кукарача  букву  "о"  или  другую букву
очень легко. Но как поставить исполнителя в нужную строку после
просмотра текста?  Без  рекурсии  с отложенными командами здесь
совсем плохо.

ЭТО Подсчет
 Работа
 Коррекция
КОНЕЦ

 ЭТО Работа
  ВВЕРХ  // Толкнуть_кубик
  ЕСЛИ НЕ ПУСТО
   ТО
   {
     ЕСЛИ о
      ТО
      {
        Дальше Работа
        Отложенные_действия
      }
      ИНАЧЕ { Дальше Работа }
   }
 КОНЕЦ

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

  ЭТО Дальше
   ВНИЗ                                
   ВПРАВО
  КОНЕЦ                                

  ЭТО Отложенные_действия              
    ВНИЗ
  КОНЕЦ

  ЭТО Коррекция                        
   ПОВТОРИ 2 ВВЕРХ
  КОНЕЦ

   В общем  случае процедура Отложенные_действия может быть как
угодно сложна.
   С разной степенью запутанности большинство ребята реализова-
ли описанный выше алгоритм.
   А вот программа  Ялышева Влада из команды 09 (г.Пермь) отли-
чается одной важной деталью: она работает не только  для 8 букв
"о"  в  слове  (как сказано в условии), но и для 9, то есть она
верно обрабатывает слово "ооооооооо", в то  время как остальным
программам этот  тест "не по  зубам". Что же такого сделал Влад
(возможно, не заметив этого сам)? Он распределил корректирующие
действия на две  фазы: одна команда ВВЕРХ выполняется перед от-
ложенными действиями, а  вторая - после. Именно из-за этого от-
ложенный спуск может быть на  одну  ступеньку  длиннее. Вот его
решение.

ЭТО Число_букв_о
 Число_букв_о_2
 ВВЕРХ
КОНЕЦ

ЭТО Число_букв_о_2
 ВВЕРХ
 ЕСЛИ НЕ ПУСТО ТО Поиск_о
 ИНАЧЕ ВВЕРХ
КОНЕЦ

ЭТО Поиск_о
 ЕСЛИ О ТО
  {
   ВНИЗ
   ВПРАВО
   Число_букв_о_2
   ВНИЗ
  }
 ИНАЧЕ
  {
   ВНИЗ
   ВПРАВО
   Число_букв_о_2
  }
КОНЕЦ


     Задача 8

   Возможный алгоритм решения основан  на  рекурсивном свойстве
сложения. Запишем исходное  число в виде  xd, где d  -  младшая
цифра числа,  а x -  остальные его цифры. Обозначим через Плюс1
алгоритм добавления 1 к исходному числу. Тогда можно записать:

                       /
                      │ x(d+1), если d < 9
          Плюс1(xd) = │
                      │ Плюс1(x)0, если d = 9
                       \
   Почти  все  команды  следовали приведенному выше  алгоритму.
Вот,  например,  решение команды  13  (руководители  Емельянова
Е.В., Полюшкина Н.А., г.Иркутск).

ЭТО Увеличь_на_1
 ВВЕРХ
 ЕСЛИ НЕ 9 ТО Увеличь
 ИНАЧЕ
 {
  Цифра_0
  Увеличь_на_1
 }
КОНЕЦ

ЭТО Увеличь
 ЕСЛИ       0 ТО Цифра_1
 ИНАЧЕ ЕСЛИ 1 ТО Цифра_2
 ИНАЧЕ ЕСЛИ 2 ТО Цифра_3
 ИНАЧЕ ЕСЛИ 3 ТО Цифра_4
 ИНАЧЕ ЕСЛИ 4 ТО Цифра_5
 ИНАЧЕ ЕСЛИ 5 ТО Цифра_6
 ИНАЧЕ ЕСЛИ 6 ТО Цифра_7
 ИНАЧЕ ЕСЛИ 7 ТО Цифра_8
 ИНАЧЕ ЕСЛИ 8 ТО Цифра_9
 ВНИЗ
 НАЗАД
КОНЕЦ

ЭТО Цифра_0
 ВНИЗ
 ПОВТОРИ 2 ВПЕРЕД
 ВВЕРХ
 НАЗАД
 ВНИЗ
 НАЗАД
 ВЛЕВО
КОНЕЦ

ЭТО Цифра_1
 ВНИЗ
 ПОВТОРИ 3 ВПЕРЕД
 ВВЕРХ
 ПОВТОРИ 2 НАЗАД
КОНЕЦ

ЭТО Цифра_2
 ВНИЗ
 ПОВТОРИ 4 ВПЕРЕД
 ВВЕРХ
 ПОВТОРИ 3 НАЗАД
КОНЕЦ

ЭТО Цифра_3
 ВНИЗ
 ПОВТОРИ 5 ВПЕРЕД
 ВВЕРХ
 ПОВТОРИ 4 НАЗАД
КОНЕЦ

ЭТО Цифра_4
 ВНИЗ
 ПОВТОРИ 6 ВПЕРЕД
 ВВЕРХ
 ПОВТОРИ 5 НАЗАД
КОНЕЦ

ЭТО Цифра_5
 ВНИЗ
 ПОВТОРИ 7 ВПЕРЕД
 ВВЕРХ
 ПОВТОРИ 6 НАЗАД
КОНЕЦ

ЭТО Цифра_6
 ВНИЗ
 ПОВТОРИ 8 ВПЕРЕД
 ВВЕРХ
 ПОВТОРИ 7 НАЗАД
КОНЕЦ

ЭТО Цифра_7
 ВНИЗ
 ПОВТОРИ 9 ВПЕРЕД
 ВВЕРХ
 ПОВТОРИ 8 НАЗАД
КОНЕЦ

ЭТО Цифра_8
 ВНИЗ
 ПОВТОРИ 10 ВПЕРЕД
 ВВЕРХ
 ПОВТОРИ 9 НАЗАД
КОНЕЦ

ЭТО Цифра_9
 ВНИЗ
 ПОВТОРИ 11 ВПЕРЕД
 ВВЕРХ
 ПОВТОРИ 10 НАЗАД
КОНЕЦ


   Решения команд 27 (руководитель Пиняжина И.Н.,  г.Зеленогор-
ски) и 57 (автор  решения  Ляхов Александр, г.Волгоград) не ре-
курсивные. Вместо рекурсии в них использован цикл ПОКА.

Решение Александра.

Описание алгоритма.
   Смещаемся по записи числа справа налево.
   1. Пока в клетке стоит цифра "9" заменяем ее на "0"
   2. Как только встретили  цифру  отличную от "9", заменяем ее
на следующую и завершаем работу.

ЭТО Плюс_1
 ВВЕРХ                                 
 ПОКА 9 { Ставь_0 ВЛЕВО ВВЕРХ }
 Ставь_цифру
КОНЕЦ                                  

ЭТО Ставь_0
 ВНИЗ
 ПОВТОРИ 2 ВПЕРЕД
 ВВЕРХ                                 
 НАЗАД                                 
 На_место
КОНЕЦ                                  

ЭТО Ставь_цифру
 ЕСЛИ 0 ТО Ставь_1
 ЕСЛИ 1 ТО Ставь_2
 ЕСЛИ 2 ТО Ставь_3
 ЕСЛИ 3 ТО Ставь_4
 ЕСЛИ 4 ТО Ставь_5
 ЕСЛИ 5 ТО Ставь_6
 ЕСЛИ 6 ТО Ставь_7
 ЕСЛИ 7 ТО Ставь_8
 ЕСЛИ 8 ТО Ставь_9
КОНЕЦ                                  

ЭТО Ставь_1
 ВНИЗ                                  
 ПОВТОРИ 3 ВПЕРЕД                      
 ВВЕРХ
 ПОВТОРИ 2 НАЗАД
 На_место
КОНЕЦ                                  

ЭТО Ставь_2
 ВНИЗ                                  
 ПОВТОРИ 4 ВПЕРЕД                      
 ВВЕРХ
 ПОВТОРИ 3 НАЗАД                       
 На_место
КОНЕЦ                                  

ЭТО Ставь_3
 ВНИЗ                                  
 ПОВТОРИ 5 ВПЕРЕД                      
 ВВЕРХ                                 
 ПОВТОРИ 4 НАЗАД                       
 На_место
КОНЕЦ                                  

ЭТО Ставь_4
 ВНИЗ
 ПОВТОРИ 6 ВПЕРЕД
 ВВЕРХ                                 
 ПОВТОРИ 5 НАЗАД                       
 На_место
КОНЕЦ                                  

ЭТО Ставь_5
 ВНИЗ
 ПОВТОРИ 7 ВПЕРЕД                      
 ВВЕРХ                                 
 ПОВТОРИ 6 НАЗАД                       
 На_место
КОНЕЦ                                  

ЭТО Ставь_6
 ВНИЗ                                  
 ПОВТОРИ 8 ВПЕРЕД                      
 ВВЕРХ                                 
 ПОВТОРИ 7 НАЗАД                       
 На_место
КОНЕЦ                                  

ЭТО Ставь_7
 ВНИЗ                                  
 ПОВТОРИ 9 ВПЕРЕД                      
 ВВЕРХ                                 
 ПОВТОРИ 8 НАЗАД
 На_место
КОНЕЦ                                  

ЭТО Ставь_8
 ВНИЗ                                  
 ПОВТОРИ 10 ВПЕРЕД                     
 ВВЕРХ                                 
 ПОВТОРИ 9 НАЗАД                       
 На_место
КОНЕЦ                                  

ЭТО Ставь_9
 ВНИЗ                                  
 ПОВТОРИ 11 ВПЕРЕД                     
 ВВЕРХ                                 
 ПОВТОРИ 10 НАЗАД                      
 На_место
КОНЕЦ

ЭТО На_место
 ВНИЗ                                  
 НАЗАД                                 
КОНЕЦ                                  
