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

5.2.1. Задача 2 (5 баллов)
Средний бал решений: 4.0 (81%)

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

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

   Решение.

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

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


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

Замечание 2 о программирование переключателей
---------------------------------------------

   В своих  работах  школьники  часто записываю переключатели в
виде:

ЕСЛИ 4 ТО ВНИЗ
ЕСЛИ 5 ТО ПОВТОРИ 2 ВНИЗ
ЕСЛИ 6 ТО ПОВТОРИ 3 ВНИЗ              (вариант 1)
ЕСЛИ 7 ТО ПОВТОРИ 4 ВНИЗ
ЕСЛИ 8 ТО ПОВТОРИ 5 ВНИЗ
ЕСЛИ 9 ТО ПОВТОРИ 6 ВНИЗ

   Настоятельно рекомендуется записывать переключатели так:

ЕСЛИ       4 ТО ВНИЗ
ИНАЧЕ ЕСЛИ 5 ТО ПОВТОРИ 2 ВНИЗ
ИНАЧЕ ЕСЛИ 6 ТО ПОВТОРИ 3 ВНИЗ        (вариант 2)
ИНАЧЕ ЕСЛИ 7 ТО ПОВТОРИ 4 ВНИЗ
ИНАЧЕ ЕСЛИ 8 ТО ПОВТОРИ 5 ВНИЗ
ИНАЧЕ ЕСЛИ 9 ТО ПОВТОРИ 6 ВНИЗ


   В чем смысл сделанной рекомендации?:

   1) Текст варианта 2 будет работать быстрее.
   2) Текст варианта 1 может привести к ошибкам.

   Разъяснение.

   1) Если какая-то проверка привела к положительному результа-
ту, то остальные  проверки не будут работать в тексте программы
варианта 2 и будут работать в тексте программы варианта 1.
   2) Из разъяснения 1) следует, что лишние проверки могут при-
вести к ошибке в работе программы.
   Пример.
Если число равно 5, увеличить его на 1.
Если число равно 6, увеличить его на 2.
В остальных случаях оставить число без изменения.

                     Решение
 вариант 1                 │вариант 2
 ЕСЛИ x = 5 ТО x := x + 1  │ЕСЛИ x = 5 ТО x := x + 1
 ЕСЛИ x = 6 ТО x := x + 2  │ИНАЧЕ ЕСЛИ x = 6 ТО x := x + 2
                           │
   Если переменная x  имела значение 5, то после выполнения ле-
вого кода она получит неожиданное значение  8,  то  есть  будет
увеличена не на один, а на три!
   Код справа работает правильно.
   Для этой кукарачинской задачи  текст  варианта 1 к ошибке не
приведет, но  лучше  сразу учиться писать правильные алгоритми-
ческие конструкции!
