Роботландский Университет 00/01
31 Азы программирования
Авторское решение задач турнира Кукарачи
-------------------------------

ноябрь-декабрь, 2000 (C) А.А.Дуванов

Вступительное слово
-------------------
Ниже предлагаются авторские решения задач турнира. Эти решения нельзя
рассматривать как наилучшие из всех возможных. Многолетний опыт работы
курса 31 не позволяет мне заявить: вот образец к которому нужно
стремиться. В каждом турнире случаются решения ребят, которые лучше
моего (эффективнее, красивее).

Единственное, что я могу сказать: мои решения лучше по оформлению. Мои
алгоритмы описаны понятнее, мои программы легче читать.

К сожалению, ребята в своих текстах описывают не столько алгоритмы,
сколько архитектуру кода. Они пишут так:

"Сначала работает процедура Игрек, затем начинает работу процедура
Зет..."

Но, я немного забегаю вперед. Знакомство с работами юных программистов
еще впереди. Может быть в этом году в описательной сфере будут
радостные перемены!

Замечание. Эти тексты надо смотреть в обычном DOS-редакторе, так как
для правильной визуализации необходим моноширинный шрифт и поддержка
псевдографики. Этот текст нельзя читать в WORDе!

┌─────────────┐
│Решение задач│
└─────────────┘
1----------------------------------------------------------------------
Задача 1. (3 балла)  Программируемое перемещение.
Исполнитель расположен в левом верхнем углу поля, клетке (1,1). Где-то
в первом столбце расположен кубик с цифрой, справа от которого еще один
кубик с символом:

   1 2 3 4 5 6 7 8 9
  ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬
 1│¤│ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
 2│ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
 3│5│К│ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
 4│ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼

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

   1 2 3 4 5 6 7 8 9
  ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬
 1│¤│ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
 2│ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
 3│5│ │ │ │ │ │K│ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
 4│ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼

Дополнительные условия:
1) Поле исполнителя бесконечно вправо и вниз.
2) Надпись на символьном кубике может быть любой.

Решение
-------
А л г о р и т м
Исполнитель рекурсивно идет вниз пока не толкнет цифровой кубик. После
установки символьного кубика и возврата цифрового кубика на прежнее
место, отложенная в рекурсии команда ВВЕРХ возвращает исполнителя в
исходное положение.

П р о г р а м м а
ЭТО вход
 ВНИЗ                                  
 ЕСЛИ ПУСТО ТО { вход ВВЕРХ }          
 ИНАЧЕ         горизонталь
КОНЕЦ

ЭТО горизонталь                        
 ЕСЛИ       1 ТО ВПРАВО
 ИНАЧЕ ЕСЛИ 2 ТО { ПОВТОРИ 2 ВПРАВО    
                   ВЛЕВО }             
 ИНАЧЕ ЕСЛИ 3 ТО { ПОВТОРИ 3 ВПРАВО    
                   ПОВТОРИ 2 ВЛЕВО }
 ИНАЧЕ ЕСЛИ 4 ТО { ПОВТОРИ 4 ВПРАВО    
                   ПОВТОРИ 3 ВЛЕВО }   
 ИНАЧЕ ЕСЛИ 5 ТО { ПОВТОРИ 5 ВПРАВО
                   ПОВТОРИ 4 ВЛЕВО }   
 ИНАЧЕ ЕСЛИ 6 ТО { ПОВТОРИ 6 ВПРАВО    
                   ПОВТОРИ 5 ВЛЕВО }   
 ИНАЧЕ ЕСЛИ 7 ТО { ПОВТОРИ 7 ВПРАВО
                   ПОВТОРИ 6 ВЛЕВО }   
 ИНАЧЕ ЕСЛИ 8 ТО { ПОВТОРИ 8 ВПРАВО
                   ПОВТОРИ 7 ВЛЕВО }
 ИНАЧЕ ЕСЛИ 9 ТО { ПОВТОРИ 9 ВПРАВО    
                   ПОВТОРИ 8 ВЛЕВО }   
 ВНИЗ ВНИЗ                             
 ВЛЕВО ВВЕРХ                           
 ВПРАВО ВВЕРХ ВВЕРХ ВЛЕВО
КОНЕЦ
                                       
