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

6.2.3. Задача 3 (9 баллов)
Средний бал решений: 5.7 (63 %)

 Введем следующее определение:
Определение
-----------
<выражение> ::= <число> | <выражение>+<число>
<число>   ::= 0 | 1 | 2

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

   В начальный момент окошко расположено перед записью.

   Примеры работы программы:

Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┐
│░│░║░║1│+│2│░│░│░│░│    ─────>     │░│░│░│1│+│2║=║3│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┘
Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┐
│░│░║░║1│░│░│░│░│░│░│    ─────>     │░│░│░│1║=║1│░│░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┘

Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐
│░│░║░║1│.│7│+│1│░│░│    ─────>     │░│░│░│1║.║7│+│1│░│о│ш│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘


   Решение.

 Диаграмма переходов здесь очень проста:

           ПУСТО                0,1,2         остальное
 (ответ) <────── (выражение) <──────── (вход) ──────────> (ошибка)
                     │   │               ^
                     │   │ +             │
            остальное│   │               │
(ошибка) <───────────┘   └───────────────┘


   Однако, нам нужно не просто проверить выражение, но и вычис-
лить его.  Поэтому в программе появляются дополнительные проце-
дуры, связанные не  с переходом в другие состояния алгоритма, а
с вычислениями.

ЭТО вход0                      │ Эта процедура подготавливает  ящик  для
 ОБМЕН                         │ вычислений  перед  входом  в  состояние
 ПИШИ ПУСТО                    │ (вход) алгоритма.
 ОБМЕН                         │
 вход                          │
КОНЕЦ                          │
                               │
ЭТО вход                       │ Состояние (вход)
 ВПРАВО                        │ Смотрим следующий символ.
 ЕСЛИ       0 ТО выражение     │ Если это 0, переходим в состояние (выражение)
 ИНАЧЕ ЕСЛИ 1 ТО добавить1     │ без вычислений. Если 1 или 2, перед переходом
 ИНАЧЕ ЕСЛИ 2 ТО добавить2     │ в состояние (выражение) "добавим" число в ящик.
 ИНАЧЕ ошибка                  │ Любой другой символ в состоянии
КОНЕЦ                          │ (вход) - ошибка.
                               │
ЭТО выражение                  │ Состояние (выражение)
 ВПРАВО                        │ Смотрим следующий символ.
 ЕСЛИ       +     ТО вход      │ Если это "+", переходим в состояние (вход) -
 ИНАЧЕ ЕСЛИ ПУСТО ТО ответ     │ выражение продолжается.
 ИНАЧЕ ошибка                  │ Если это ПУСТО, выражение закончилось.
КОНЕЦ                          │ Любой другой символ - ошибка.
                               │
ЭТО добавить1                  │ Вспомогательная переходная процедура
 ОБМЕН                         │ между состояниями (вход) и (выражение).
 ПЛЮС                          │ В ней к ящику "добавляется" 1.
 ОБМЕН                         │
 выражение                     │
КОНЕЦ                          │
                               │
ЭТО добавить2                  │ Вспомогательная переходная процедура
 ОБМЕН                         │ между состояниями (вход) и (выражение).
 ПЛЮС ПЛЮС                     │ В ней к ящику "добавляется" 2.
 ОБМЕН                         │
 выражение                     │
КОНЕЦ                          │
                               │
ЭТО ошибка                     │ Идем рекурсивно от ошибочного символа
 ВПРАВО                        │ до конца записи, сжимая рекурсивную пружину.
 ЕСЛИ ПУСТО                    │ Записываем в конце записи сообщение об ошибке
  ТО ответ_ошибка              │ и под воздействием энергии сжатой пружины
  ИНАЧЕ ошибка                 │ возвращаем окно на место ошибки.
 ВЛЕВО                         │
КОНЕЦ                          │
                               │
ЭТО ответ_ошибка               │ Сообщение об ошибке.
 ВПРАВО ПИШИ о                 │
 ВПРАВО ПИШИ ш                 │
 ПОВТОРИ 2 ВЛЕВО               │
КОНЕЦ                          │
                               │
ЭТО ответ                      │ Подготовка к записи значения выражения
 ВПРАВО ВПРАВО                 │ в виде числа на ленту.
 ПИШИ 0                        │ Алгоритм: к числу 0 на ленте прибавлять 1,
 ответ1                        │ а символ в ящике заменять на предыдущий, пока
