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

5.2.3. Задача 3 (7 баллов)
Средний бал решений: 5.9 (84%)

   В одной строке  поля расположены кубики с символами так, что
между ними есть пустое пространство -  две  или  больше  пустых
клеток. Известно, что среди кубиков  есть  только  один кубик с
символом "!", и он - самый последний. Написать программу, кото-
рая уплотняет символы - сдвигает их в строке так, чтобы все они
шли подряд без промежутков. В начальный момент исполнитель рас-
положен сразу за первым символом.
   Пример начальной установки среды:
                    1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─
                 1 │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
                 2 │ │л│¤│ │и│ │ │ │с│ │ │а│ │ │!│
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─

   Среда после выполнения программы:
                    1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
                   ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─
                 1 │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
                 2 │ │л│и│с│а│!│¤│ │ │ │ │ │ │ │ │
                   ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─


  Решение

   Исполнитель должен  работать  (уплотнять запись), пока не не
встретит знака "!". В силу этого логично основную процедуру за-
писать так:

ЭТО Уплотнение
 ПОКА НЕ ! Уплотнение1
КОНЕЦ                                  

   Что же должна делать процедура Уплотнение1?
   Эта процедура  должна  "уплотнить  один символ" - придвинуть
его вплотную к предыдущему и поместить исполнителя за ним, при-
готавливая его к очередному витку цикла ПОКА.
   Рассмотрим результаты выполнений процедуры Уплотнить1 в цик-
ле ПОКА:

│ │л│¤│ │и│ │ │ │с│ │ │а│ │ │!│  до работы программы
                                 условие в ПОКА истинно

│ │л│и│¤│ │ │ │ │с│ │ │а│ │ │!│  первое выполнение процедуры Уплотнить1
                                 условие в ПОКА истинно (толкали назад не "!")


│ │л│и│c│¤│ │ │ │ │ │ │а│ │ │!│  второе выполнение процедуры Уплотнить1
                                 условие в ПОКА истинно (толкали назад не "!")

│ │л│и│c│а│¤│ │ │ │ │ │ │ │ │!│  третье выполнение процедуры Уплотнить1
                                 условие в ПОКА истинно (толкали назад не "!")

│ │л│и│c│а│!│¤│ │ │ │ │ │ │ │ │  четвертое выполнение процедуры Уплотнить1
                                 условие в ПОКА стало ложным (толкали назад "!")

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

                  рекурсия
ЭТО Уплотнение1  <─────────┐│
 ВПРАВО                    ││Шаг вперед!
                           ││
 ЕСЛИ НЕ ПУСТО             ││Проверим, был ли кубик.
                           ││
  ТО Поставить             ││Ага! Толкнули кубик. Надо ставить его на место.
                           ││Процедура Поставить установит Кукарачу справа от
                           ││кубика, а уж "толчки" назад выполнит "автоматом"
                           ││отложенная команда ВЛЕВО ────────────┐
                           ││                                     │
  ИНАЧЕ Уплотнение1 ───────┘│Кубика нет! Рекурсивно идем дальше.  │
                            │                                     │
 ВЛЕВО                      │Вот оно, отложенное безумие!   < ────┘
КОНЕЦ                       │
                            │
ЭТО Поставить               │ Ну, эта процедурка просто заводит исполнителя
  ВНИЗ                      │ за кубик, изготавливая Кукарачу перед работой
  ПОВТОРИ 2 ВПРАВО          │ отложенной команды ВЛЕВО.
  ВВЕРХ                     │
  ВЛЕВО                     │
КОНЕЦ                       │

   Теперь посмотрим, как выглядит эта программа целиком:

ЭТО Уплотнение
 ПОКА НЕ ! Уплотнение1
КОНЕЦ

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

ЭТО Поставить
  ВНИЗ
  ПОВТОРИ 2 ВПРАВО
  ВВЕРХ
  ВЛЕВО
КОНЕЦ

                      * * *

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

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

                    * * *

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

   В качестве примера рекурсивной программы, уплотняющей запись
целиком, приведем следующее решение:

ЭТО Уплотнение
 ВПРАВО
 ЕСЛИ НЕ !
   ТО
    {
      ЕСЛИ НЕ ПУСТО ТО Петля
      Уплотнение
    }
   ИНАЧЕ Петля
 ВЛЕВО
КОНЕЦ

ЭТО Петля
 ВНИЗ
 ПОВТОРИ 2 ВПРАВО
 ВВЕРХ
 ВЛЕВО
КОНЕЦ
