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

5.2.1. Задача 1 (4 балла)
Средний бал решений: 3.6 (90%)

   Где-то  на  поле,  в  прямоугольнике,  образованном клетками
(1,3), (1,7), (9,3),  (9,7), расположен кубик с непустым симво-
лом.
   Найти этот кубик и переместить его в клетку (1,1). В началь-
ный момент исполнитель расположен в клетке (1,1).

    1 2 3 4 5 6 7 8 9 0
   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
 1 │¤│ │▒│▒│▒│▒│▒│ │ │ │  Прямоугольник, в котором может располагаться
   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤  символ, заштрихован.
 2 │ │ │▒│s│▒│▒│▒│ │ │ │  Сам символ "s" (в данном конкретном случае)
   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤  помещен в клетку (2,4)
 3 │ │ │▒│▒│▒│▒│▒│ │ │ │
   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 4 │ │ │▒│▒│▒│▒│▒│ │ │ │
   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 5 │ │ │▒│▒│▒│▒│▒│ │ │ │
   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 6 │ │ │▒│▒│▒│▒│▒│ │ │ │
   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 7 │ │ │▒│▒│▒│▒│▒│ │ │ │
   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 8 │ │ │▒│▒│▒│▒│▒│ │ │ │
   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 9 │ │ │▒│▒│▒│▒│▒│ │ │ │
   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 10│ │ │ │ │ │ │ │ │ │ │
   └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘


  Решение.

   1. Подвести исполнителя к прямоугольнику (в клетку 1,2).
   2. Для  каждой  строки прямоугольника  предусмотреть универ-
сальную процедуру Поиск1, перемещающую символ в последний стол-
бец этого прямоугольника.
   3. Применить  построенную  процедуру  для всех строк  прямо-
угольника.
   4. Сместить символ в последнем столбце прямоугольника в пер-
вую строку (в клетку (1,7)).
   5. Переместить символ из клетки  (1,7) в клетку (1,1).


 1. Подвод исполнителя выполняется одной командой ВПРАВО.

 2. Построение процедуры Поиск1.

   1) Сместить символ в строке в 7 столбец. Это достигается ко-
мандой: ПОВТОРИ 4 ВПРАВО.
    1 2 3 4 5 6 7 8 9 0
   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
 1 │ │¤┼─┼─┼─┼>│ │ │ │ │
   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 2 │ │ │ │s│ │ │ │ │ │ │
   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤

   2) Вернуться назад: ПОВТОРИ 4 ВЛЕВО

   А если символа в строке  нет?  Процедура  будет работать для
всех строк и в какой-нибудь строке символ точно найдется!
   Когда процедура  выполнится  для  всех строк прямоугольника,
символ будет обязательно находиться в седьмом столбце.

   Таким образом, процедура Поиск1 будет иметь вид:

ЭТО Поиск1
 ПОВТОРИ 4 ВПРАВО
 ПОВТОРИ 4 ВЛЕВО
КОНЕЦ


   3. Применение процедуру  Поиск1 для всех строк  прямо-
угольника:
ПОВТОРИ 9
{
  Поиск1      (*)
  ВНИЗ
}
   Команда ВНИЗ обеспечивает перемещение  Кукарачи  в следующую
строку для выполнения очередной команды Поиск1.

   4. Сместить символ в последнем столбце прямоугольника в пер-
вую строку (в клетку (1,7)).
   После  выполнения  цикла  (*)  Кукарача  застынет  в  клетке
(10,2). Теперь необходимо заставить его пройтись вверх по стол-
бцу 7, чтобы переместить символ в клетку (1,7):

ПОВТОРИ 5 ВПРАВО // Подвод исполнителя в 7 столбец
ПОВТОРИ 8 ВВЕРХ  // Прогулка по 7 столбцу

   5. Переместить символ из клетки  (1,7) в клетку (1,1).
   Теперь задача совсем простая: символ в клетке (1,7), а Кука-
рача в клетке (2,7):
    1 2 3 4 5 6 7 8 9 0
   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
 1 │ │ │ │ │ │ │s│ │ │ │
   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 2 │ │ │ │ │ │ │¤│ │ │ │
   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
 2 │ │ │ │ │ │ │ │ │ │ │
   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤

   Символ устанавливается на место следующими командами:
ВПРАВО
ВВЕРХ
ПОВТОРИ 6 ВЛЕВО

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

ЭТО Поиск
 // Подвод исполнителя к прямоугольнику
 ВПРАВО

 // Символ в столбец 7
 ПОВТОРИ 9 { Поиск1 ВНИЗ }
 // Подвод исполнителя в 7 столбец
 ПОВТОРИ 5 ВПРАВО

 // Прогулка по 7 столбцу
 ПОВТОРИ 8 ВВЕРХ

 // Символ из (1,7) в (1,1)
 ВПРАВО
 ВВЕРХ
 ПОВТОРИ 6 ВЛЕВО
