5.2. Решения и комментарии

                  История Корректора
   Корректор, как и Кукарача,  переехал  в Переславль-Залесский
из Благовещенска (дальневосточный город, центр Амурской  облас-
ти, граница с Китаем). Этот исполнитель  был придуман А.А.Дува-
новым двумя годами позже Кукарачи в 1986 году.
   В этом же  году была подготовлена рукопись книги "Введение в
программирование. Корректор" со следующим посвящением:
                                 "Посвящается моим студентам.
                                  Как тем, кто верит в чудеса
                                  кибернетики, так и тем, кто
                                  упорно считает ее лженаукой."
   И, конечно, благодарностями:
   "Автор выражает  благодарность своим друзьям и коллегам, без
помощи которых  Корректор  не  увидел  бы  свет: О.Г.Какаулину,
А.В.Ситникову, А.А.Евладову, С.В.Медведеву, З.А.Пан, О.А.Щерби-
ной. С их помощью рукопись была подготовлена к  печати всего за
три недели."
   Чудесные иллюстрации  для книги были созданы Александром Мо-
розовым.
   Однако, эта рукопись так и не появилась в печати. Как  раз в
этом году Дуванов переехал из Благовещенска в Переславль-Залес-
ский и поступил на работу в Институт программных систем АН СССР
(директор Альфред  Карлович  Айламазян)  в лабораторию школьной
информатики, которую возглавил, приехав в Переславль из Новоси-
бирска, Юрий Абрамович Первин.
   В Переславле закипела работа над  новыми  идеями  на  уровне
творческих безумств  и вдохновения, съедающего все время. Руко-
пись сначала  просто была положена в  "стол", а потом  на время
забыта.
   Тем не менее,  Корректор был одной из самых первых программ,
реализованных на Ямахе  и вошедших в самую раннюю версию Робот-
ландии. В дальнейшем, при переносе Роботландии сначала на УКНЦ,
а затем на PC, Корректор остался на старой квартире. Мы не ста-
ли  включать  Корректор в новые версии Роботландии, потому  что
его  программирование выходило  за  рамки  общеобразовательного
курса информатики для младших школьников, носило факультативный
характер и предназначалось для детей, которые хотели заниматься
именно программированием.  На  пристройку  к Роботландии кружка
юных  натуралистов  от программирования не было сил и  времени:
нужно было разрабатывать и опробовать в школьных классах, став-
шие теперь традиционными, роботландские общеобразовательные те-
мы.
   Только  в  1992  году,  когда  для  издательства  "Педагоги-
ка-Пресс" готовилась книга "Необычайные приключения Пети Кука в
Роботландии" (авторы А.Дуванов, Ю.Первин), рукопись по  Коррек-
тору была извлечена из картонной  коробки  и  использована  при
подготовке четырех глав Петиных приключений.
   Второй семестр  Роботландских Курсов дал новую жизнь Коррек-
тору. Семестр был  задуман  именно как "кружок юных программис-
тов", объединяющий маленьких фанатов этого сказочного  действа.
Рекурсивные  опусы  Кукарачи  в Корректоре получили  логические
продолжение, более оправданное в его псевдотьюринговской среде,
чем на клетчатом поле коллеги.

      Замечание об опасности использования переключателя
                 без ключевого слова ИНАЧЕ
   Проверка работ показала, что часто авторы решений используют
опасное программирование переключателя без ключевого слова ИНА-
ЧЕ. Рассмотрим такую задачу.
   Задача. Через окошко на ленте  видна  цифра.  Заменить ее на
другую цифру - дополнение до 9.

НЕВЕРНОЕ решение.
ЭТО Замена1
 ЕСЛИ 0 ТО ПИШИ 9
 ЕСЛИ 1 ТО ПИШИ 8
 ЕСЛИ 2 ТО ПИШИ 7
 ЕСЛИ 3 ТО ПИШИ 6     (*)
 ЕСЛИ 4 ТО ПИШИ 5
 ЕСЛИ 5 ТО ПИШИ 4
 ЕСЛИ 6 ТО ПИШИ 3     (**)
 ЕСЛИ 7 ТО ПИШИ 2
 ЕСЛИ 8 ТО ПИШИ 1
 ЕСЛИ 9 ТО ПИШИ 0
КОНЕЦ

   Пусть на ленте записана цифра 3. Тогда сначала сработает ве-
точка ТО в команде (*) и цифра 3 заменится цифрой 6. Затем сра-
ботает веточка ТО команды (**) и цифра 6 заменится снова цифрой
3.  Понятно,  что программа правильно работает только для  цифр
больших 5. Цифры 0-4 она сохранит на ленте без изменений.

ВЕРНОЕ решение.
ЭТО Замена2
 ЕСЛИ       0 ТО ПИШИ 9
 ИНАЧЕ ЕСЛИ 1 ТО ПИШИ 8
 ИНАЧЕ ЕСЛИ 2 ТО ПИШИ 7
 ИНАЧЕ ЕСЛИ 3 ТО ПИШИ 6
 ИНАЧЕ ЕСЛИ 4 ТО ПИШИ 5
 ИНАЧЕ ЕСЛИ 5 ТО ПИШИ 4
 ИНАЧЕ ЕСЛИ 6 ТО ПИШИ 3
 ИНАЧЕ ЕСЛИ 7 ТО ПИШИ 2
 ИНАЧЕ ЕСЛИ 8 ТО ПИШИ 1
 ИНАЧЕ           ПИШИ 0
КОНЕЦ

   Второй вариант лучше первого по времени исполнения.
   Например, если на ленте записана цифра 0, то программа Заме-
на2 выполнит только  одну  проверку, а программа Замена1 всегда
выполняет 10 проверок.  Программа Замена2 в любом случае не вы-
полнит больше 9 проверок и только один раз команду ПИШИ.

       Самые общие впечатления о задачах Корректора,
            их решении и проверке решений.

   Программирование для Корректора существенно сложнее програм-
