                     Решения задач
                     -------------

5.2.9. Задача 9 (5 баллов) Кукарачья геометрия.
Средний бал решений: 4.3 (87%)

   Определение 5
   -------------
   Будем рассматривать  каждую  клетку  на поле исполнителя как
геометрическую точку. Координаты точки отсчитываются от  левого
верхнего угла поля и обозначаются как обычные точки на плоскос-
ти парой чисел (x,y). Число x - номер строки, а y - номер стол-
бца, на  пересечении  которых  расположена клетка-точка. Первое
число x будем называть строкой точки, второе y  - столбцом точ-
ки. Точки  будем обозначать малыми латинскими буквами, приписы-
вая к ним, в  случае  необходимости, координаты. Точка o, соот-
ветствующая первой  клетке  в  первой  строке, имеет координаты
(1,1). Таким образом, она обозначается как o(1,1).

   Определение 6
   -------------
   Горизонтальным отрезком на поле Кукарачи назовем упорядочен-
ную пару точек, имеющих одинаковую  строку.  При  этом  столбец
первой точки пары меньше столбца второй.  Отрезок будем обозна-
чать двумя латинскими  буквами  - названиями точек, его образу-
ющих. При  необходимости  в  скобках можно указывать координаты
точек, отделяя их друг от друга запятой.
   Например, горизонтальный  отрезок, образуемый двумя  точками
a(x,y1)  и   b(x,y2),   можно   обозначать   как   ab  или  как
ab((x,y1),(x,y2)).
   Длиной  горизонтального  отрезка  ab((x,y1),(x,y2))  назовем
число y2-y1. Обозначать длины горизонтальных отрезков будем как
Pab или Pab((x,y1),(x,y2)). Таким образом, можно записать:
                 Pab((x,y1),(x,y2)) = y2-y1
   Будем считать, что  точка  t(t1,t2) на поле исполнителя при-
надлежит горизонтальному отрезку ab((x,y1),(x,y2)), если:
                      t1 = x
                      y1 <= t2 <= y2
(через "<=" обозначен знак "меньше или равно")

   Определение 7
   -------------
   Вертикальным отрезком на поле Кукарачи назовем упорядоченную
пару точек, имеющих одинаковый столбец. При  этом строка первой
точки пары меньше строки второй. Отрезок будем обозначать двумя
латинскими буквами - названиями точек, его  образующих. При не-
обходимости в скобках можно указывать координаты точек, отделяя
их друг от друга запятой.
   Например,  вертикальный отрезок,  образуемый  двумя  точками
a(x1,y)  и   b(x2,y),   можно   обозначать   как   ab  или  как
ab((x1,y),(x2,y)).
   Длиной вертикального отрезка ab((x1,y),(x2,y)) назовем число
x2-x1. Обозначать  длины  горизонтальных отрезков будем как Pab
или Pab((x1,y),(x2,y)). Таким образом, можно записать:
                 Pab((x1,y),(x2,y)) = x2-x1
   Будем считать, что  точка  t(t1,t2) на поле исполнителя при-
надлежит вертикальному отрезку ab((x1,y),(x2,y)), если:
                      x1 <= t1 <= x2
                      t2 = y
(через "<=" обозначен знак "меньше или равно")

 Задание.
   Буквы a и  b на поле исполнителя образуют горизонтальный от-
резок ab. В начальный момент Кукарача расположен на этом отрез-
ке сразу за буквой a.
   Написать программу,  которая поставит Кукарачу в нижний пра-
вый угол квадрата, построенного на  отрезке  ab  как на верхней
его стороне.
   Пример. При таком расположении букв a и b на поле:
                    1 2 3 4 5 6 7 8 9
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬
                 1 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 2 │ │a│¤│ │ │ │b│ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 3 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 4 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 5 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 6 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
                 7 │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼

Кукарача должен быть установлен в точку (7,7):

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


 Решение

   Несмотря на  очень  длинное  описание  задачи, решение очень
простое и короче самого условия в несколько раз.
   Алгоритмическая  идея:   рекурсивно  перемещать  исполнителя
вправо до буквы  b,  накапливая команду ВНИЗ. Когда исполнитель
толкнет кубик, поставить букву  b  на место и отпустить "пружи-
ну", заведенную на выполнение команд ВНИЗ.

─────────────────────────────┬──────────────────────────────────────────
                   рекурсия  │
ЭТО Квадрат   <─────────────┐│ Исполнитель идет вправо до буквы b,
 ВПРАВО                     ││ сжимая рекурсивную "пружину".
 ЕСЛИ b ТО Установкаb       ││ Процедура Установкаb возвращает букву b
 ИНАЧЕ Квадрат    ──────────┘│ на место.
 ВНИЗ         <──────────────┼─ Отложенная команда. Она сработает столько
КОНЕЦ                        │  раз, сколько сработала команда ВПРАВО.
                             │
// Букву b поставить на место│Возврат буквы b на место.
ЭТО Установкаb               │
 ВНИЗ                        │
 ПОВТОРИ 2 ВПРАВО            │
 ВВЕРХ                       │
 ВЛЕВО                       │
 ВНИЗ                        │
 ВЛЕВО                       │
КОНЕЦ                        │
─────────────────────────────┴─────────────────────────────────────
 Трассировка выполнения программы
────────────────────────────────┬─────────────────────────────────────
                                │
До начала работы программы      │  ..a¤...b..
                                │  ..........
                                │  ..........
                                │  ..........
                                │  ..........
                                │  ..........
                                │
Результат работы процедуры      │  ..a....¤b.  Исполнитель выполнил
Квадрат  в рекурсии по ветви    │  ..........  команду ВПРАВО четыре раза.
ИНАЧЕ:                          │  ..........  Соответственно запомнились
                                │  ..........  4 команды ВНИЗ.
ЭТО Квадрат   <────────┐        │  ..........
 ВПРАВО                │        │  ..........
 ЕСЛИ b ТО Установкаb  │        │
 ИНАЧЕ Квадрат  ───────┘        │
 ВНИЗ                           │
КОНЕЦ                           │
                                │
Когда  исполнитель  толкнул  b, │
управление передается в  проце- │
дуру Установкаb:                │
                                │
ЭТО Квадрат                     │
 ВПРАВО                         │
 ЕСЛИ b ТО Установкаb ──┐       │
 ИНАЧЕ Квадрат          │       │
 ВНИЗ                   │       │
КОНЕЦ                   │       │
                        │       │
┌───────────────────────┘       │
V                               │ ..a....b..   Среда после выполнения
ЭТО Установкаb                  │ .......¤..   процедуры Установкаb.
 ВНИЗ                           │ ..........
 ПОВТОРИ 2 ВПРАВО               │ ..........
 ВВЕРХ                          │ ..........
 ВЛЕВО                          │ ..........
 ВНИЗ                           │
 ВЛЕВО                          │
КОНЕЦ                           │
                                │
Рекурсия в процедуре Квадрат    │ ..a....b..   Среда после выполнения
закончилась. Теперь начинают    │ ..........   отложенных команд ВНИЗ.
работать отложенные команды     │ ..........
ВНИЗ. Этих команд накопилось    │ ..........
четыре.                         │ ..........
                                │ .......¤..
                                │
────────────────────────────────┴────────────────────────────────────────

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