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

5.2.8. Задача 8 (9 баллов)
Средний бал решений: 5.6 (62%)

 Введем следующее определение выражения
Определение 4
-------------
<выражение> ::= <число>+<число> | <число>+<выражение>
<число>   ::= <цифра> | <число><цифра>
<цифра> ::= 0 | 1
   Задание. Напишите программу для Кукарачи, которая проверяет,
является ли запись  на его поле выражением в смысле определения
4.
   В начальный  момент  исполнитель расположен перед кубиками с
записью во второй строке:
                         ¤запись
   Если проверяемая запись - выражение, установить исполнитель в
конец записи:
                         запись¤
   Если запись - не выражение, поставить исполнитель под первым
неверным символом:
                         запись
                           ¤

Решение

   Из определения  следует, что выражением является запись сло-
жения нескольких  чисел  в  привычном  понимании  такой записи.
Только числами  являются не обычные числа, а последовательности
из нулей и единиц.
   Значит, выражениями не являются записи которые:
   - начинаются со знака "+";
   - кончаются знаком "+";
   - содержат внутри два знака "+" подряд;
   - не содержат в записи ни одного знака "+".

   Балл  за  оценку этой задачи, вероятно, был немного  завышен
куратором. Эта задача проще предыдущей, и решения ребят говорят
о том же.

   В качестве  "сырья"  для  изготовления программы этой задачи
хорошо подходит программа задачи 6. Изменить ее придется совсем
немного.

──────────────────────────┬──────────────────────────────────────────────
ЭТО Проверка              │ Проверка первого символа.
 Шаг                      │ Если это 0 или 1, то дальше будет
 ЕСЛИ       0 ТО Проверка0│ работать процедура Проверка0.
 ИНАЧЕ ЕСЛИ 1 ТО Проверка0│ Любой другой первый знак - ошибка.
 ИНАЧЕ Ошибка             │ Так программируем обработку
КОНЕЦ                     │ ошибочного знака "+" на первом месте в записи.
                          │
ЭТО Проверка0             │ Эта процедура проверяет запись "на цифры",
 Шаг                      │ пока не встретит:
 ЕСЛИ  ПУСТО  ТО Выражение│ - пустую клетку: запись - выражение;
 ИНАЧЕ ЕСЛИ 0 ТО Проверка0│
 ИНАЧЕ ЕСЛИ 1 ТО Проверка0│
 ИНАЧЕ ЕСЛИ + ТО Проверка1│ - знак "+": следующий знак не должен быть снова
 ИНАЧЕ Ошибка             │   знаком "+" - это проверит процедура Проверка1
КОНЕЦ                     │
                          │
ЭТО Проверка1             │ Эта процедура проверяет следующий знак за
 Шаг                      │ знаком "+" в записи. Этот знак обязан быть цифрой.
 ЕСЛИ       0 ТО Проверка0│ Если знак - цифра, управление возвращается
 ИНАЧЕ ЕСЛИ 1 ТО Проверка0│ процедуре Проверка0 для продолжения работы.
 ИНАЧЕ Ошибка             │
КОНЕЦ                     │
                          │
ЭТО Шаг                   │
 ВНИЗ                     │
 ВПРАВО                   │
 ВВЕРХ                    │
КОНЕЦ                     │
                          │
ЭТО Выражение             │
 ВВЕРХ                    │
КОНЕЦ                     │
                          │
ЭТО Ошибка                │
 Шаг                      │
 ЕСЛИ НЕ ПУСТО ТО Ошибка  │
 ВЛЕВО                    │
КОНЕЦ                     │
                          │
──────────────────────────┴──────────────────────────────────────────────

   Итак, процедура  Проверка, начиная работу, посмотрит, не яв-
ляется ли первый знак в записи знаком "+".
   Процедура Проверка1,  начнет работу после того, как исполни-
тель толкнул знак "+" и не пропустит:
   - два знака "+" подряд;
   - знак "+" последним в записи (ведь она выдает ошибку и тог-
да, когда за знаком "+" следует пустая клетка).
   Так хорошо  будут  работать  совместно процедуры Проверка0 и
Проверка1, дополняя друг-друга!
   Неплохая программа, правда?
   Так  и  думал куратор, когда ее писал.  Однако,  он  ошибся!
Программа неправильная:  она  считает выражением число, то есть
запись из нулей и единиц, в которой нет ни одного  знака сложе-
ния. Это выяснилось при тестировании, и  конечно, пришлось вно-
сить исправления.

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

   Теперь построим решение, используя метод построения  синтак-
сической диаграммы.

<выражение> ::= <число>+<число> | <число>+<выражение>
<число>   ::= <цифра> | <число><цифра>
<цифра> ::= 0 | 1


                  ┌─────────>  (ошибка) <───────────┐
                  │              ^                  │
                  │              │                  │
        остальное │              │остальное         │
                  │              │                  │
                  │     0,1      │                  │
       ┌────> (число) <──────  (вход)               │
       │  0,1   │ │                                 │
       └────────┘ │                                 │
                  │                                 │
                  │+                                │
                  │                                 │
                  V          остальное              │
  ┌────────> (выражение?) ────────────────────────>─┤
  │               │                                 │
  │               │0,1                              │
  │               │                                 │
  │               V          остальное              │
  │   ┌────> (выражение) ─────────────────────────>─┘
  │   │ 0,1   │  │    │
  │   └───────┘  │+   │пусто
  │              │    │
  └──────────────┘    V
                    (ответ выражение)

Перевод схемы на язык программирования:

ЭТО вход
 шаг
 ЕСЛИ       0 ТО число
 ИНАЧЕ ЕСЛИ 1 ТО число
 ИНАЧЕ           ошибка
КОНЕЦ

ЭТО число
 шаг
 ЕСЛИ       0 ТО число
 ИНАЧЕ ЕСЛИ 1 ТО число
 ИНАЧЕ ЕСЛИ + ТО выражение?
 ИНАЧЕ           ошибка
КОНЕЦ

ЭТО выражение?
 шаг
 ЕСЛИ       0 ТО выражение
 ИНАЧЕ ЕСЛИ 1 ТО выражение
 ИНАЧЕ           ошибка
КОНЕЦ

ЭТО выражение
 шаг
 ЕСЛИ       0     ТО выражение
 ИНАЧЕ ЕСЛИ 1     ТО выражение
 ИНАЧЕ ЕСЛИ +     ТО выражение?
 ИНАЧЕ ЕСЛИ ПУСТО ТО ответ_выражение
 ИНАЧЕ               ошибка
КОНЕЦ

ЭТО ответ_выражение
 ВВЕРХ
КОНЕЦ

ЭТО шаг
 ВНИЗ ВПРАВО ВВЕРХ
КОНЕЦ

ЭТО ошибка
 шаг
 ЕСЛИ НЕ ПУСТО ТО ошибка
 ВЛЕВО
КОНЕЦ

                            * * *


   Верные решения для  этой  задачи создали четыре команды: 13,
20, 24, 30. Это большой прогресс по сравнению  с предыдущей за-
дачей, в которой не было ни одной до  конца правильной програм-
мы.
   Типичные ошибки.
   1) Программы считают  выражениями записи которые  начинаются
со знака "+" и (или) заканчиваются знаком "+".
   2) В том случае, когда запись - число, исполнитель показыва-
ет ошибку на  его последней цифре,  а нужно: на  первую  пустую
клетку.
