Авторские решения задач

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

Ваши решения лучше уже потому, что они ВАШИ собственные!

А мои решения лучше тем, что они понятнее выглядят и старательнее
оформлены. У меня, конечно, было на это больше времени, чем у вас.
Я старался сделать алгоритмы и программы понятнее для вас, но не только!

В описании решений одной из команд руководитель пишет:

"В некоторых задачах понять логику ребят оказалось не просто 
 не только руководителям, но и самим исполнителям :-)."

Получается, что даже через несколько дней (или часов, минут) юные программисты
уже не понимали СВОИ СОБСТВЕННЫЕ алгоритмы или программы! 
Даже в турнирной спешке все-таки стОило писать структурно, красиво
и не пренебрегать комментариями! При проверке работ вы это почуствуете.


Буду благодарен всем, кто укажет мне на ошибки  и вообще за любые суждения.


Задача 1 "Сколько палочек?"
Описание алгоритма

  Накапливать количество палочек будем в ящике.  Для этого вна-
чале запишем в ящик число  "0".  Передвигаясь  вправо по записи
палочек (пока они не кончатся), на каждом шаге увеличиваем чис-
ло-символ в  ящике на единицу. Дойдя до конца  записи, пишем после нее
знак "=" и символ из ящика.

Имя файла с программой 001.kor

Описание программы

ЭТО Вход              │
 ПИШИ 0 ОБМЕН ВПРАВО  │  Подготовка ящика, окно на начало записи
 ПОКА НЕ ПУСТО        │  Цикл от первой до последней палочки
 {                    │
  ОБМЕН ПЛЮС ОБМЕН    │  увеличиваем число в ящике на единицу
  ВПРАВО              │  перемещаем окно на следующий символ
 }                    │
 ПИШИ = ВПРАВО ОБМЕН  │  Дойдя до конца записи, оформляем результат
КОНЕЦ                 │

Задача 2 "Поиск максимума"
Описание алгоритма

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

Имя файла с программой 002.kor
Описание программы

ЭТО Вход            │
 ЯЩИК+              │ Первый символ в ящик
 ПОКА НЕ ПУСТО      │
 {                  │
  ПИШИ ПУСТО        │ Удаляем символ
  ВПРАВО            │ К следующему символу
  ЕСЛИ Я<Л ТО ЯЩИК+ │ Сравнение
 }                  │
 ОБМЕН              │ Результат на ленту
КОНЕЦ               │

Задача 3 "Символ в число"
Описание алгоритма

Если в окошке не цифра, значит, символ изображает число,
которое, по крайней мере, больше 9. Значит, можно смело
уменьшить его на 10 и добавить в разряд десятков единицу.
Если опять НЕ ЦИФРА, действуем также. Типичный случай
применения цикла ПОКА.

Имя файла с программой 003.kor
Описание программы

ЭТО Вход            │
 ПОКА НЕ ЦИФРА      │
  {                 │
   ПОВТОРИ 10 МИНУС │
   ВЛЕВО            │
   ЕСЛИ НЕ ПУСТО    │
    ТО ПЛЮС         │ Добавление в разряд десятков единицы
    ИНАЧЕ ПИШИ 1    │ Запись первого десятка
   ВПРАВО           │
  }                 │
КОНЕЦ               │


Задача 4 "Среднее арифметическое"
Описание алгоритма
Вычислять полусумму (решение "в лоб") не очень рационально,
т.к. для этого придется одно из чисел уменьшать до нуля.
Особенно много лишней работы, если это "число" достаточно
большое, например "$".  К тому же сумма может превысить вели-
чину "@" (что, впрочем, не должно караться согласно предисловию
к задачам).

  В моем  алгоритме  реализована другая очевидная идея: меньшее
число увеличивать на единицу, а большее число уменьшать на еди-
ницу, (как бы  двигаться навстречу), пока не получим равные или
соседние символы.
  Для  этого  необходимо сначала  "разобраться",  какой  символ
"меньше". Например, поместить меньший символ в  ящик, а больший
оставить на ленте, как в предлагаемой процедуре "Вход".
  "Сближая" числа,  надо  не пропустить момент, когда получатся
не равные, но соседние символы. То есть на  каждом шаге "сближе
ния" делать две проверки: после  уменьшения  бОльшего  числа  и
после увеличения меньшего.

  Небольшая хитрость состоит в том, чтобы закончить цикл "сбли-