мирования для Кукарачи. Об  этом  говорит и число команд, прис-
лавших работы 2 тура  - 20 (из 64, подавших заявки на  работу в
Курсах). Однако, эти 20 команд прислали решения, которые демон-
стрируют глубокие теоретические познания и практические умения.
   Существенно более сложной и трудоемкой (по сравнению с Кука-
рачей) является проверка и анализ чужих  программ. Учитывая по-
вышенную сложность  проверки,  мы предложили на этапе перекрес-
тного контроля только  3  работы (в конкурсе Кукарачи предлага-
лось  6).  Однако, не все проверки были выполнены  качественно.
Некоторые команды прислали  только  одни таблички с баллами без
всяких комментариев.  По  комментариям других было понятно, что
проверяющие не вникали  в алгоритм автора задачи, а лишь прове-
ряли "устойчивость"  работы  программы  на разных тестах. Часто
указывался тест,  на котором программа работает некорректно, но
не причины, которые привели к "краху" решения.

               Решение задач и анализ работ

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


   Задача 1.

   Идея алгоритма: переносить символы не вправо, а влево от ис-
ходного текста:

              дубль_наоборот исходный_текст

   Программа.

//--------------------- |
ЭТО Дубль_наоборот      |
 ПОКА НЕ ПУСТО          | Цикл по всем символам исходного текста
 {                      |
   ЯЩИК+                | Запоминаем  очередной  символ в  ящике,
   Перенос              | переносим его на новое место и сдвигаем
   ВПРАВО               | окно к следующему символу.
 }                      |
 Удалить_старое_слово   | Стираем с ленты исходное слово.
КОНЕЦ                   |
//--------------------- | Перенос одного  символа на новое место и воз-
ЭТО Перенос             | врат на  прежнее место в исходном тексте. Ал-
 ВЛЕВО                  | горитм: сдвигаем окно влево до пустого симво-
 ЕСЛИ ПУСТО             | ла, затем устанавливаем символ (он в ящике) в
  ТО Установка          | начало нового текста-дубля-наоборот.
  ИНАЧЕ Перенос         |
 ВПРАВО                 | Эта команда обеспечивает возврат в исходное
КОНЕЦ                   | место в начальном тексте.
//--------------------- |
ЭТО Установка           | Установка символа  (он  в  ящике) слева перед
 ВЛЕВО                  | формируемым текстом-дублем-наоборот и возврат
 ПОКА НЕ ПУСТО ВЛЕВО    | на символ ПУСТО, отделяющий дубль от исходно-
 ЯЩИК-                  | го текста.
 ПОКА НЕ ПУСТО ВПРАВО   |
КОНЕЦ                   |
//--------------------- |
ЭТО Удалить_старое_слово| Замена всех символов исходного текста
 ВЛЕВО                  | символом ПУСТО.
 ПОКА НЕ ПУСТО          |
 {                      |
  ПИШИ ПУСТО            |
  ВЛЕВО                 |
 }                      |
КОНЕЦ                   |
//--------------------- |

Анализ работ.
   В целом задача не вызвала затруднений.
   О внешнем виде программ: в ряде представленных решений прог-
рамма становится трудно читаемой из-за того, что авторы записы-
вали свои  процедуры заглавными буквами (текст программы стано-
виться слишком однородным: ключевые слова, команды  СКИ и имена
процедур плохо выделяются в тексте).

   Решение Ялышева  Влада (команда 09, г.Пермь) восхищает своей
рекурсивной остроумностью: для поиска правильного места очеред-
ного символа в перевертыше и для возврата окна  в текущее поло-
жение в исходном слове  используются  соответственно отложенные
команды ВПРАВО и ВЛЕВО.

 Решение Влада.

//--------------------- |
ЭТО Обратно             |
 Поставить_флаг         | Установка символа "@" в конце слова.
 ПОКА НЕ @ Копировать   | Формирование "перевертыша".
КОНЕЦ                   |
//--------------------- |
ЭТО Поставить_флаг      |
 ПОКА НЕ ПУСТО ВПРАВО   |
 ПИШИ @                 |
 ПОКА НЕ ПУСТО ВЛЕВО    |
 ВПРАВО                 |
КОНЕЦ                   |
//--------------------- |
ЭТО Копировать          |
 ЯЩИК+                  | Очередной символ слова  помещается в ящик.
 Символ                 | Перемещение окна к  нужному месту. Вставка
 ЯЩИК-                  | символа  в  слово-"перевертыш". Возврат  к
 Символ_2               | текущему месту в  исходном слове. Смещение
 ВПРАВО                 | к следующему символу в исходном слове.
КОНЕЦ                   |
//--------------------- |
ЭТО Символ              | Эта процедура находит для символа
 ВПРАВО                 | правильное место в "перевертыше".
 ЕСЛИ НЕ @ ТО Символ    |
 ВПРАВО                 |
КОНЕЦ                   |
//--------------------- |
ЭТО Символ_2            | Эта процедура устанавливает  окно на преж-
 ВЛЕВО                  | нее место в исходном слове.
 ЕСЛИ НЕ @ ТО Символ_2  |
 ВЛЕВО                  |
КОНЕЦ                   |
//--------------------- |


   Задача 2.

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

   Идея алгоритма (на примере слова "кок").

   Подготовительная работа

┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬
│░│░║к║о│к│░│░│░│░│░│     Исходная начальная среда
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴

┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬     Процедура: "Записать=".
│░║░║к│о│к│=│░│░│░│░│     В конец слова допишем символ "=" и устано-
┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴     вим окно на первый пустой символ слева.

┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬     Процедура: "Дубль".
│░│░│к│о│к║=║к│о│к│░│     В  конец текста  допишем  копию  исходного
┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴     слова.

┬─┬─┬─┬─┬─┬─┬─┬─┬─╦═╦     Команда: "ПОКА НЕ ПУСТО ВПРАВО".
│░│░│к│о│к│=│к│о│к║░║     Устанавливаем окно на первый пустой символ
┴─┴─┴─┴─┴─┴─┴─┴─┴─╩═╩     за дублем.

   Основная работа (процедура "Сравнить_символы")
   Сравниваем по символам дубль и начальное слово. Символ в дубле
берется с конца, символ в исходном слове - с начала.
    ┌─┐
    │к│
    └─┘
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐
│░│░║к║о│к│=│к│о│░│░│    Первая проверка
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘
      ┌─┐
      │о│
      └─┘
┬─┬─╥─╦═╦─┬─┬─┬─┬─┬─┐
│░│░║░║о║к│=│к│░│░│░│    Вторая проверка
┴─┴─╨─╩═╩─┴─┴─┴─┴─┴─┘
        ┌─┐
        │к│
        └─┘