КОНЕЦ                          │ в ящике не окажется символ ПУСТО.
                               │
ЭТО ответ1                     │ Запись результата вычислений.
 ПОКА НЕ ПУСТО ВПРАВО          │ Установить окошко на последний символ
 ВЛЕВО                         │ текущего значения результата.
 ОБМЕН                         │ Посмотреть, что в ящике.
 ЕСЛИ НЕ ПУСТО                 │ Если в ящике нет символа ПУСТО:
  ТО                           │ - заменить символ в ящике на предыдущий;
  {                            │ - к текущему результату на ленте прибавить 1;
    МИНУС                      │ - повторить алгоритм с самого начала
    ОБМЕН                      │
    плюс1                      │
    ответ1                     │
  }                            │ Если в ящике символ ПУСТО, формирование
  ИНАЧЕ ответ2                 │ результата закончено. Остается записать
КОНЕЦ                          │ перед ним символ "=" и закончить работу.
                               │
ЭТО ответ2                     │
  ОБМЕН                        │
  ПОКА НЕ ПУСТО ВЛЕВО          │
  ПИШИ =                       │
КОНЕЦ                          │
                               │
ЭТО плюс1                      │ Процедура добавления единицы к числу на ленте.
 ЕСЛИ 9 ТО    девять           │ В начальный момент окошко должно быть
        ИНАЧЕ ПЛЮС             │ установлено на последний символ числа.
КОНЕЦ                          │
                               │
ЭТО девять                     │
 ПОКА 9 { ПИШИ 0 ВЛЕВО }       │
 ЕСЛИ НЕ ЦИФРА                 │
   ТО    ПИШИ 1                │
   ИНАЧЕ ПЛЮС                  │
КОНЕЦ                          │


Из анализа присланных на конкурс работ
-------------------------------------

   Большинство  программ,  присланных  на конкурс, работало  по
многопроходным алгоритмам.  Это  означает, что при работе прог-
раммы запись просматривается не один раз, а несколько, что, ко-
нечно, не является оптимальным.

Команда 320 (Бычков Анатолий Владимирович)
|||||||||||
Оценка: 9
Авторы решения: Меденников Антон, Субботин Дима

Авторское описание алгоритма.
    В ящик записываем 0 - начинаем накапливать сумму. Далее про-
верка числа и знака "+" после него (или пусто). В конце записи -
знак "=" и запись результата.  Под  запись  результата отводим 2
клетки (замечание 2). Если результат  <  10,  делаем сдвиг числа
влево.

Комментарий куратора.

   Очень хорошее  описание  алгоритма  (общее  выше) и детальное
справа от текста программы в текстовом файле.
   Хорошо комментировать программу не так-то легко. Обычные ком-
ментарии, которые  любят  вставлять  в программные коды новички,
типа

ВПРАВО // Перемещаем окно на одну клетку вправо

просто вредны. Они замусоривают текст программы, не давая  ника-
кой новой информации.
   Комментарии Антона и Димы другого рода:

 ПИШИ 0                       //   "Обнуляем счетчик"
 ОБМЕН                        //
 ...                          //
 ВЛЕВО                        //  Если число < 10, сдвинем
 ЕСЛИ ПУСТО ТО { ВПРАВО ЯЩИК+ //  его влево.
 ...                          //
 ВЛЕВО                        //   "Пружина"  "помнит", где
                              //   ошибка.

   Такие комментарии  помогают  легко понять текст программы и,
как ни странно,  помогают  программировать. На самом деле, ком-
ментарии пишутся не для проверяющих, а для себя.

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

ЭТО Плюс1
 ЕСЛИ НЕ 9 ТО { ЕСЛИ ПУСТО ТО ПИШИ 1    Перевод суммы из ящика в
                 ИНАЧЕ ПЛЮС }           обычное десятичное число
  ИНАЧЕ { ПИШИ 0 ВЛЕВО Плюс1 ВПРАВО }   на ленту
КОНЕЦ


Команда 324 (Пинженина Софья Владимировна)
|||||||||||
Оценка: 7.5
Авторы программы: Хлызов Иван, Волков Алексей, Савинков Дмитрий.

   Программа показывает ошибку в записи  "1+"  на  знак "+", что
неверно.