КОНЕЦ

// Поиск в строке
ЭТО Поиск1
 ПОВТОРИ 4 ВПРАВО
 ПОВТОРИ 4 ВЛЕВО
КОНЕЦ

                      * * *

   Все присланные на  конкурс  решения  можно  разделить  на два
класса:

   - нерекурсивные
   - рекурсивные

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

Команда: 21
Авторы: Обухова Наташа, Плотникова Оля, Громов Алеша
Оценка: 3.5

   Рекурсивное решение, предложенное ребятами, имеет одну  пог-
решность: корректировка рекурсивного подъема кубика выводит Ку-
карачу в  11 строку в том  случае, если символ  располагается в
последней строке прямоугольника. Правда, ребята, для того, что-
бы избежать сообщения  "Не  могу", удлинили поле исполнителя на
одну строку. Однако, в удлинении поля нет необходимости.

Программа                               │ Комментарии куратора
────────────────────────────────────────┼──────────────────────────
ЭТО Возвращение_Беглеца                 │
 // Подойдем к границе прямоугольника   │
 ВПРАВО                                 │
                                        │
 // Найдем и вернем непустой кубик в    │
 // клетку (1,1)                        │
 Поиск_и_возврат                        │
КОНЕЦ                                   │
                                        │
//------------------------------------- │
// Проходим прямоугольник по            │
// горизонтали. В конце проверяем       │
// наличие непустого кубика. Если такой │
// есть, то передвигаем его в первый    │
// столбец и поднимаем вверх на         │
// "подсчитанное" количество шагов      │
//------------------------------------- │
ЭТО Поиск_и_возврат                     │
 ПОВТОРИ 5 ВПРАВО                       │
                                        │ Символ обнаружен! Он теперь в вось-
 ЕСЛИ НЕ ПУСТО                          │ мом столбце текущей  строки.  Пере-
  ТО                                    │ местим символ  в первый столбец,  а
    {                                   │ исполнитель   установим   под  ним.
     Подход_1                           │ Дальнейшую  работу  по  перемещению
     ПОВТОРИ 7 ВЛЕВО //В первый столбец │ символа  в  первую строку  выполнит
     Подход_2                           │ "рекурсивная пружина"
                                        │
     ВНИЗ            //Корректировка    │ Вот эта корректировка и мешает,
    }                                   │ когда кубик расположен в 9 строке.
  ИНАЧЕ                                 │
    {                                   │
     ПОВТОРИ 5 ВЛЕВО //Переход на сле-  │
     ВНИЗ            //дующую строку    │ Эта команда смещает исполнителя вниз
     Поиск_и_возврат //Повторяем работу │ по строкам.
    }                                   │
 // Отложенная команда выполняется      │
 // столько раз, сколько прошли пустых  │
 // строчек.                            │ Эта команда (рекурсивная пружина) по-
 ВВЕРХ                                  │ днимает исполнителя вверх по строкам.
КОНЕЦ                                   │
                                        │
//------------------------------------- │
ЭТО Подход_1                            │ Вспомогательные процедуры Подход_1
 ВНИЗ                                   │ и Подход_2 не слишком содержательны.
 ПОВТОРИ 2 ВПРАВО                       │ Можно было и не выделять эти действия
 ВВЕРХ                                  │ в отдельные процедуры.
КОНЕЦ                                   │
                                        │
//------------------------------------- │
ЭТО Подход_2                            │
 ВНИЗ                                   │
 ВЛЕВО                                  │
КОНЕЦ                                   │
-------------------------------------------------------------------------

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

ЭТО Возвращение_Беглеца
 ВПРАВО                                
 Поиск_и_возврат
КОНЕЦ                                  

ЭТО Поиск_и_возврат
 ПОВТОРИ 4 ВПРАВО // Проверка строки
 ЕСЛИ НЕ ПУСТО                         
  ТО    // Символ найден!              
    {                                  
     // Символ в первый столбец        
     ВНИЗ ВПРАВО ВПРАВО ВВЕРХ
     ПОВТОРИ 6 ВЛЕВО
     ВНИЗ ВЛЕВО
    }                                  
  ИНАЧЕ // Символа еще нет!            
    {
     ПОВТОРИ 4 ВЛЕВО  // В начало строки
     ВНИЗ             // На строку вниз
     Поиск_и_возврат  // Рекурсивный цикл

     ВВЕРХ  // Рекурсивная пружина.
    }       // Сработает правильно!
КОНЕЦ