┬─┬─╥─╥─╦═╦─┬─┬─┬─┬─┐
│░│░║░║░║к║=│░│░│░│░│    Третья проверка
┴─┴─╨─╨─╩═╩─┴─┴─┴─┴─┘

┬─┬─╥─╥─┬─╦═╦─┬─┬─┬─┐
│░│░║░║░│░║=║░│░│░│░│    Проверка закончена
┴─┴─╨─╨─┴─╩═╩─┴─┴─┴─┘

Программа.

//---------------------    |
ЭТО Палиндром              |
 Записать=                 |
 Дубль                     |
 ПОКА НЕ ПУСТО ВПРАВО      |
 Сравнить_символы          |
КОНЕЦ                      |
//---------------------    |
ЭТО Сравнить_символы       | Перемещаем окно влево по символам дубля
  ВЛЕВО                    | пока не обнаружим символ "=" или несовпадение
  ЕСЛИ НЕ =                | символов при проверке.
   ТО                      |
  {                        | Помещаем в ящик очередной символ
    Взять_символ           | (стирая его с ленты)
    Сравнить               | Сравниваем символ в ящике с первым символом
    ЕСЛИ Я#Л               | текста на ленте.
     ТО Нет                | Если они не совпадают, работа заканчивается.
     ИНАЧЕ                 | Если совпадают, стираем символ  с  ленты, воз-
     {                     | вращаем окно в исходное  положение  (когда оно
       Вернуться           | показывает первый пустой символ справа от тек-
       Сравнить_символы    | ста)  и  начинаем проверку  рекурсивно сначала
     }                     | над укороченными на один символ словами.
  }                        |
КОНЕЦ                      |
//---------------------    |
ЭТО Взять_символ           | Скопировать символ в ящик и
  ЯЩИК+                    | стереть его с ленты.
  ПИШИ ПУСТО               |
КОНЕЦ                      |
//---------------------    |
ЭТО Сравнить               | Установить окно на первый не пустой
 ВЛЕВО                     | символ слева.
 ПОКА НЕ ПУСТО ВЛЕВО       |
 ВПРАВО                    |
КОНЕЦ                      |
//---------------------    |
ЭТО Вернуться              | Стереть символ с ленты и установить окно
 ПИШИ ПУСТО                | на первый пустой символ справа от  рабо-
 ВПРАВО                    | чей записи.
 ПОКА НЕ ПУСТО ВПРАВО      |
КОНЕЦ                      |
//---------------------    |
ЭТО Нет                    | Слово не палиндром.
 ПОКА НЕ =                 | Стираем остаток исходного слова с ленты.
 {                         |
   ПИШИ ПУСТО              |
   ВПРАВО                  |
 }                         |
 ПИШИ #                    | Вместо знака "=" записываем знак "#".
 ВПРАВО                    |
 ПОКА НЕ ПУСТО             | Стираем остаток дубля
 {                         |
   ПИШИ ПУСТО              |
   ВПРАВО                  |
 }                         |
 ПОКА НЕ # ВЛЕВО           | Устанавливаем окно на знак "#"
КОНЕЦ                      |
//---------------------    |
ЭТО Записать=              |
 ПОКА НЕ ПУСТО ВПРАВО      |
 ПИШИ =                    |
 ПОКА НЕ ПУСТО ВЛЕВО       |
КОНЕЦ                      |
//---------------------    |
ЭТО Дубль                  | Процедура "Дубль" и вспомогательные
 ВПРАВО                    | процедуры "Перенос_символа",
 ПОКА НЕ =                 | "Установка_символа" - выполняют копирование
 {                         | исходного слова на ленту сразу за знаком "=".
   ЯЩИК+                   |
   Перенос_символа         |
   ВПРАВО                  |
 }                         |
КОНЕЦ                      |
//---------------------    |
ЭТО Перенос_символа        |
 ВПРАВО                    |
 ЕСЛИ НЕ =                 |
   ТО Перенос_символа      |
   ИНАЧЕ Установка_символа |
 ВЛЕВО                     |
КОНЕЦ                      |
//---------------------    |
ЭТО Установка_символа      |
 ВПРАВО                    |
 ПОКА НЕ ПУСТО ВПРАВО      |
 ЯЩИК-                     |
 ПОКА НЕ = ВЛЕВО           |
КОНЕЦ                      |
//---------------------    |


Анализ работ.

Решение Гуреева Дениса (команды 05, г.Снежинск)

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

ЭТО Проверка               | В процедуре организован
 ВПРАВО                    | рекурсивный косвенный цикл.
 ЕСЛИ НЕ ПУСТО             | Процедура работает,  пока
  ТО { ВЛЕВО Работа }      | сокращение слова не приведет к
  ИНАЧЕ Да                 | одному символу или пустому месту.
КОНЕЦ                      |
                           |
ЭТО Работа                 | Процедура Работа сравнивает  буквы
                           | по концам слова, убирая их с  лен-
                           | ты.  Если  попались не  одинаковые
                           | буквы, то сразу сообщается "нет".
                           |
 ОБМЕН                     | Занесение первого символа в ящик и
 ПИШИ ПУСТО                | удаление его с ленты.
 ВПРАВО                    | Перемещение окна на
 ПОКА НЕ ПУСТО ВПРАВО      | последний символ
 ВЛЕВО                     | слова.
 ЕСЛИ Я=Л                  | Символы совпали
  ТО                       |
  {                        |
    ПИШИ ПУСТО             | Удалить последний символ слова.
    ВЛЕВО                  | Возврат в начало
    ПОКА НЕ ПУСТО ВЛЕВО    | укороченного
    ВПРАВО                 | слова и рекурсивное
    Проверка               | продолжение алгоритма с самого начала.
  }                        |
  ИНАЧЕ Нет                | Символы не совпали - слово не палиндром.
КОНЕЦ                      |
                           |
ЭТО Да                     |
 ВЛЕВО                     | Удаление символа с ленты
 ПИШИ д ВПРАВО             | и запись ответа.
 ПИШИ а                    |
КОНЕЦ                      |
                           |