З а м е ч а н и е
Отложенная в рекурсии команда ВВЕРХ помещена внутрь условной команды.
Это позволяет сократить ее выполнение на один.

Сравните  две таких программы:

ЭТО пример1               ЭТО пример2
 ВНИЗ                      ВНИЗ
 ЕСЛИ ПУСТО ТО пример1     ЕСЛИ ПУСТО ТО { пример2 ВВЕРХ }
 ВВЕРХ                    КОНЕЦ
КОНЕЦ

Выполняя программу "пример1" исполнитель, после обнаружения кубика,
будет перемещен вверх на одну клетку дальше, чем в программе
"пример2". Почему?

Потому, что в программе "пример1" команда ВВЕРХ стоит после команды
ЕСЛИ и выполняется один раз после завершения команды ЕСЛИ, а затем
много раз под действием рекурсивной пружины.

В программе "пример2" команда ВВЕРХ стоит в самой конструкции ECЛИ и
работает только под действием рекурсивной пружины.

2----------------------------------------------------------------------
Задача 2. (5 баллов)  Деление пополам.
На поле исполнителя из кубиков собран вертикальный столбик.
Исполнитель расположен слева перед первым кубиком основания:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │6│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │5│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │4│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │3│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │2│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │¤│1│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─

Разделить столбик на два, не нарушая вертикального расположения
кубиков:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │3│6│ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │2│5│ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │1│4│ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─


Дополнительные условия:
1) Поле исполнителя бесконечно по всем четырем направлениям.
2) Число кубиков в исходном столбике не меньше двух и четно.
3) Надписи на кубиках могут быть любыми.

Решение
-------

А л г о р и т м
Процедура "середина"
"Слепой" исполнитель идет вверх ощупывая кубики. За один ход
принимается два сдвига вверх по вертикали, рекурсивная пружина при
этом программируется только на одну команду ВНИЗ. Когда исполнитель
поднимется до верхнего кубика столбика, пружина "отпускается" и
исполнитель устанавливается в середину столбика.

Процедура "сдвиг"
Исполнитель сдвигает верхнюю половину столбика на одну клетку вправо,
программируя рекурсивную пружину на команду ВНИЗ. Когда сдвиг вправо
закончен, сдвиг половинки (как единого целого) вниз завершают
отложенные команды.

П р о г р а м м а
ЭТО вход                  │
 середина                 │найдем середину
 сдвиг                    │сдвинем верхнюю половину вниз
КОНЕЦ                     │
                          │
ЭТО середина          <──┐│
 ВПРАВО ВЛЕВО            ││Два шага вверх если кубики еще есть
 ВВЕРХ                   ││
 ВПРАВО                  ││
 ЕСЛИ НЕ ПУСТО           ││
  ТО                     ││
  {                      ││
    ВЛЕВО ВВЕРХ середина─┘│
  }                       │
 ВНИЗ                     │Отложенная в рекурсии команда для перемещения
КОНЕЦ                     │исполнителя к середине столбика.
                          │
ЭТО сдвиг           <──┐  │
 ВПРАВО                │  │Сдвигаем верхнюю половину столбика вправо
 ЕСЛИ НЕ ПУСТО         │  │
  ТО                   │  │
  {                    │  │
    ВЛЕВО ВВЕРХ сдвиг ─┘  │
    ВНИЗ                  │Отложенная в рекурсии команда для сдвига
  }                       │верхней половины столбика вниз.
  ИНАЧЕ ВПРАВО            │Эта команда нужна для смещения исполнителя
КОНЕЦ                     │на верхушку столбика перед сдвигом его вниз
                          │усилием рекурсивной пружины.

3----------------------------------------------------------------------
Задача 3. (5 баллов)  Ракета.
На поле исполнителя из кубиков собран вертикальный столбик.
Исполнитель расположен слева перед первым кубиком основания:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │5│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │4│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │3│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │2│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │¤│1│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─

Построить из кубиков "ракету":

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │3│ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │2│ │5│ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │1│ │4│ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─


Дополнительные условия:
1) Поле исполнителя бесконечно по всем четырем направлениям.
2) Число кубиков в исходном столбике -- любое нечетное число большее одного.
3) Надписи на кубиках могут быть любыми.


