                     Решения задач
                     -------------
5.2.10. Задача a (6 баллов) Кукарачья геометрия.
Средний бал решений: 4.3 (72%)

   Определение 8
   -------------
  Горизонтальный отрезок,  концевая  точка  которого совпадает с
одной из точек вертикального отрезка, называется перпендикуляром
к вертикальному отрезку.
   Соответственно, вертикальный отрезок, концевая точка которо-
го совпадает с одной из точек  горизонтального отрезка, называ-
ется перпендикуляром к горизонтальному отрезку.
   Перпендикуляр к  отрезку называется срединным, если его кон-
цевая точка совпадает с точкой, расположенной  точно в середине
отрезка. Понятно, что срединный  перпендикуляр  можно построить
только к отрезку с длиной, выражающейся четным числом.
   Задание.
   Буквы a и  b на поле исполнителя образуют горизонтальный от-
резок ab.  Известно,  что  длина  отрезка  ab выражается четным
числом. В начальный момент Кукарача расположен на этом отрезке,
сразу за буквой a.
   Установить исполнитель в точку на срединном  перпендикуляре,
построенного к отрезку  ab  вниз так, чтобы длина вертикального
отрезка, изображающего перпендикуляр,  равнялась половине длины
отрезка ab.

   Пример. При таком расположении букв a и b на поле:
                    1 2 3 4 5 6 7 8 9
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬
                 1 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 2 │ │a│¤│ │ │ │ │b│ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 3 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 4 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 5 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼

   Кукарача должен быть установлен в точку (5,5):
                    1 2 3 4 5 6 7 8 9
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬
                 1 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 2 │ │a│ │ │ │ │ │b│ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 3 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 4 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 5 │ │ │ │ │¤│ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼


   Решение.
   Эта задача  очень  похожа  на  предыдущую.  Правда, есть две
проблемы:
   1. Нужно сместить исполнителя  вниз  не на длину отрезка ab,
как было в первой задаче, а в половину меньше;
   2. Установить исполнитель нужно не в столбце с буквой "b", а
в столбце - срединном перпендикуляре к отрезку ab.

   Решение проблем.
   В  решении  задачи 9 каждой команде ВПРАВО сопоставляется  в
рекурсии отложенная команда ВНИЗ. Таким образом, мы смещали ис-
полнитель _вниз_ на число шагов, совершенных _вправо_.
   Теперь нужно сделать так, чтобы  число  шагов  _вниз_ было в
два раза меньше числа шагов _вправо_. Значит, на каждые две ко-
манды ВПРАВО,  выполняемые  в рекурсии, должна приходиться одна
отложенная команда ВНИЗ.
   На самом деле, "откладывать" надо не одну команду ВНИЗ а па-
ру команд: ВНИЗ и ВЛЕВО. Это позволит решить проблему 2. Испол-
нитель,  подталкиваемый  рекурсивной "пружиной",  будет переме-
щаться вниз-влево и в итоге окажется на срединном перпендикуля-
ре.
   Из этих рассуждений рождается процедура:

ЭТО Перпендикуляр        │
 ВПРАВО        <─────────┼┐ Эти команды выполняются в рекурсии
 ВПРАВО        <─────────┼┘
 ЕСЛИ b ТО Установкаb    │
 ИНАЧЕ Перпендикуляр     │
 ВНИЗ          <─────────┼┐ Эти команды работают при выходе
 ВЛЕВО         <─────────┼┘ из рекурсии.
КОНЕЦ                    │
                         │

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

─────────────────────┬───────────────────────────────────────────
ЭТО Работа           │ Главная процедура
 Перпендикуляр       │
 ВЛЕВО       <───────┼─  корректировка положения исполнителя
КОНЕЦ                │
                     │
ЭТО Перпендикуляр    │
 ПОВТОРИ 2 ВПРАВО    │Два шага вправо в рекурсии
 ЕСЛИ b ТО Установкаb│
 ИНАЧЕ Перпендикуляр │
 ВНИЗ               ┌┤и один "зигзаг" при выходе из нее.
 ВЛЕВО              └┤
КОНЕЦ                │
                     │
ЭТО Установкаb       │
 ВНИЗ                │
 ПОВТОРИ 2 ВПРАВО    │
 ВВЕРХ               │
 ПОВТОРИ 2 ВЛЕВО <─┐ │В силу того, что  длина отрезка ab четна,
КОНЕЦ              │ │кубик с "b" всегда сдвигается вправо ровно на две клетки.
                   └─│Значит, команда ПОВТОРИ 2 ВЛЕВО гарантированно вернет
                     │его на прежнее место.
─────────────────────┴─────────────────────────────────────────

   Описанная выше идея легла в основу  алгоритма всех (правиль-
ных) решений.
   Программы незначительно отличаются друг  от  друга. Отдельно
стоит программа команды 30.

Команда: 30
Авторы: Саша Усик, Сасса
Оценка: 6

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

   Комментарий куратора.
   Идея все та же: два шага вправо - один вниз-влево.  Но прог-
рамма, устроена не так, как другие: более хитро.
   Рекомендуется для любителей красивых головоломок.

ЭТО программа
  вправо
КОНЕЦ

ЭТО вправо
  ВПРАВО
  ЕСЛИ НЕ ПУСТО ТО вернуть
  ИНАЧЕ вправо1
  ВЛЕВО
КОНЕЦ

ЭТО вправо1
  ВПРАВО
  вправо
  ВНИЗ
КОНЕЦ


ЭТО вернуть
  ВНИЗ ВПРАВО ВПРАВО ВВЕРХ ВЛЕВО ВНИЗ
ВЛЕВО
КОНЕЦ