ЭТО Нет                    |
 ПОКА НЕ ПУСТО             | Удаление остатка слова
 {                         | с ленты.
   ПИШИ ПУСТО              |
   ВЛЕВО                   |
 }                         |
 ПИШИ н ВПРАВО             | Запись ответа.
 ПИШИ е ВПРАВО             |
 ПИШИ т                    |
КОНЕЦ                      |


   Решение Ялышева Влада и Козловой В.А. (команда 09, г.Пермь).

   Описание алгоритма.
   1. Создается копия слова (процедура Дубль).
   2. За дублем записывается заготовка ответа - "да".
   3. Сравниваются "зеркально" симметричные буквы в обоих  сло-
вах. Поиск и возврат к очередной букве выполняются  за счет от-
ложенных в рекурсии команд.
   4. Заготовка "да" заменяется на "нет", если  слово не палин-
дром.

ЭТО Палиндром              |
 Дубль                     | Создание дубля слова справа.
 Результат                 | Запись заготовки ответа  "да" и установка
                           | окна между дублем и оригиналом.
 Сравнение                 | Сравнение оригинала и дубля.
КОНЕЦ                      |
                           |
ЭТО Сравнение              |
ВПРАВО                     |
ПОКА НЕ ПУСТО              | Цикл по символам дубля.
{                          |
  ЯЩИК+                    | Запоминание очередного символа в дубле.
  Ищи_букву                | Поиск "зеркальной" позиции в оригинале.
  ЕСЛИ Я#Л                 | Сравнение символов.
    ТО    Нет              | Если символы совпадают возврат к текущему
    ИНАЧЕ Возврат          | месту в дубле для продолжения работы.
  ВПРАВО                   | Если нет, то вызываем процедуру Нет.
}                          |
КОНЕЦ                      |
                           |
ЭТО Ищи_букву              | За счет отложенной в рекурсии команды
 ВЛЕВО                     | ВЛЕВО отыскивается "зеркальная" символ.
 ЕСЛИ НЕ ПУСТО             |
  ТО    Ищи_букву          |
 ВЛЕВО                     |
КОНЕЦ                      |
                           |
ЭТО Возврат                | Возврат к текущему месту в дубле
  ВПРАВО                   | за счет отложенной в рекурсии
  ЕСЛИ НЕ ПУСТО ТО Возврат | команды ВПРАВО.
  ВПРАВО                   |
 КОНЕЦ                     |
                           |
ЭТО Нет                    | Замена "да" на "нет".
  ПОВТОРИ 2                |
  {                        |
    ПОКА НЕ ПУСТО ВПРАВО   |
    ВПРАВО                 |
  }                        |
  ПИШИ н ВПРАВО            |
  ПИШИ е ВПРАВО            |
  ПИШИ т                   |
КОНЕЦ                      |
                           |
ЭТО Результат              | Запись слова "да" за дублем.
  ВПРАВО                   |
  ПОКА НЕ ПУСТО ВПРАВО     |
  ВПРАВО                   |
  ПИШИ д                   |
  ВПРАВО                   |
  ПИШИ а                   |
  ПОКА НЕ ПУСТО ВЛЕВО      | Возврат в исходное положение
  ВЛЕВО                    | между оригиналом и дублем.
  ПОКА НЕ ПУСТО ВЛЕВО      |
КОНЕЦ                      |
                           |
 ЭТО Дубль                 |
  ПОКА НЕ ПУСТО            |
  {                        |
   ЯЩИК+                   | Запомнить символ
   Перенос                 | Скопировать
   ВПРАВО                  | Переместиться дальше
  }                        |
 КОНЕЦ                     |
                           |
ЭТО Перенос                |
 ВПРАВО                    |
 ЕСЛИ ПУСТО                |
  ТО    Установка          |
  ИНАЧЕ Перенос            |
 ВЛЕВО                     | Возврат в текущее положение
КОНЕЦ                      | в оригинале.
                           |
ЭТО Установка              | Установка очередного символа в
 ВПРАВО                    | конец дубля.
 ПОКА НЕ ПУСТО ВПРАВО      |
 ЯЩИК-                     |
 ПОКА НЕ ПУСТО ВЛЕВО       |
КОНЕЦ                      |

   Задача 3.

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

   Первый алгоритм.
   Будем считать, что исходные числа на  ленте незначащих нулей
не содержат. Если это не так, то предварительно нужно запустить
процедуру, которая эти незначащие нули убирает.
   Подсчитаем и сравним длины чисел. То число, которое длиннее,
является  наибольшим.  Если считать, что каждое число на  ленте
состоит не более, чем из 71 цифр (число символов в алфавите Кор-
ректора), то в качестве счетчика длин  можно использовать ящик.
В итоге мы получим два символа, каждый из которых выражает дли-
ну соответствующего числа. Сравнив эти два символа, получим от-
вет для задачи.
   Что делать, если окажется, что числа имеют одинаковую длину?
   Нужно приступить к выполнению следующего алгоритма:  сравни-
вать цифры числа начиная со старшей. Либо они все окажутся рав-
ны,  и  тогда числа совпадают, либо проверка заканчивается  при
первом несовпадении.
   Пример: 239?261
2 равно 2 проверяем дальше,
3 меньше 6 проверка закончена: первое число меньше.

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


Второй алгоритм.
   Рассмотрим не  оптимальный, но самый очевидный алгоритм: вы-
читаем из каждого числа (слева и справа от знака "?") по едини-
це до тех пор, пока слева  или справа не получим число 0. Даль-
нейший ход решения очевиден. Поясним сказанное на примерах.
           2?3    4?2    2?2
           1?2    3?1    1?1
           0?1    2?0    0?0
            <      >      =

 // Установка окна на знак "?"
//---------------------    |
ЭТО Проверка               |
 Дубль                     |
 ПОКА НЕ ? ВПРАВО          | Установить окно на знак "?" в дубле.
 Работа_с_дублем           | Записать нужный знак (< , =, >) в ящик.
 Стереть_копию             | Удаление остатка дубля с ленты.
 Установить_знак           | Установить знак из ящика на место знака "?"
КОНЕЦ                      | в оригинале.

  .......

   Если при  программировании процедуры поочередного  вычитания
единиц от чисел использовать рекурсию (как  это сделала команда
32), то обнаружится, что программа не хочет работать с длинными
числами. На экран выдается сообщение "Переполнение стека интер-
претатора". Это происходит уже для задания "200?200" Что бы это
означало?
   Дело в глубокой  рекурсии,  которая быстро расходует всю па-