жения" и в том случае, когда  результат - один символ, и в том,
когда два. Нужно просто подвинуть окошко на тот символ, при ко-
тором цикл закончится (выполнится условие Я=Л).

Алгоритм пригоден ДЛЯ ЛЮБЫХ двух символов из алфавита Корректора.


Имя файла с программой 004.kor
Описание программы

ЭТО Вход                               
 ЯЩИК+                     │ Первое число
 ПИШИ ПУСТО                │ убрали в ящик
 ВПРАВО                    │
 ЕСЛИ Я=Л                  │ Числа равны- ответ готов
  ТО { ПИШИ ПУСТО ОБМЕН }  │
  ИНАЧЕ                    │
 {                         │ меньшее число
  ЕСЛИ Я>Л  ТО ОБМЕН       │ в ящик
  Сближение                │
 }                         │
КОНЕЦ
                                       
ЭТО Сближение                   │
 ПОКА Я#Л                       │
  {                             │
   МИНУС                        │
   ЕСЛИ Я=Л                     │ Найдены сосед-
    ТО                          │ ние символы
    { ВПРАВО ЯЩИК- ПЛЮС ВЛЕВО } │
    ИНАЧЕ                       │ Продолжить
    { ОБМЕН ПЛЮС ОБМЕН }        │ "сближение"
  }                             │
КОНЕЦ                                  

Задача 5 "Разгадай шифр 1"
Описание алгоритма

Разгадка шифра : каждый символ заменяется "симметричным" ему символом
относительно середины алфавита Корректора, т.е. "ш" заменяется на "щ",
"ч"- на "ъ" и т.д. ... "0"- на "@" (и наоборот).

Чтобы реализовать алгоритм расшифровки, нужно сначала сравнить символ
на ленте с символом "ш" (как в предлагаемой программе), или с символом
"щ". Если символ окажется "левее" середины, рекурсивно "отсчитываем",
наскОлько левее (увеличивая его до "ш"), и отложенной командой "ПЛЮС"
получаем зашифрованный. Совершенно аналогично "отражаем" относительно "ш"
символы, расположенные "правее" середины.

Имя файла с программой 005.kor
Описание программы

ЭТО Вход        │
 ПИШИ ш ОБМЕН   │ "ш" в ящик для сравнения
 ВПРАВО         │
 ПОКА НЕ ПУСТО  │ Цикл по всем символам
 {              │
  ЕСЛИ  Я>Л     │
   ТО    Вперед │ Символ в левой части алфавита
   ИНАЧЕ Назад  │ Символ в правой части или ш
  ПЛЮС          │
  ВПРАВО        │
 }              │
КОНЕЦ           │

ЭТО Вперед
 ПЛЮС                      │ Увеличиваем "число" до ш
 ЕСЛИ Я#Л ТО Вперед        │
 ПЛЮС                      │ Находим симметричное
КОНЕЦ                      │

ЭТО Назад                  │
 ЕСЛИ Я#Л                  │
  ТО { МИНУС Назад МИНУС } │Уменьшаем "число" до ш
КОНЕЦ                      │и находим симметричное

Задача 6 "Разгадай шифр 2"
Описание алгоритма
Разгадка шифра: попарно поменять местами рядом стоящие
символы: первый со вторым, третий с четвертым и т.д.
Единственный нюанс (надеюсь, его все учли), что при нечетном
количестве символов последний символ остается на месте, т.к.
его не с чем менять местами. Проблема решается просто:
цикл ПОКА НЕ ПУСТО следует начинать со второго символа.

Имя файла с программой 006.kor
Описание программы

ЭТО Вход             │
 ВПРАВО              │ На второй символ
 ПОКА НЕ ПУСТО       │
 {                   │
  ЯЩИК+ ВЛЕВО ОБМЕН  │ Меняем местами
  ВПРАВО ОБМЕН       │ с предыдущим
  ПОВТОРИ 2 ВПРАВО   │ к след. паре
 }                   │
 ПОВТОРИ 2 ВЛЕВО     │ Установка окна
 ПОКА НЕ ПУСТО ВЛЕВО │ на начало
 ВПРАВО              │
КОНЕЦ                │

