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

5.2.6. Задача 6 (8 баллов)
Средний бал решений: 5.1 (63%)

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

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

1)   1010¤

2)   121.34
      ¤
3)   .00¤

4)   .10.0
        ¤

   Решение

   Из определения следует, что числом является  любая запись из
нулей и единиц, и, кроме того, любая запись из нулей,  единиц и
одной точки. Но, если точка в записи есть, то длина записи дол-
жна быть больше единицы!

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

   Неверной записью является  также  пустая запись, то есть от-
сутствие каких-либо символов.

   Эти примеры  являются необходимым (но не достаточным!) набо-
ром тестов для проверки работоспособности программы.
   К сожалению, тест из  записи,  состоящей из одного символа -
точки - привел к краху всех программ, присланных на конкурс.
   У одной команды  этот  тест, правда, проходит, но, вероятно,
случайно, потому как почти ничего больше не работает.
   Заметим, что когда запись - точка, исполнитель должен указы-
вать не на нее, а  на  пустую клетку за ней: ошибка  начинается
именно там, в пустой  клетке,  сама точка ошибочным символом не
является.

   Сначала приведем вариант решения  дух  которого присутствует
во всех решениях, присланных на конкурс. Суть его в следующем:

   - отдельно проверяем первый символ (процедура Проверка);
   - проверяем остальные  символы  до  точки  или пустой клетки
     (процедура Проверка0);
   - проверяем остаток записи после точки (процедура Проверка1).

   Распределение проверки по трем процедурам совершенно обосно-
вано: нужно отдельно проверить первый символ, а когда обнаруже-
на точка, нужно помнить, что она была и вторую точку рассматри-
вать как ошибку.  У  исполнителя нет памяти, поэтому приходится
компенсировать это лишней процедурой.

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

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

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


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