мять  интерпретатора  Корректора, предназначенную  для хранения
адресов возврата. Иными словами происходит то, о чем говорилось
в разделе 2.7. "Подводные камни рекурсии"  на примере рекурсив-
ного алгоритма для вычисления чисел Фибоначчи.
   Где в этом решении  тонкое  место? Может быть, в рекурсивной
процедуре Минус1 (отнимающей 1 от  обычного  числа  на  ленте)?
Нет, эта  процедура  добавляет  рекурсивные  адреса возвратов в
стек только тогда, когда происходит вычитание единицы от числа,
заканчивающегося на 0.  Но даже в этом случае число рекурсивных
вызовов не накапливается катастрофически (оно не превышает раз-
рядность числа и уж, конечно, для трехзначных чисел дает совсем
небольшую нагрузку на стек).
   Причина - в работе процедуры, которая поочередно отнимает от
чисел по  единице, пока одно из них не  станет нулем. В решении
команды 32  эта процедура рекурсивная, и рекурсия заканчивается
тогда, когда одно из чисел станет нулем.
   Для примера "200?200" это произойдет через 200 шагов.
   Можно, конечно, посетовать, почему  стек  возвратов процедур
Корректора такой  короткий.  Предположим,  что мы увеличим стек
возвратов в пять раз.  Это  означает, что программа будет рабо-
тать с выражениями  до "1000?1000", что, конечно, не сильно из-
менит ее универсальность. Здесь  тот  самый случай, когда к ре-
курсии надо относиться осторожно.
   Можно ли  при  реализации этого алгоритма придумать нерекур-
сивную процедуру? Да, и это продемонстрировано в работе команды
57 (см. ниже).
   В заключение один программистский этюд. Несмотря на рекурсив-
ную безобидность процедур Плюс1 и Минус1, их легко можно сделать
совсем без рекурсии.
   Вот как выглядит, например, нерекурсивный вариант  процедуры
Плюс1 (добавление единицы к обычному числу на ленте):
//---------------------    |
ЭТО Плюс1                  |
 ЕСЛИ 9 ТО    Девять       | Девятку обработаем отдельно, а
        ИНАЧЕ ПЛЮС         | иную цифру просто увеличим на один.
КОНЕЦ                      |
//---------------------    |
ЭТО Девять                 |
 ПОКА 9                    | Пока в окошке видны девятки,
 {                         | заменяем их нулями, перемещая окно
   ПИШИ 0                  | влево.
   ВЛЕВО                   |
 }                         | Девятки закончились.
 ЕСЛИ НЕ ЦИФРА             | Если все  цифры числа были девятками, то перед
   ТО    ПИШИ 1            | всеми нулями измененного числа записываем 1, в
   ИНАЧЕ ПЛЮС              | противном  случае  увеличивает цифру-не-девять
КОНЕЦ                      | на 1.
//---------------------    |

Анализ работ.
   Сафин Артур, Громатчиков Алексей (команда 14, г.Казань), Ас-
тахова, Шевченко, Вычугин, Силинская  (команда  24, г.Иркутск),
Лебедь Саша  (команда 27, г.Зеленогорск), Григорьев Андрей (ко-
манда 39,  г.Ижевск) используют модификацию описанного выше ал-
горитма 1. В  их  решении применен оригинальный прием сравнения
длин чисел. Окошко смещается по первому числу до знака "?", на-
капливая при этом отложенную команду ВПРАВО. Эта отложенная ко-
манда запускается на  втором  числе. Что получается: окно будет
сдвинуто вправо на длину первого числа. Если при этом оно уста-
новится на пустое место, то первое  число  было  длиннее.  Если
внутри второго числа, то  первое  число было короче, если точно
на его  край, то числа равны  по длине, и  нужна дополнительная
проверка их цифр (начиная со старшей).
   Радченко Сергей (команда 57, г.Волгоград) использовал  неоп-
тимальный  алгоритм  2. Программа работает очень долго, но  она
способна обрабатывать  очень длинные числа! Почему? Потому, что
Сергей применил нерекурсивный алгоритм для вычитания единицы от
каждого числа. Он обошелся (вполне обоснованно) циклом ПОКА:

ЭТО Вычитание
 Проверка_конца_работы //Если работать
 ПОКА НЕ 0             //можно, то ...
 {                                     
   // Установим окно на                
   // конец второго числа              
   ПОВТОРИ 2 ВПРАВО
   ПОКА НЕ ПУСТО ВПРАВО
   ВЛЕВО
   // Отнимем 1 от второго числа
   Минус1
   // Установим окно на первое число
   ПОКА НЕ - ВЛЕВО                     
   ВЛЕВО                               
   // Отнимем 1 от первого числа
   Минус1
   Проверка_конца_работы               
 }                                     
 // Очистим окно проверки
 ПИШИ ПУСТО                            
КОНЕЦ
                                       
 .....

    Задача  4.
   Самое красивое и  короткое решение здесь - рекурсивное с от-
ложенными в рекурсии командами для стирания лишних палочек.
   Для начала  рассмотрим бесхитростные неоптимальные  решения,
чтобы потом насладиться изяществом и красотой рекурсии.

   Вариант 1. Палочное число не больше числа символов в алфавите
Корректора (то есть, в числе не больше 71 палочек).
   Программа работает  для  всех  таких  палочных чисел, включая
ноль и нечетные. Для последних она выполняет деление нацело.
   Алгоритм: вычисляем длину палочной записи числа, используя в
качестве счетчика ящик и удаляем половину палочек с ленты.

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

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

//---------------------    |
ЭТО Деление_2              |
 Половина_длины            |
 Стереть_лишнее            |
КОНЕЦ                      |
//---------------------    |
ЭТО Половина_длины         |
 ОБМЕН ПИШИ 0 ОБМЕН        | Записать 0 в счетчик
 ПОКА НЕ ПУСТО             |
 {                         |
   ОБМЕН ПЛЮС ОБМЕН        | Добавить к счетчику 1
   ВПРАВО                  | Переместить окно на две
   ЕСЛИ НЕ ПУСТО ТО ВПРАВО | клетки вправо
 }                         |