Задача 7 "Умножение"
Описание алгоритма
Предлагается заменить произведение а*b суммой из b
одинаковых слагаемых, равных  а: а*b=а+а+...а.

Идея сложения двух чисел описана в курсовом пакете:

нц пока первое число не 0
│ уменьшить первое число на 1
│ увеличить второе число на 1
кц

При многократном сложении придется позаботиться о том, чтобы
"первое" число (превращаемое в 0) было сохранено для следующего
сложения (например, на ленте).
Количесво сложений, равное (b-1), запоминается с помощью
рекурсивной процедуры "Умножение", в которой откладывается
нужное количество вызовов процедуры сложения "Ящик+лента".

"Вырожденные" случаи умножения на 0 и на 1 прописаны отдельно
в процедуре "Умножать_не_надо".


Имя файла с программой 007.kor
Описание программы

ЭТО Вход
 Меньшее_вперед
 ВЛЕВО ПИШИ 1 ЯЩИК+    │  Единицу в ящик
 ПИШИ ПУСТО ВПРАВО     │  для сравнения
                       │
 ЕСЛИ НЕ Я<Л           │  Множитель <=1
  ТО Умножать_не_надо  │
  ИНАЧЕ                │
  {                    │
   ВПРАВО ЯЩИК+ ВЛЕВО  │ Сохранение копии второго числа
   Умножение           │
   ВЛЕВО ПИШИ ПУСТО    │  Уборка мусора
   ЯЩИК+ ВПРАВО        │  и окно на результат
  }                    │
КОНЕЦ

ЭТО Меньшее_вперед         │ Перестановка
 ЯЩИК+ ВПРАВО              │ символов
 ЕСЛИ Я>Л                  │ в порядке
  ТО { ОБМЕН ВЛЕВО ЯЩИК- } │ возрастания
  ИНАЧЕ ВЛЕВО              │
КОНЕЦ                      │

ЭТО Умножать_не_надо │
 ЕСЛИ 0              │ Умножение на 0
  ТО                 │
  {                  │
   ВПРАВО ПИШИ ПУСТО │
   ЯЩИК+ ВЛЕВО       │
  }                  │
  ИНАЧЕ              │ Умножение на 1
  {                  │
   ПИШИ ПУСТО        │
   ЯЩИК+ ВПРАВО      │
  }                  │
КОНЕЦ                │

ЭТО Умножение <───┐     │
 ЕСЛИ НЕ 1        │     │
  ТО              │     │
  {               │     │
   МИНУС          │     │
   Умножение ─────┘     │
   Лента+ящик           │ Сложение
   ВЛЕВО ЯЩИК+ ВПРАВО   │ Восстановление первого
  }                     │ сомножителя
  ИНАЧЕ { ЯЩИК- ВПРАВО }│
КОНЕЦ                   │

Задача 8 "Деление с остатком"
Описание алгоритма
  Заменим  деление   a/b   вычитанием   делителя  из  делимого:
(((a-b)-b)-b... Вычитание продолжаем до тех пор,  пока не полу-
чим результат меньше делителя. Этот результат и есть остаток от
деления, а количество вычитаний - округленное в меньшую сторону
частное.
  Основной алгоритм получится такой:
с:=0
нц пока не а<b
│ а:=а-b
│ с:=с+1
кц
  После его  выполнения  величина  с содержит результат деления
нацело, величина а -  остаток  от деления. Особые случаи деления
(на 0 и на 1) описываются отдельно.

Имя файла с программой 008.kor
Описание программы

Если делимое- не 0 и не 1, вызыватся процедура "Деление",
реализующая описанный алгоритм. Само вычитание и прибавление
к единице оформлено процедурой "Работа", которая вызывается
в цикле ПОКА НЕ Я<Л. В момент проверки условия Я<Л в ящике
делитель, на ленте делимое или результат очередного вычитания.

ЭТО Вход                       │
 ВПРАВО                        │
 ЕСЛИ       0 ТО Ошибка        │ Особые случаи
 ИНАЧЕ ЕСЛИ 1 ТО Ответ-делимое │ деления
 ИНАЧЕ           Деление       │
КОНЕЦ                          │

ЭТО Деление                   │
  ПОВТОРИ 2 ВЛЕВО             │
  ЯЩИК+                       │ Сохранение
  ВЛЕВО ЯЩИК-                 │ делимого на ленте
  ПОВТОРИ 5 ВПРАВО            │
  ПИШИ 0                      │ Заготовка для частного
  ПОВТОРИ 2 ВЛЕВО             │
  ЯЩИК+                       │
  ПОВТОРИ 2 ВЛЕВО             │
  ПОКА НЕ Я>Л Работа          │ Вычитание делителя
  ВЛЕВО ЯЩИК+ ПИШИ ПУСТО      │ Восстановление
  ВПРАВО ОБМЕН                │ делимого
КОНЕЦ                         │
                                       
ЭТО Работа                    │
 ОБМЕН                        │
 ПОКА НЕ 0                    │
 {                            │
  МИНУС ОБМЕН МИНУС ОБМЕН     │
 }                            │
 ОБМЕН                        │
 ПОВТОРИ 4 ВПРАВО             │ Увеличение
 ПЛЮС                         │ частного на 1
                              │
 ПОВТОРИ 2 ВЛЕВО ЯЩИК+        │ Подготовка
 ПОВТОРИ 2 ВЛЕВО              │ к вычитанию
КОНЕЦ                         │

Задача 9 "Возведение в степень"

Описание алгоритма
Возведение в степень заменим последовательным умножением:
а^n = а*а*...*а.
Алгоритм и программу для умножения используем из задачи 7,
а для перевода в десятичный вид- из задачи 3.
Если показатель степени не 0 и не 1 (эти особые случаи
описываются отдельно), то выписываем n раз на ленту основание степени
и организуем запуск программы из задачи 7 для двух "чисел", стоящих
на ленте слева. Умножение даст число, которое будет первым сомножителем
для следующего умножения и т.д.

Имя файла с программой 009.kor
Описание программы
ЭТО Вход                               
 ОБМЕН                                 
 ПИШИ 1                                
 ОБМЕН
 ВПРАВО                                
 ЕСЛИ Я<Л                │ Показатель степени > 1
  ТО                     │
  {                      │
   Разложение            │Выписать на ленту основание степени
                         │нужное количество раз
   Перемножение          │Попарное умножение
  }                      │
  ИНАЧЕ                  │ Особые случаи
  {                      │
   ЕСЛИ 1                             │
    ТО ПОВТОРИ 2 { ПИШИ ПУСТО ВЛЕВО } │ первая степень
    ИНАЧЕ                             │
    {                                 │
     ПОВТОРИ 2 { ПИШИ ПУСТО ВЛЕВО }   │ нулевая степень
     ПИШИ 1                           │
    }                                 │
  }                                   │
  Перевод                             │ символ в число (задача 3)
КОНЕЦ                                  
                                       
ЭТО Разложение <──┐ │ Рекурсивная процедура
 МИНУС            │ │ для записи первого числа
 ЕСЛИ НЕ 0        │ │ в количестве, равном
  ТО              │ │ второму числу
  {               │ │
   Разложение ────┘ │
   ЯЩИК-            │ Отложенные команды
   ВПРАВО           │ записи на ленту
  }                 │
  ИНАЧЕ             │
  {                 │
   ПИШИ ПУСТО ВЛЕВО │ Уборка мусора
   ПИШИ ПУСТО       │
   ВЛЕВО            │
   ЯЩИК+            │ Первое число в ящик
   ВПРАВО           │ для копирования на ленту
  }                 │
КОНЕЦ               │
                                       
ЭТО Перемножение<─┐ │ К началу записи
 ВЛЕВО            │ │ с запоминанием количества
 ЕСЛИ НЕ ПУСТО    │ │ умножений
  ТО              │ │
  {               │ │
   Перемножение ──┘ │
   Умножить         │ Вызов программы умножения
  }                 │ двух стоящих рядом "чисел" (задача 7)
  ИНАЧЕ ВПРАВО      │
КОНЕЦ               │


Задача а "Сократить дробь"
Описание алгоритма
  Для сокращения  дроби  требуется найти наибольший общий дели-
тель (НОД) для  исходных  чисел. Алгоритм Евклида и реализующая
его программа для Корректора взяты из  курсового пакета (турнир
2000-2001 года,  автор программы Данила Первушин из Снежинска).
Когда НОД найден и если он не равен 1, реализуется деление обо-
их чисел по алгоритму задачи 8 нынешнего турнира.


Имя файла с программой 00a.kor
Описание программы

ЭТО Вход                        │
 ВПРАВО                         │
 ЕСЛИ       0 ТО Ошибка         │ Особые случаи
 ИНАЧЕ ЕСЛИ 1 ТО Ответ=Делимому │ деления
  ИНАЧЕ                         │
  {                             │
   ВЛЕВО ВЛЕВО                  │
   ЕСЛИ 0     ТО Ответ=0        │ Особые случаи
   ИНАЧЕ ЕСЛИ 1 ТО ВПРАВО       │ деления
   ИНАЧЕ Работа                 │
  }                             │
КОНЕЦ                           │
                                       
ЭТО Работа                │
 ВПРАВО                   │
 Вычисление_НОД           │
 ЕСЛИ НЕ 1                │
  ТО                      │ Деление обоих
  {                       │ чисел на НОД
   ЯЩИК+ ВЛЕВО            │
   Деление                │
   ВПРАВО ЯЩИК+           │
   ПИШИ ПУСТО             │
   ПОВТОРИ 2 ВЛЕВО ЯЩИК-  │
   ВЛЕВО                  │
   Деление                │
   ВПРАВО ПИШИ /          │
  }                       │
  ИНАЧЕ                   │
  {                       │
   ПИШИ ПУСТО             │
   ПОВТОРИ 2 ВЛЕВО        │
  }                       │
КОНЕЦ                     │


Задача b "Антиавтомат"
Описание алгоритма

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

Пример: 50-25-24-12-6-3-2-1-0
          *  +  *  * * + * +

  Таким образом, для решения задачи нужно исходное число делить
на 2 (если оно четное)  или  уменьшать на 1 (если нечетное)  до
тех пор,  пока не получим 1. (1, а не 0 - потому что первая ко-
манда в программе автомата  всегда  +). При этом каждое деление
добавляет  в  программу Автомата "*", а каждое вычитание-  "+".

  Главная пробема - определение четности. Предлагается вычитать
из числа по 2, пока не  получится 1 или 0. Перед тем, как прев-
ращать число в 0  или в 1, запоминаем его в ящике  для последу-
ющего деления на 2 или вычитания единицы.

  Сначала я применил цикл ПОКА НЕ 1 и каждый раз "гонял" окошко
Корректора в начало  записи программы и обратно к "числу"... Но
чудесное свойство рекурсивного стека  позволило-  таки отложить
запись программы "на потом" и  выписать  символы  в один проход
после всех вычитаний и делений!

Получилась такая косвенная рекурсия :

┌──────────────────┐   ┌────────────────┐    ┌──────────────┐
│Вход              │ ┌─> Работа <────┐  │ ┌──> Нечетное     │
│Если еще не 1 то────┘ │ Вычитаем 2  │  │ │  │ Вычитаем 1   ├─┐
│иначе все, отпус- │   │ если > 1 то─┘  │ │  │ Откладываем +│ │
│каем пружины!     │   │ иначе если 1 то──┘  └──────────────┘ │
└──────────────────┘   │ иначе если 0 то──┐  ┌──────────────┐ │
       ^     ^         └───────────────┘  └──> Четное   ┌─┐ │ │
       │     │                               │ Делим на 2─┘ │ │
       │     │                               │ Откладываем *│ │
       │     │                               └──────┬───────┘ │
       │     └──────────────────────────────────────┘         │
       └──────────────────────────────────────────────────────┘

Кроме этого, сама "Работа" и деление на 2 тоже рекурсивные.
Итого четыре переплетенных рекурсивных кольца. 


Имя файла с программой 00b.kor
Описание программы

  Процедуры "Вход",  "Работа",  "Нечетное"  или "Четное" образуют
рекурсивные цепочки. Они вызывают друг друга, пока не превратят
число в  1 путем  деления на 2 и вычитания  единицы. При этом в
стеке откладываются команды записи на ленту "*" и "+".

ЭТО Вход <────────────────────────┐
 ЕСЛИ       0 ТО ПИШИ ПУСТО       │
 ИНАЧЕ ЕСЛИ 1 ТО ПИШИ +           │
 ИНАЧЕ           { ЯЩИК+ Работа } │
КОНЕЦ   ┌──────────────────┘      │
        V                         │
ЭТО Работа <───────────────────┐  │
 МИНУС МИНУС                   │  │ │ Вычитаем 2 до тех
 ЕСЛИ       1 ТО Нечетное ─┐   │  │ │ пор, пока не получим
 ИНАЧЕ ЕСЛИ 0 ТО Четное ── │─┐ │  │ │ 0 или 1.
 ИНАЧЕ           Работа ── │ │─┘  │
КОНЕЦ                      │ │    │
                           │ │    │
ЭТО Нечетное  <────────────┘ │    │  │
 ЯЩИК- МИНУС                 │    │  │ Вычесть единицу
 Вход  ───────────────────────────┘  │ На начало
 ВПРАВО ПИШИ + │ Отложенные  │    ^  │ Запомнить +
КОНЕЦ          │ команды     │    │  │
                             │    │
ЭТО Четное  <────────────────┘    │  │
  ЯЩИК-                           │  │
  Дели_на_2                       │  │ Разделить на 2
  Вход  ──────────────────────────┘  │ На начало
  ВПРАВО ПИШИ *│ Отложенные          │ Запомнить *
КОНЕЦ          │ команды             │

ЭТО Дели_на_2 <──────────┐   │
 МИНУС МИНУС             │   │  Вычитаем по 2,
 ЕСЛИ НЕ 0 ТО Дели_на_2 ─┘   │
 ПЛЮС                        │  а прибавляем по 1
КОНЕЦ                        │

Задача c "Скобки"
Описание алгоритма

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

Имя файла с программой 00c.kor
Описание программы

Программу хорошо поясняет диаграмма переходов:

  ┌──────────────┐    ┌────────────┐
  │  ┌──────┐  ┌─V────V─┐          │
  │  │ Вход ├──>Проверка│          │
  │  └──────┘  └┬──┬───┬┘          │
  │            (│пусто │)          │
  │      ┌──────┴─┐│┌──┴─────────┐ │
  │      │Левая   │││Правая      │ │
  │      │Счетчик+│││Если сч>0 то│ │
  │      └───┬────┘││Счетчик- ───┼─┘  ┌─────────┐
  └──────────┘     ││иначе ──────┼────>Ошибка   │
                   │└────────────┘    └─^───────┘
      ┌──┐      ┌──┴─┐                  │
      │Ок├─сч=0─┤Итог├─счетчик не = 0───┘
      └──┘      └────┘



ЭТО Вход        │
 ПИШИ 0 ОБМЕН   │Подготовка счетчика скобок
 Проверка       │
КОНЕЦ           │
                                       
ЭТО Проверка                           
 ВПРАВО                                
 ЕСЛИ       (     ТО Левая             
 ИНАЧЕ ЕСЛИ )     ТО Правая            
 ИНАЧЕ ЕСЛИ ПУСТО ТО Итог              
 ИНАЧЕ Проверка                        
КОНЕЦ                                  
                                       
ЭТО Левая          │
 ОБМЕН ПЛЮС ОБМЕН  │ Увеличить счетчик на 1
 Проверка          │
КОНЕЦ              │
                                       
ЭТО Правая                       │
 ОБМЕН                           │
 ЕСЛИ 0                          │ Непарная скобка
  ТО    { ОБМЕН Ошибка }         │
  ИНАЧЕ { МИНУС ОБМЕН Проверка } │ Уменьшить счетчик на 1
КОНЕЦ                                  
                                       
ЭТО Итог                              │
 ВПРАВО                               │
 ОБМЕН                                │
 ЕСЛИ 0                               │ Проверка баланса
  ТО { ПИШИ о ВПРАВО ПИШИ к ВЛЕВО }   │ скобок
  ИНАЧЕ                               │
  { ПИШИ о ВПРАВО ПИШИ ш ВЛЕВО ВЛЕВО }│
КОНЕЦ                                  

Задача d "Проверка выражения"

Определение:
<Выражение> ::= <Цифра> | <Скобки> | <Выражение>+<Выражение>
<Скобки>    ::= (<Цифра>+<Цифра>)
<Цифра>     ::=0|1|2|3|4|5|6|7|8|9

Диаграмма переходов

┌───────────┐  ┌────────────────────────────────────────────────┐
│         ┌─V──V───┐                                            │
│         │  Вход  │                                            │
│         └┬───┬──┬┘                                            │
│      ┌─ц─┘  во  └─(───┐                                       │
│  ┌───V──┐    │      ┌─V─────┐ ┌───────┐ ┌───────┐ ┌───────┐   │
│  │Цифра │    │      │Скобки1├ц>Скобки2├+>Скобки3├ц>Скобки4│   │
│  └┬─┬─┬─┘    │      └─┬─────┘ └─┬─────┘ └─┬─────┘ └─┬──┬──┘   │
└─+─┘ │ └─во┐  │        во        во        во        во )      │
    пусто   │  │  ┌─────┴─────────┴─────────┴─────────┘  │      │
      │    ┌┴──V──V┐                              ┌──────V─────┐│
      │    │Ошибка │                              │После_скобок││
      │    └──────^┘                              └┬──┬───┬────┘│
      │           └─────────────────────────────во─┘  │   └ + ──┘
      └──────┐      ┌────────────────────────────пусто┘
           ┌─V──────V┐
           │Выражение│     "ц"  означает "цифра",
           └─────────┘     "во" означает "все остальное"

  Описание алгоритма лексического анализатора после составления
диаграммы переходов  просто не требуется. Состояния диаграммы в
точности соответствуют  процедурам программы.

Имя файла с программой 00c.kor
Описание программы

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

ЭТО Прибавь <───────┐ │
 ЕСЛИ НЕ 0          │ │
  ТО                │ │
  {                 │ │
   МИНУС            │ │Уменьшение цифры на 1
   ОБМЕН ПЛЮС ОБМЕН │ │Добавление 1 к ящику
   Прибавь ─────────┘ │
   ПЛЮС               │"Пружинка" для восстановления
  }                   │числа на ленте
КОНЕЦ                 │


  Процедура "Ошибка" (автор А.А.Дуванов) рекурсивно передвигает
окошко в конец записи, пишет на ленту сообщение "ош" и отложен-
ной командой ВЛЕВО возвращает окно на место ошибки:

ЭТО Ошибка <─────┐             │
 ВПРАВО          │             │ До конца записи
 ЕСЛИ НЕ ПУСТО   │             │
  ТО Ошибка   ───┘             │
  ИНАЧЕ                        │
  {                            │
   ВПРАВО ПИШИ о ВПРАВО ПИШИ ш │ Сообщение об ошибке
   ПОВТОРИ 2 ВЛЕВО             │ и возврат к концу записи
  }                            │
 ВЛЕВО                         │ "Пружинка" для возврата
КОНЕЦ                          │

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

ЭТО Вход                               
 ВПРАВО                                
 ЕСЛИ       ЦИФРА ТО Цифра             
 ИНАЧЕ ЕСЛИ (     ТО Скобки1           
 ИНАЧЕ               Ошибка            
КОНЕЦ

ЭТО Цифра                              
 Прибавь                               
 ВПРАВО                                
 ЕСЛИ       +     ТО Вход              
 ИНАЧЕ ЕСЛИ ПУСТО ТО Выражение         
 ИНАЧЕ               Ошибка            
КОНЕЦ                                  
                                       
ЭТО Скобки1                            
 ВПРАВО
 ЕСЛИ ЦИФРА ТО { Прибавь Скобки2 }     
 ИНАЧЕ           Ошибка
КОНЕЦ                                  

ЭТО Скобки2                            
 ВПРАВО                                
 ЕСЛИ + ТО Скобки3                     
 ИНАЧЕ     Ошибка                      
КОНЕЦ                                  
                                       
ЭТО Скобки3
 ВПРАВО
 ЕСЛИ ЦИФРА ТО { Прибавь Скобки4 }     
 ИНАЧЕ           Ошибка                
КОНЕЦ                                  
                                       
ЭТО Скобки4                            
 ВПРАВО                                
 ЕСЛИ ) ТО После_скобок                
 ИНАЧЕ     Ошибка                      
КОНЕЦ                                  

ЭТО После_скобок                       
 ВПРАВО
 ЕСЛИ       +     ТО Вход              
 ИНАЧЕ ЕСЛИ ПУСТО ТО Выражение
 ИНАЧЕ               Ошибка            
КОНЕЦ                                  
                                       
ЭТО Выражение
 ПИШИ = ВПРАВО ОБМЕН ПЛЮС              
КОНЕЦ                                  