Решение
-------
А л г о р и т м
Алгоритм получается небольшой модификацией алгоритма предыдущей задачи
(сдвиг верхней части не на один, а на два столбца вправо и отдельная
установка центрального кубика).

П р о г р а м м а
ЭТО вход                    │
 середина                   │Найдем "середину"
 сдвиг                      │Сдвинем верхнюю часть вниз
 центр                      │Установим центральный кубик
КОНЕЦ                       │
                            │
ЭТО середина                │
 ВПРАВО ВЛЕВО               │
 ВВЕРХ                      │
 ВПРАВО                     │
 ЕСЛИ НЕ ПУСТО              │
  ТО                        │
  {                         │
    ВЛЕВО ВВЕРХ середина    │
    ВНИЗ                    │
  }                         │
КОНЕЦ                       │
                            │
ЭТО сдвиг                   │Эта процедура сдвигает верхнюю часть
 ВПРАВО ВПРАВО              │не на один столбик вправо, а на два.
 ЕСЛИ НЕ ПУСТО              │
  ТО                        │
  {                         │
    ВЛЕВО ВЛЕВО ВВЕРХ сдвиг │
  }                         │
  ИНАЧЕ ВПРАВО              │
  ВНИЗ                      │
КОНЕЦ                       │
                            │
ЭТО центр                   │
 ВВЕРХ                      │
 ПОВТОРИ 3 ВЛЕВО            │
 ВНИЗ                       │
 ВПРАВО                     │
КОНЕЦ                       │

З а м е ч а н и е
Сравните процедуры "середина" этой и предыдущей задачи:

Задача 2                        Задача 3
---------------------------------------------------------
ЭТО середина                    ЭТО середина
 ВПРАВО ВЛЕВО                    ВПРАВО ВЛЕВО
 ВВЕРХ                           ВВЕРХ
 ВПРАВО                          ВПРАВО
 ЕСЛИ НЕ ПУСТО                   ЕСЛИ НЕ ПУСТО
  ТО                              ТО
  {                               {
    ВЛЕВО ВВЕРХ середина            ВЛЕВО ВВЕРХ середина
  }                                 ВНИЗ
 ВНИЗ                             }
КОНЕЦ                             КОНЕЦ

Рекурсивная пружина в процедуре "середина" задачи 2 опускает
исполнителя на одну клетку ниже. Почему?

Потому, что в ней команда ВНИЗ стоит после команды ЕСЛИ и
выполняется один раз после завершения команды ЕСЛИ, а затем
много раз под действием рекурсивной пружины.

В процедуре "середина" задачи 3 команда ВНИЗ стоит в самой конструкции
ECЛИ и работает только под действием рекурсивной пружины.

4----------------------------------------------------------------------
Задача 4. (8 баллов) Опрокидывание столбика.
На поле исполнителя из кубиков собран вертикальный столбик.
Исполнитель расположен слева перед первым кубиком основания:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │5│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │4│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │3│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │2│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │¤│1│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─

"Опрокинуть" столбик на горизонталь так, чтобы кубик, расположенный
в основании остался на месте:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │¤│1│2│3│4│5│ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─

Дополнительные условия:

1) Поле исполнителя бесконечно по всем четырем направлениям.
2) Число кубиков в исходном столбике не меньше двух.
3) Надписи на кубиках могут быть любыми.


Решение
-------

А л г о р и т м

Нижний кубик столбика на месте.
Вертикальный остаток сдвинем вправо и сместим вниз как целое.
Так будем повторять, пока остаток не станет пустым:
       ¤
 4     4     ¤            ¤
 3     3     4     4      4      ¤              ¤
 2 ->  2 ->  3 -> ¤3 ->   3 ->   4 ->  ¤4 ->    4 ->    ¤ ->   ¤
¤1    1     12    12    12     123    123    123     1234    1234

В этих действиях заметен цикл. Выделим его тело:

     4
    ¤3 ->  ¤4
... 12    123 ...

П р о г р а м м а

ЭТО вход                          │
 ВВЕРХ                            │ Первый кубик оставляем на месте.
 ВПРАВО                           │
 ПОКА НЕ ПУСТО { остаток ВПРАВО } │ Пока есть вертикальный остаток
КОНЕЦ                             │ укладываем его по кубику на горизонталь.
                                  │ (смещение остатка вправо и вниз)
                                  │