КОНЕЦ                      |
//---------------------    |
ЭТО Стереть_лишнее         |
  ВЛЕВО                    |
  ОБМЕН                    |
  ПОКА НЕ 0                |
  {                        |
    МИНУС                  |
    ОБМЕН                  |
    ПИШИ ПУСТО             |
    ВЛЕВО                  |
    ОБМЕН                  |
  }                        |
 ОБМЕН                     |
КОНЕЦ                      |
//---------------------    |

   Рекурсия "зацепила" воображение ребят даже больше, чем пред-
полагали организаторы  Курсов.  Посмотрите  на вариант решения,
предложенный Самусенко и Медведевым (команда 24, г.Иркутск):

                           | Отличная программа!
                           | Ни один из вариантов организаторов
ЭТО Деление                | не идет ни в какое сравнение с
  ПОВТОРИ 2 ВПРАВО         | этой малюсенькой программой.
  ЕСЛИ НЕ ПУСТО ТО Деление |
  ВЛЕВО                    || Вот эти две команды и выполняют чудо:
  ПИШИ ПУСТО               || стирают с ленты лишние палочки.
КОНЕЦ                      |

   Еще несколько решений, основанных на той же идее.

Разуваев Алеша и Шестаков Паша (команда 13, г.Иркутск):
ЭТО Деление
 ВПРАВО
 ЕСЛИ |
  ТО { ВПРАВО Деление }
 ВЛЕВО
 ПИШИ ПУСТО
КОНЕЦ

   Кириллов Сергей, Гарифуллин Динар,  Ананьев  Сергей (команда
14, г.Казань):

ЭТО Двигаться_через_палку
   ПОВТОРИ 2 ВПРАВО
   ЕСЛИ | ТО Двигаться_через_палку
   Стереть_палку
КОНЕЦ

ЭТО Стереть_палку
  ВЛЕВО
  ПИШИ ПУСТО
КОНЕЦ

   Мехряков Олег (команда 09, г.Пермь):
ЭТО Деление
 ПОКА НЕ ПУСТО ИЩИ
КОНЕЦ

ЭТО ИЩИ
 ПОВТОРИ 2 ВПРАВО
 ЕСЛИ НЕ ПУСТО
   ТО ИЩИ
 ВЛЕВО
 ПИШИ ПУСТО
КОНЕЦ

   Если бы еще добавить в эти программы возврат  окошка на пер-
вый символ числа, то результат на ленте смотрелся бы лучше. Ду-
мается, что ребята не сделали это умышленно: чтобы окончательно
потрясти нас краткостью своих программ.

   Задача 5.
   Ящик служит счетчиком знаков сложения. Вначале работы он об-
нуляется.
   Запись просматривается слева направо.  При  обнаружении знака
сложения он заменяется на палочку и  содержимое ящика увеличива-
ется на единицу. После просмотра записи  в  конце  ее  стирается
столько палочек, сколько знаков сложения в ней было обнаружено.
   Если использовать  для стирания отложенную в рекурсии группу
команд ВЛЕВО ПИШИ  ПУСТО,  то программа становится совсем корот-
кой. Ниже приводится нерекурсивный вариант решения.


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

   Необыкновенно красивое и короткое решение предложили Липина
Настя и Ильина Лена (команды 13, г.Иркутск):

ЭТО Сложение_палочек        |
 ПОКА НЕ + ВПРАВО           |
 ПИШИ |                     |
 ПОКА | ВПРАВО              |
 ЕСЛИ + ТО Сложение_палочек |
 ВЛЕВО                      || Вот они отложенные команды,
 ПИШИ ПУСТО                 || творящие чудеса!
КОНЕЦ                       |

   Такое же решение у Сафина Артура и Громатчикова Алексея (ко-
манда 14, г.Казань):
ЭТО Искать+
  ПОКА | ВПРАВО
  ЕСЛИ +
   ТО
   {
     ПИШИ |
     Искать+
   }
  Стирание
КОНЕЦ

ЭТО Стирание
   ПИШИ ПУСТО
   ВЛЕВО
КОНЕЦ

   Мы увидели множество вариантов решения этой задачи.
   Одни из них связаны со сложением палочек, другие - со сложе-
нием знаков "+", как в решении, описанном оргкомитетом.
   Среди решений,  складывающих палочки, можно выделить 3 вари-
анта.
   Первый  из  них оперирует только с палочными числами,  сумма
которых не превышает 9. Ясно, что такой вариант  не решает пос-
тавленную  задачу.  Такие решения очень просты, потому что  ис-
пользуют для сложения команду ПЛЮС, которая  не ПРИБАВЛЯЕТ еди-
ницу к символу-цифре, а заменяет текущий символ на следующий за
текущим в алфавите  Корректора  и, конечно, "не справляется" со
сложением "9+1".
   Второй вариант решения построен также на замене сложения ко-
мандой  ПЛЮС,  применяемой к  одному  символу-сумматору.  После
окончания "сложения" символ-сумма "развертывается" в число. Та-
кое решение также имеет ограничение на величину полученной сум-
мы: она не  должна превышать длины алфавита Корректора, то есть
числа 71.
   В третьем  варианте, самом универсальном, величина суммы ог-
раничивается только размером ленты Корректора.

   Задача 6.

   Вариант 1. Если предположить, что текст на ленте короче чис-
ла символов  в алфавите Корректора,  то для подсчета цифр в ка-
честве счетчика можно использовать ящик (неоднократно использу-
емый ранее прием).

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


   Вариант 2. Общий случай:  число  цифр в тексте не ограничено
длиной алфавита Корректора.  В  этом случае в качестве счетчика
нельзя использовать  ящик,  и  счетчик "монтируется" прямо перед
текстом  на  ленте. Каждый раз, когда Корректор обнаруживает  в
тексте цифру, он перемещает  окно  на счетчик и увеличивает его
на один, затем при помощи рекурсивно  отложенной команды ВПРАВО
возвращается на прежнее место  в  тексте и продолжает его прос-
мотр.

//---------------------    |
ЭТО Подсчет_цифр           |
 Подготовка_счетчика       | Записать в счетчик на ленте 0
 Подсчет                   | Подсчет цифр
 Установить_на_ответ       | Переместить окно на результат
