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

5.2.7. Задача 7 (9 баллов)
Средний бал решений: 4.7 (51%)

 Введем следующее определение числа:
Определение 3
-------------
<число>   ::= <целое> | <дробь>
<целое>   ::= <цифра> | <целое><цифра>
<дробь>   ::= <простая> | <десятичная>
<простая> ::= <целое>/<целое>
<десятичная> ::= .<целое> | <целое>. | <целое>.<целое>
<цифра>   ::= 0 | 1

   Задание. Напишите программу для Кукарачи, которая проверяет,
является ли запись на его поле числом в смысле определения 3.
   В начальный  момент  исполнитель расположен перед кубиками с
записью во второй строке:
                         ¤запись
   Если проверяемая  запись  -  число, установить исполнитель в
конец записи:
                         запись¤
   Если запись - не число, поставить исполнитель под первым не-
верным символом:
                         запись
                           ¤

Решение

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

Примеры неверных записей        │ Примеры верных записей
(исполнитель показывает ошибку) │(исполнитель в конце проверенной записи)
────────────────────────────────┼────────────────────────────────────────
.                               │.1¤
 ¤                              │
                                │
..                              │1.¤
 ¤                              │
                                │
.1.                             │0.0¤
  ¤                             │
                                │
2                               │1¤
¤                               │
                                │
2.1                             │101.011¤
¤                               │
                                │
1.2,3                           │1/0¤
  ¤                             │
                                │
/1                              │000/000¤
¤                               │
                                │
1/                              │
  ¤                             │
                                │
./                              │
 ¤                              │
                                │
1/0/1                           │
   ¤                            │
                                │
1.0/1                           │
   ¤                            │

   Замечание. Заметим, что в смысле определения, выражение типа
"1/0" числом является. Определение есть определение, оно не мо-
жет быть неправильным, если не нарушена его внутренняя логика.
   А уж, что понимать под числом "1/0" - это совсем другой воп-
рос, уводящий нас от построения конструкции к описанию ее смыс-
ла. (Например, под числами с нулем в знаменателе можно понимать
обозначение бесконечности).

   Эти примеры  являются необходимым (но не достаточным!) набо-
ром тестов для проверки работоспособности программы.

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

   Сначала рассмотрим решение этой задачи, без привлечения син-
таксических диаграмм.

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

   Программа выглядит  достаточно  большой, но записать ее было
просто на базе программы для задачи 6. Фактически ничего нового
писать и  не пришлось: дополнительные строки получились копиро-
ванием текста программы 6 и внесением в них небольших правок.
   Однако, задача оказалась достаточно коварной для  участников
турнира (нет ни одного правильного решения).  Прежде всего, это
связано с недостаточно  точным  пониманием определения 3 и, ко-
нечно, с недостаточно тщательным тестированием программы  перед
отправкой на конкурс.

   Второе  решение  запишем, предварительно  построив диаграмму
переходов.
┌───────────────────────────────┐
│                               V
│           (ответ число)    (ошибка) <─────────────┐
│               ^             ^ ^                   │
│               │  остальное  │ │                   │
│         пусто │ ┌───────────┘ │ остальное         │
│               │ │             │                   │
│               │ │     0,1     │                   │
│     ┌────── (целое) <───────(вход)                │
│     │       ^ │   │           │                   │
│     │       │ │   │           │                   │
│     │ 0,1   │ │   │.          │.                  │
│     └───────┘ │   │           │                   │
│         ┌─────┘   │           V      остальное    │
│         │/        │     (десятичная?)─────────────┤
│         │         │           │                   │
├───── (простая?)   │        0,1│      остальное    │
│остальное │        │           │  ┌────────────────┘
└───────┐  │        │           V  │
        │  │0,1     └─────>(десятичная)────┐
        │  V                    │  ^       │
┌────> (простая)                │  │       │
│      │       │                │  │  0,1  │
│0,1   │       │пусто     пусто │  └───────┘
└──────┘       │                │
               │                V
               └───────> (ответ число)

   Замечание. На схеме повторяется состояние "ответ число". Это
сделано для того, чтобы не рисовать длинных линий с пересечени-
ями. Это состояние, конечно, существуют в одном экземпляре.
   Схема переписывается в следующую программу:

ЭТО вход                           │Состояние (вход)
 шаг                               │Смотрим следующий символ
 ЕСЛИ        0 ТО целое            │
 ИНАЧЕ ЕСЛИ  1 ТО целое            │
 ИНАЧЕ ЕСЛИ  . ТО десятичная?      │
 ИНАЧЕ ошибка                      │
КОНЕЦ                              │
                                   │
ЭТО целое                          │Состояние (целое)
 шаг                               │Смотрим следующий символ
 ЕСЛИ       ПУСТО ТО ответ_число   │
 ИНАЧЕ ЕСЛИ 0     ТО целое         │
 ИНАЧЕ ЕСЛИ 1     ТО целое         │
 ИНАЧЕ ЕСЛИ .     ТО десятичная    │
 ИНАЧЕ ЕСЛИ /     ТО простая?      │
 ИНАЧЕ               ошибка        │
КОНЕЦ                              │
                                   │
ЭТО десятичная?                    │Состояние (десятичная?)
 шаг                               │Смотрим следующий символ
 ЕСЛИ       0     ТО десятичная    │
 ИНАЧЕ ЕСЛИ 1     ТО десятичная    │
 ИНАЧЕ               ошибка        │
КОНЕЦ                              │
                                   │
ЭТО десятичная                     │Состояние (десятичная)
 шаг                               │Смотрим следующий символ
 ЕСЛИ       ПУСТО ТО ответ_число   │
 ИНАЧЕ ЕСЛИ 0     ТО десятичная    │
 ИНАЧЕ ЕСЛИ 1     ТО десятичная    │
 ИНАЧЕ               ошибка        │
КОНЕЦ                              │
                                   │
ЭТО простая?                       │Состояние (простая?)
 шаг                               │Смотрим следующий символ
 ЕСЛИ       0     ТО простая       │
 ИНАЧЕ ЕСЛИ 1     ТО простая       │
 ИНАЧЕ               ошибка        │
КОНЕЦ                              │
                                   │
ЭТО простая                        │Состояние (простая)
 шаг                               │Смотрим следующий символ
 ЕСЛИ       ПУСТО ТО ответ_число   │
 ИНАЧЕ ЕСЛИ 0     ТО простая       │
 ИНАЧЕ ЕСЛИ 1     ТО простая       │
 ИНАЧЕ               ошибка        │
КОНЕЦ                              │
                                   │
ЭТО ошибка                         │
 шаг                               │Перемещение остатка записи
 ЕСЛИ НЕ ПУСТО ТО ошибка           │в первую строку
 ВЛЕВО                             │Возврат к месту ошибки
КОНЕЦ                              │
                                   │
ЭТО ответ_число                    │
 ВВЕРХ                             │
КОНЕЦ                              │
                                   │
ЭТО шаг                            │Проверка следующего
 ВНИЗ ВПРАВО ВВЕРХ                 │символа
КОНЕЦ                              │