ЭТО остаток            <───┐      │Рекурсивная процедура, которая:
 ЕСЛИ НЕ ПУСТО             │      │-- смещает остаток вправо
  ТО                       │      │-- смещает остаток вниз
  {                        │      │
    ВЛЕВО ВВЕРХ  ВПРАВО    │      │
    остаток  ──────────────┘      │
    ВНИЗ                          │Рекурсивная пружинка для смещения
  }                               │исполнителя к горизонтальному ряду.
 ИНАЧЕ                            │
 {                                │
   ВПРАВО                         │Помещаем исполнитель над остатком.
   ВНИЗ                           │Толкаем остаток вниз.
   ВЛЕВО                          │Возвращаем исполнителя под удар
   ВВЕРХ                          │рекурсивной пружины с корректирующим
 }                                │шагов вверх.
КОНЕЦ                             │
                                  │

5----------------------------------------------------------------------
Задача 5. (7 баллов) Разобрать по бревнышку.
На поле исполнителя из кубиков собран прямоугольник высотой в четыре
кубика. Исполнитель расположен слева перед первым кубиком основания:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │a│b│c│ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │7│8│9│ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │4│5│6│ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │¤│1│2│3│ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼

Преобразовать прямоугольник в горизонтальный отрезок:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │ │ │ │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │ │ │ │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │ │ │ │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │¤│a│b│c│7│8│9│4│5│6│1│2│3│
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼


Дополнительные условия:

1) Поле исполнителя бесконечно по всем четырем направлениям.
2) Ширина прямоугольника -- любое число кубиков.
3) Надписи на кубиках могут быть любыми.

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

А л г о р и т м

Исходное положение:

   abc
   789
   456
  ¤123

Будем "раскатывать" прямоугольник по рядам:

-- нижний ряд сместим вправо на ширину прямоугольника (процедура
"ряд"):

   abc
   789
   456

       123

-- остаток прямоугольника опустим на уровень первого ряда (процедура
"смещение"):

    abc
    789
   ¤456123

Понятно, что процедуры "ряд" и "смещение" нужно повторить 3 раза.

П р о г р а м м а

ЭТО вход                  │
 ПОВТОРИ 3                │
 {                        │
   ряд                    │1) сдвиг нижнего ряда
   смещение               │2) смещение вниз остатка прямоугольника
 }                        │
КОНЕЦ                     │
                          │
ЭТО ряд        <───┐      │Сдвиг нижнего ряда.
 ВПРАВО            │      │
 ВВЕРХ             │      │Сдвигаем ряд вправо пока сверху есть кубики.
 ЕСЛИ НЕ ПУСТО     │      │Рекурсивная пружинка "ВЛЕВО" возвращает
  ТО { ВНИЗ ряд } ─┘      │исполнителя к левому краю прямоугольника.
 ВЛЕВО                    │
КОНЕЦ                     │
                          │
ЭТО смещение              │Смещение вниз остатка прямоугольника
 ВВЕРХ                    │
 ВПРАВО                   │
 ПОКА НЕ ПУСТО            │Поднимаемся на верхний ряд прямоугольника.
 { ВЛЕВО ВВЕРХ ВПРАВО }   │
 вниз2                    │Опускаем прямоугольник вниз на две клетки.
 ВНИЗ                     │
 ВПРАВО                   │
 ПОКА НЕ ПУСТО            │Возвращаем исполнителя в исходное положение
 {                        │со сдвигом прямоугольника на клетку вправо.
  ВЛЕВО ВНИЗ ВПРАВО       │
 }                        │
 ВВЕРХ                    │
КОНЕЦ                     │
                          │
ЭТО вниз2          <───┐  │Опускаем прямоугольник вниз на две клетки.
 ВПРАВО                │  │
 ВНИЗ ВНИЗ             │  │
 ЕСЛИ НЕ ПУСТО         │  │
  ТО { ВВЕРХ ВВЕРХ вниз2 }│
 ВЛЕВО                    │Рекурсивная пружинка "ВЛЕВО" возвращает
КОНЕЦ                     │исполнителя к левому краю прямоугольника.


6----------------------------------------------------------------------
Задача 6. (8 баллов) Разобрать по бревнышку 2.
На поле исполнителя из кубиков собран прямоугольник.
Исполнитель расположен слева перед первым кубиком основания:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │a│b│c│ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │7│8│9│ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │4│5│6│ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │¤│1│2│3│ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼

Преобразовать прямоугольник в горизонтальный отрезок:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │ │ │ │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │ │ │ │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │ │ │ │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │¤│a│b│c│7│8│9│4│5│6│1│2│3│
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼


Дополнительные условия:

1) Поле исполнителя бесконечно по всем четырем направлениям.
2) Ширина и высота прямоугольника - произвольные.
3) Надписи на кубиках могут быть любыми.

Решение
-------
А л г о р и т м
Цикл, который записан для решения предыдущей задачи хорош, но он для
фиксированного числа оборотов. Вот бы заменить его на цикл ПОКА, тогда
он годился бы для произвольной высоты прямоугольника.

Проблема в том, чтобы правильно построить условие цикла ПОКА и
правильно подготовить среду к проверке этого условия.

Сделаем так. Запустим процедуру "ряд" -- она сдвинет нижний ряд
прямоугольника по горизонтали:

   abc
   789
   456

       123

Но прежде чем отпускать рекурсивную пружинку "ВЛЕВО", сдвинем
предпоследний ряд прямоугольника на одну клетку влево:

   abc
   789
  456

       123

Исполнителя рекурсивно (с поправкой) вернем к первому кубику этого
сдвинутого ряда:
   abc
   789
  456
 ¤
       123

Это и будет теперь положением среды для проверки условия НЕ ПУСТО после
команд ВВЕРХ ВПРАВО. Пока НЕ ПУСТО цикл ПОКА будет продолжаться:

ЭТО вход
 ряд
 ВВЕРХ
 ВПРАВО
 ПОКА НЕ ПУСТО
 {
   ВНИЗ смещение
   ряд ВВЕРХ ВПРАВО
 }
КОНЕЦ

П р о г р а м м а
ЭТО вход                  │
 ряд                      │
 ВВЕРХ                    │
 ВПРАВО                   │
 ПОКА НЕ ПУСТО            │
 {                        │
   ВНИЗ смещение          │
   ряд ВВЕРХ ВПРАВО       │
 }                        │
КОНЕЦ                     │
                          │
ЭТО ряд                   │
 ВПРАВО                   │
 ВВЕРХ                    │
 ЕСЛИ НЕ ПУСТО            │
  ТО { ВНИЗ ряд }         │
  ИНАЧЕ                   │
  {                       │
    ВВЕРХ                 │
    ВЛЕВО                 │
    ВНИЗ                  │
  }                       │
 ВЛЕВО                    │
КОНЕЦ                     │
                          │
ЭТО смещение              │
 ВВЕРХ                    │
 ВПРАВО                   │
 ПОКА НЕ ПУСТО            │
 { ВЛЕВО ВВЕРХ ВПРАВО }   │
 вниз2                    │
 ВНИЗ                     │
 ВПРАВО                   │
 ПОКА НЕ ПУСТО            │
 {                        │
  ВЛЕВО ВНИЗ ВПРАВО       │
 }                        │
 ВВЕРХ                    │
КОНЕЦ                     │
                          │
ЭТО вниз2                 │
 ВПРАВО                   │
 ВНИЗ ВНИЗ                │
 ЕСЛИ НЕ ПУСТО            │
  ТО { ВВЕРХ ВВЕРХ вниз2 }│
 ВЛЕВО                    │
КОНЕЦ                     │

7----------------------------------------------------------------------
Задача 7. (7 баллов) Кирпич на другой столбик.
На поле два столбика кирпичей. Снять верхний кирпич с первого
столбика, положить на второй столбик и вернуться в исходное положение
(слева от нижнего кирпича первого столбика). Столбики отстоят друг от
друга на две клетки:

  ├─┼─┼─┼─┼─┼─┼─┼─┼         ├─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │         │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼         ├─┼─┼─┼─┼─┼─┼─┼─┼
  │ │1│ │ │ │ │ │ │         │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼         ├─┼─┼─┼─┼─┼─┼─┼─┼
  │ │2│ │ │ │ │ │ │  ───>   │ │2│ │ │1│ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼         ├─┼─┼─┼─┼─┼─┼─┼─┼
  │¤│3│ │ │Ш│ │ │ │         │¤│3│ │ │Ш│ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼         ├─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │         │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼         ├─┼─┼─┼─┼─┼─┼─┼─┼