КОНЕЦ                      |
//---------------------    |
ЭТО Подготовка_счетчика    |
 ВЛЕВО                     |
 ПИШИ 0                    |
 ПОВТОРИ 2 ВПРАВО          |
КОНЕЦ                      |
//---------------------    |
ЭТО Подсчет                |
 ПОКА НЕ ПУСТО             | Цикл по всем символам текста.
 {                         |
   ЕСЛИ ЦИФРА ТО Добавить1 | Если в тексте обнаружена цифрая,  "идти" к счетчику    v
                           | и добавлять к нему единицу.
   ВПРАВО                  | Сместиться к следующему символу текста.
 }                         |
КОНЕЦ                      |
//---------------------    |
ЭТО Добавить1              |
 ВЛЕВО                     | Сдвигаем окно влево, пока оно не будет
 ЕСЛИ НЕ ПУСТО             | установлено на первый пустой символ перед текстом.
   ТО Добавить1            |
   ИНАЧЕ                   |
   {                       |
     ВЛЕВО                 |
     Плюс1                 | Добавляем единицу к счетчику и
     Возврат               | возвращаем оно на пустой символ перед текстом.
   }                       |
                           | Это - отложенная команда. Она обеспечивает
 ВПРАВО                    | возврат к текущему положению окна в тексте.
КОНЕЦ                      |
//---------------------    |
ЭТО Возврат                |
 ПОКА НЕ ПУСТО ВПРАВО      | Возврат на пустой символ перед текстом после
КОНЕЦ                      | работы процедуры Плюс.
//---------------------    |
ЭТО Установить_на_ответ    | Установка окна в удобное положение для
 ВЛЕВО                     | демонстрации ответа.
 ПОКА НЕ ПУСТО ВЛЕВО       |
КОНЕЦ                      |
//---------------------    |
ЭТО Плюс1                  |
 ЕСЛИ НЕ 9                 |
   ТО                      |
   {                       |
     ЕСЛИ ПУСТО            |
      ТО    ПИШИ 1         |
      ИНАЧЕ ПЛЮС           |
   }                       |
   ИНАЧЕ                   |
   {                       |
     ПИШИ 0                |
     ВЛЕВО                 |
     Плюс1                 |
   }                       |
КОНЕЦ                      |
//---------------------    |

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

   Задача 7.

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

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


   Команда 32 (руководитель Ким  Л.С.,  г.Находка) использовала
для решения задачи следующий алгоритм. (Правильность  алгоритма
командой не доказана; приведенные ниже доказательства  - от ор-
гкомитета).
   1. Сначала каждая  цифра исходного числа заменяется на оста-
ток от деления на  три.  Неявно утверждается, что если исходное
число делилось на три, но новое также делится на три.  И наобо-
рот, если  новое число делится на  три, то исходное  делится на
три тоже.  Прямая  и  обратная  теоремы  справедливы, это можно
очень легко доказать.

    Пусть исходное число имеет вид:
                   a0a1...ai...an, где ai - цифры числа.
      Эту запись можно представить в виде:
                n       n-1           n-i           0
           a0*10 + a1*10 + ... + ai*10 + ... + an*10    (*)

   Если теперь, каждое ai заменить на  3ki +di , где ki - целая
часть от деления ai на 3,  a di - остаток, то (*) легко разбить
на два слагаемых.  Одно  из них  состоит  из суммы членов  вида
                             n-1
                     (3ki)*10
и заведомо на три делится.
   Другое представляет собой запись вида
                n       n-1           n-i           0
           d0*10 + d1*10 + ... + di*10 + ... + dn*10    (**)

   Но это и есть запись исходного числа, в  котором каждая цифра
заменена на остаток от ее деления на 3:

                     d0d1...di...dn                   (***)

   Значит, делимость исходного числа на 3 однозначно определяет-
ся делимостью на 3 числа (***).

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

   Правомерно ли  описанное  преобразование?  Это тоже подлежит
доказательству.
   Шаг а) очевидно правомерен. Остается доказать  правомерность
шага б).
   Этот шаг  правомерен  по следующей причине. Известен признак
деления на три: число делится на три тогда и только тогда, ког-
да сумма его цифр делится на три.
   Тогда число (***) делится на три тогда и  только тогда, когда
на три делится сумма

                 d0 + d1 + ... + di + ... + dn           (****)

   Заменим сумму  d0 + d1 на сумму  3*l+v, где  l и v  соответ-
ственно целая  часть и  остаток от деления числа d0  + d1 на 3.
Тогда (****) преобразуется в

              3*l + v + d2 + ... + di + ... + dn        (*****)

   Очевидно, что последняя сумма делится  на  3  тогда и только
тогда, когда на три делится сумма:

                    v + d2 + ... + di + ... + dn       (******)

   Тем самым, правомерность шага б) доказана.

   Однако доказательство шага б) наводит на  мысль сразу приме-
нять описанное  преобразование  к исходному числу без предвари-
тельного его упрощения путем замены каждой его цифры на остаток
от ее деления на три.
   Примеры таких преобразований.
  2597 -> 197 -> 17 -> 2 - исходное число на три не делится.
  2745 -> 045 -> 15 -> 6 - исходное число на три делится

   Для замены  двух цифр на одну - остаток  от деления их суммы
на три можно использовать следующий прием.
//--------------------- |
 ЭТО Сумма_двух_цифр    |
   ЯЩИК+                | Запомнить первую цифру в ящике
   ПИШИ ПУСТО           | Стереть цифру
   ВПРАВО               | Подойти к следующей цифре
   ПОКА НЕ 0            | Суммирование цифры в ящике и на ленте,
   {                    | результат помещается в ящик.
    ОБМЕН               |
    ПЛЮС                |
    ОБМЕН               |
    МИНУС               |
   }                    |
   ОБМЕН                | Записать результат на ленту
   Замена               | Вызвать процедуру, которая заменит
КОНЕЦ                   | сумму на остаток от деления на 3.
//--------------------- |

   Процедура замена может быть спроектирована при помощи перек-