Дополнительные условия:

1) Поле исполнителя бесконечно вверх, вниз и вправо.
2) В первом столбике есть хотя бы один кирпич.
3) Во втором столбике кирпичи могут отсутствовать вовсе.
4) После выполнения задания столбики остаются на прежних местах.

Решение
-------
А л г о р и т м

1) Снять кирпич с первого столбика (процедура п1-2.1)

-- Исполнитель идет к верхнему кирпичу первого столбика, закручивая
рекурсивную пружинку для возврата к основанию:
                                ¤
    1        1       ¤1         1
    2    ->  ¤2   ->  2    ->  2
    ¤3 ш      3 ш     3 ш      3 ш

-- Рекурсивной пружинкой исполнитель перемещает верхний кирпич к
основанию попутно смещая столбик на прежнее место:
        ¤
        1       ¤
   ->  2    -> 21  -> 2 ¤    -> 2
       3 ш     3 ш     31 ш     3 ¤ш
                                  1

2) Подготовиться к установки кирпича на второй столбик
   (команды ВЛЕВО ВНИЗ ВНИЗ ВПРАВО ВВЕРХ):

   2
   3 1ш
     ¤

3) Забросить кирпич на второй столбик (процедура п1-2.2):

-- Исполнитель идет к вершине второго столбика, закручивая рекурсивную
пружинку для возврата к основанию и смещения второго столбика на
прежнее место:

                  1
   2 1     ->   2 ¤     ->  2 1 ¤
   3 ¤ш         3  ш        3  ш

-- Рекурсивной пружинкой исполнитель перемещается к основанию попутно
смещая столбик на прежнее место:

  2 1
  3 ш¤

4) Возвратить исполнителя в исходное положение (команды
   ВНИЗ
   ПОВТОРИ 6 ВЛЕВО
   ВВЕРХ):

  2 1
 ¤3 ш

П р о г р а м м а
                              │
ЭТО вход                      │
 п1-2                         │
КОНЕЦ                         │
                              │
ЭТО п1-2                      │
 п1-2.1                       │Снять кирпич с первого столбика
 ВЛЕВО ВНИЗ ВНИЗ ВПРАВО ВВЕРХ │Подготовка установки кирпича на второй столбик
 п1-2.2                       │Забросить кирпич на второй столбик
 ВНИЗ                         │Возвратить исполнителя в исходное положение
 ПОВТОРИ 6 ВЛЕВО              │
 ВВЕРХ                        │
КОНЕЦ                         │
                              │
ЭТО п1-2.1            <──┐    │Снять кирпич с первого столбика
 ВПРАВО                  │    │
 ЕСЛИ НЕ ПУСТО           │    │
  ТО                     │    │
  {                      │    │
    ВЛЕВО ВВЕРХ п1-2.1 ──┘    │
    ВНИЗ ВЛЕВО ВПРАВО         │Рекурсивная пружина
  }                           │
  ИНАЧЕ                       │
  {                           │Подготовка перед воздействием рекурсивной
    ВНИЗ ВПРАВО ВВЕРХ ВПРАВО  │пружины
  }                           │
КОНЕЦ                         │
                              │
ЭТО п1-2.2            <──┐    │Забросить кирпич на второй столбик
 ВВЕРХ ВПРАВО            │    │
 ЕСЛИ НЕ ПУСТО           │    │
  ТО                     │    │
  {                      │    │
    ВЛЕВО п1-2.2       ──┘    │
    ВНИЗ ВЛЕВО ВПРАВО         │Рекурсивная пружина
  }                           │
 ИНАЧЕ                        │
 {                            │
  ВЛЕВО ВЛЕВО ВВЕРХ ВПРАВО    │Подготовка перед воздействием рекурсивной
  ВВЕРХ ВПРАВО ВНИЗ           │пружины
  ВПРАВО ВПРАВО ВНИЗ          │
 }                            │
КОНЕЦ                         │

8----------------------------------------------------------------------
Задача 8. (15 баллов) Ханойская башня.
Написать программу, которая решает на поле исполнителя задачу о
Ханойской башне.

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

Решение
-------

Смотрите отдельные файлы:

han.txt -- описание решения
han.exe -- роботландская Ханойская башня
han.htm -- решение на JavaScript (запускается загрузкой в браузер)

9----------------------------------------------------------------------
Задача 9 (6 баллов) Проверка программы.

Определение
-----------
<программа>   := <команда>|<программа><команда>
<команда>     := <простая>|<цикл>
<простая>     := л|п|в|н
<цикл>        := ц<повторитель><простая>
<повторитель> := 4|5

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

¤запись

Если проверяемая запись - программа, установить Кукарачу в конец
записи:

 запись¤

Если запись - не программа, поставить исполнитель под первым неверным
символом:

запись
  ¤

Решение
-------

А л г о р и т м

диаграмма переходов


                         л,п,в,н
                        ┌───────┐
                        V       │
┌───────────┐л,п,в,н  ┌─────────┴─┐ПУСТО    ┌───────────┐
│    вход   ├────────>│  простая  │────────>│ программа │
└─────┬─────┘         └─┬─────────┘         └───────────┘
      │ц               ц│       ^
      │   ┌─────────────┘       │
      V   V                     │л,п,в,н
┌───────────┐         ┌─────────┴─┐
│  цикл     │────────>│повторитель│
└───────────┘4,5      └───────────┘


На схеме не обозначены переходы на состояние "ошибка". Эти переходы
происходят из каждого блока (кроме конечного состояния "программа") по
обнаружению символа, отличного от тех, которые блок обрабатывает.

П р о г р а м м а

ЭТО вход                        │ начальное состояние (вход)
  шаг                           │
  ЕСЛИ       л ТО простая       │
  ИНАЧЕ ЕСЛИ п ТО простая       │
  ИНАЧЕ ЕСЛИ в ТО простая       │
  ИНАЧЕ ЕСЛИ н ТО простая       │
  ИНАЧЕ ЕСЛИ ц ТО цикл          │
  ИНАЧЕ           ошибка        │
КОНЕЦ                           │
                                │
ЭТО простая                     │ состояние (простая)
  шаг                           │
  ЕСЛИ       л     ТО простая   │
  ИНАЧЕ ЕСЛИ п     ТО простая   │
  ИНАЧЕ ЕСЛИ в     ТО простая   │
  ИНАЧЕ ЕСЛИ н     ТО простая   │
  ИНАЧЕ ЕСЛИ ц     ТО цикл      │
  ИНАЧЕ ЕСЛИ ПУСТО ТО программа │
  ИНАЧЕ               ошибка    │
КОНЕЦ                           │
                                │
ЭТО программа                   │ конечное состояние (программа)
  ВВЕРХ                         │
КОНЕЦ                           │
                                │
ЭТО цикл                        │ состояние (цикл)
  шаг                           │
  ЕСЛИ       4 ТО повторитель   │
  ИНАЧЕ ЕСЛИ 5 ТО повторитель   │
  ИНАЧЕ           ошибка        │
КОНЕЦ                           │
                                │
ЭТО повторитель                 │ состояние (повторитель)
  шаг                           │
  ЕСЛИ       л ТО простая       │
  ИНАЧЕ ЕСЛИ п ТО простая       │
  ИНАЧЕ ЕСЛИ в ТО простая       │
  ИНАЧЕ ЕСЛИ н ТО простая       │
  ИНАЧЕ           ошибка        │
КОНЕЦ                           │
                                │
ЭТО ошибка                      │ состояние (ошибка)
 шаг                            │ Сдвиг вверх остатка
 ЕСЛИ НЕ ПУСТО ТО ошибка        │ записи после ошибки.
 ВЛЕВО                          │ Возврат к месту ошибки.
КОНЕЦ                           │
                                │
ЭТО шаг                         │ проверка следующего
 ВНИЗ ВПРАВО ВВЕРХ              │ символа
КОНЕЦ                           │
                                │
a----------------------------------------------------------------------
Задача a (6 баллов) Проверка программы 2.

Определение
-----------
<программа>   := <команда>|<программа><команда>
<команда>     := <простая>|<цикл>
<простая>     := л|п|в|н
<цикл>        := ц<повторитель><команда>
<повторитель> := 4|5

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

¤запись

Если проверяемая запись - программа, установить Кукарачу в конец
записи:

 запись¤

Если запись - не программа, поставить исполнитель под первым неверным
символом:

запись
  ¤

Решение
-------

А л г о р и т м

диаграмма переходов


                         л,п,в,н
                        ┌───────┐
                        V       │
┌───────────┐л,п,в,н  ┌─────────┴─┐ПУСТО    ┌───────────┐
│    вход   ├────────>│  простая  │────────>│ программа │
└─────┬─────┘         └─┬─────────┘         └───────────┘
   ^  │ц               ц│
   │  │   ┌─────────────┘
4,5│  V   V
┌───────────┐
│  цикл     │
└───────────┘


На схеме не обозначены переходы на состояние "ошибка". Эти переходы
происходят из каждого блока (кроме конечного состояния "программа") по
обнаружению символа, отличного от тех, которые указаны в блоке.

П р о г р а м м а

ЭТО вход                        │ начальное состояние (вход)
  шаг                           │
  ЕСЛИ       л ТО простая       │
  ИНАЧЕ ЕСЛИ п ТО простая       │
  ИНАЧЕ ЕСЛИ в ТО простая       │
  ИНАЧЕ ЕСЛИ н ТО простая       │
  ИНАЧЕ ЕСЛИ ц ТО цикл          │
  ИНАЧЕ           ошибка        │
КОНЕЦ                           │
                                │
ЭТО простая                     │ состояние (простая)
  шаг                           │
  ЕСЛИ       л     ТО простая   │
  ИНАЧЕ ЕСЛИ п     ТО простая   │
  ИНАЧЕ ЕСЛИ в     ТО простая   │
  ИНАЧЕ ЕСЛИ н     ТО простая   │
  ИНАЧЕ ЕСЛИ ц     ТО цикл      │
  ИНАЧЕ ЕСЛИ ПУСТО ТО программа │
  ИНАЧЕ               ошибка    │
КОНЕЦ                           │
                                │
ЭТО программа                   │ конечное состояние (программа)
  ВВЕРХ                         │
КОНЕЦ                           │
                                │
ЭТО цикл                        │ состояние (цикл)
  шаг                           │
  ЕСЛИ       4 ТО вход          │
  ИНАЧЕ ЕСЛИ 5 ТО вход          │
  ИНАЧЕ           ошибка        │
КОНЕЦ                           │
                                │
ЭТО ошибка                      │ состояние (ошибка)
 шаг                            │ Сдвиг вверх остатка
 ЕСЛИ НЕ ПУСТО ТО ошибка        │ записи после ошибки.
 ВЛЕВО                          │ Возврат к месту ошибки.
КОНЕЦ                           │
                                │
ЭТО шаг                         │ проверка следующего
 ВНИЗ ВПРАВО ВВЕРХ              │ символа
КОНЕЦ                           │
                                │
b----------------------------------------------------------------------
Задача b (10 баллов) Исполнитель Кроха.

Кроха -- это исполнитель, который умеет выполнять программы,
записанные по следующему правилу:

Определение
-----------
<программа>   := <команда>|<программа><команда>
<команда>     := л|п

Среда Крохи -- пятая строка поля Кукарачи без первой клетки. Кроха
отображается кубиком с надписью "К". В начальный момент Кроха может
быть в любом месте своей среды.

Напишите интерпретатор команд Крохи. Интерпретатор должен выполнять
программы, написанные для Крохи. В начальный момент Кукарача
расположен перед программой в клетке (3,1).


   1 2 3 4 5 6 7 8 9 10
  ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
1 │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
2 │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
3 │¤│п│р│о│г│р│а│м│м│а│
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
4 │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
5 │ │К│ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
6 │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
7 │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼

С е м а н т и к а  к о м а н д
л - на одну клетку влево
п - на одну клетку вправо

Решение
-------
Идея алгоритма
- - - - - - - -
Нужно читать команды Крохи, рекурсивно откладывая их выполнение.
Выполнение команд начинается после того, как вся программа Крохи
прочитана.

Замечания
- - - - -
1) Рекурсивно запоминать команды надо с конца записи для того, чтобы
затем они выполнились в правильном порядке.

2) Раз уж нам все равно нужно идти в конец записи, то по пути можно
проверить запись на правильность.


П р о г р а м м а

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