лючателя:
//--------------------- |
ЭТО Замена              |
 ЕСЛИ       1 ТО ПИШИ 1 |
 ИНАЧЕ ЕСЛИ 4 ТО ПИШИ 1 |
 ИНАЧЕ ЕСЛИ 7 ТО ПИШИ 1 |
 ИНАЧЕ ЕСЛИ а ТО ПИШИ 1 |
 ИНАЧЕ ЕСЛИ г ТО ПИШИ 1 |
 ИНАЧЕ ЕСЛИ ж ТО ПИШИ 1 |
 ИНАЧЕ ЕСЛИ 2 ТО ПИШИ 2 |
 ИНАЧЕ ЕСЛИ 5 ТО ПИШИ 2 |
 ИНАЧЕ ЕСЛИ 8 ТО ПИШИ 2 |
 ИНАЧЕ ЕСЛИ б ТО ПИШИ 2 |
 ИНАЧЕ ЕСЛИ д ТО ПИШИ 2 |
 ИНАЧЕ ЕСЛИ з ТО ПИШИ 2 |
 ИНАЧЕ           ПИШИ 0 |
КОНЕЦ                   |
//--------------------- |

   Тогда главная процедура для решения поставленной задачи име-
ет вид:

//--------------------- |
ЭТО Кратность3          |
  ПОВТОРИ 2 ВПРАВО      | Устанавливаем окно на вторую цифру числа
  ПОКА НЕ ПУСТО         | Цикл по цифрам числа
  {                     |
    ВЛЕВО               |
    Сумма_двух_цифр     |
    ВПРАВО              |
  }                     |
  ВЛЕВО                 |
  Замена                | На ленте от числа осталась одна цифра.
                        | Заменим ее на остаток.
  ЕСЛИ 0 ТО    ПИШИ +   | Если остаток равен 0, то пишем "+" (кратно 3).
         ИНАЧЕ ПИШИ -   | В противном случае пишем "-" (исходное число не
КОНЕЦ                   | кратно 3).
//--------------------- |

   Самое красивое и  короткое  решение этой задачи прислал А.В.
Рудь - руководитель  команды 05 из г.Снежинска. Правда, это ре-
шение было прислано уже после окончания турнира.
   Идея алгоритма - формировать в ящике остаток от деления сум-
мы цифр исходного числа на три.

ЭТО Делимость_на_3      |
 ОБМЕН                  ||
 ПИШИ 0                 ||  Обнуление ящика-счетчика
 ОБМЕН                  ||
 ВПРАВО                 |
 ПОКА НЕ ПУСТО          | Цикл по всем цифрам числа
 {                      | и формирование в ящике остатка
  Цифра                 | от деления суммы цифр числа на 3.
  ВПРАВО                |
 }                      |
 ОБМЕН                  | Что в ящике?
 ЕСЛИ 0                 | Если остаток 0, то исходное
  ТО                    | число было кратно трем.
  {                     |
   ПИШИ д ВПРАВО        |
   ПИШИ а ВПРАВО        |
  }                     |
  ИНАЧЕ                 |
  {                     |
   ПИШИ н ВПРАВО        |
   ПИШИ е ВПРАВО        |
   ПИШИ т ВПРАВО        |
  }                     |
КОНЕЦ                   |
                        |
ЭТО Цифра               | Эта процедура формирует остаток
 ПОКА НЕ 0              |
 {                      |
  МИНУС                 |
  ОБМЕН                 |
  ПЛЮС                  |
  ЕСЛИ 3 ТО ПИШИ 0      |
  ОБМЕН                 |
 }                      |
 ПИШИ ПУСТО             |
КОНЕЦ                   |



   Задача 8.

   Вариант 1. Первый алгоритм  использует  переключатель. Прос-
матриваем запись числа слева направо и заменяем каждую его циф-
ру на ее дополнение до 9.

//--------------------- |
ЭТО Дополнение9
  ВПРАВО
  ПОКА НЕ ПУСТО
  {
    ЕСЛИ       0 ТО ПИШИ 9
    ИНАЧЕ ЕСЛИ 1 ТО ПИШИ 8
    ИНАЧЕ ЕСЛИ 2 ТО ПИШИ 7
    ИНАЧЕ ЕСЛИ 3 ТО ПИШИ 6
    ИНАЧЕ ЕСЛИ 4 ТО ПИШИ 5
    ИНАЧЕ ЕСЛИ 5 ТО ПИШИ 4
    ИНАЧЕ ЕСЛИ 6 ТО ПИШИ 3
    ИНАЧЕ ЕСЛИ 7 ТО ПИШИ 2             
    ИНАЧЕ ЕСЛИ 8 ТО ПИШИ 1
    ИНАЧЕ ЕСЛИ 9 ТО ПИШИ 0
    ВПРАВО
  }
КОНЕЦ
//--------------------- |

   Вариант 2. Второй алгоритм не использует переключатель.

//--------------------- |
ЭТО Замена_цифр         |
 ВПРАВО                 |
 ПОКА НЕ ПУСТО          | Цикл по цифрам числа
  {                     |
    Замена              | Замена цифры на дополнение
    ВПРАВО              | Перемещение к следующему символу
  }                     |
КОНЕЦ                   |
//--------------------- |
ЭТО Замена              |
 ЯЩИК+                  | Цифра копируется в ящик, а на
 ПИШИ 9                 | ленту записывается число 9.
 ОБМЕН                  | Возвращаем цифру на ленту, цифра 9 теперь в ящике.
 ПОКА НЕ 0              | Пока цифра не станет 0 вычитаем из не по единице.
 {                      |
   МИНУС                |
   ОБМЕН                | Одновременно вычитаем единицу из числа в ящике.
   МИНУС                | Когда цифра на ленте превратиться в ноль,
   ОБМЕН                | цифра в ящике станет ее дополнением.
 }                      |
 ОБМЕН                  |
КОНЕЦ                   |
//--------------------- |


   Сычев Сергей (команда 14,  г.Казань)  предложил оригинальное
рекурсивное решение с отложенной командой ПЛЮС:

ЭТО Дополнить_число
    ВПРАВО
    ПОКА ЦИФРА
    {
     ЕСЛИ ЦИФРА ТО Дополнить_цифру
     ВПРАВО
    }
КОНЕЦ
ЭТО Дополнить_цифру
    ЕСЛИ НЕ 9 ТО
       {
         ПЛЮС
         Дополнить_цифру
       }
     ИНАЧЕ ПИШИ ПУСТО
     ПЛЮС   //Отложенная команда
КОНЕЦ
