Роботландский Университет 00/01
31 Азы программирования
Авторское решение задач турнира Корректора
------------------------------------------
апрель, 2001 (C) А.А.Дуванов

Уважаемые коллеги!

Ниже приводятся решения конкурсных задач Корректора. Из всех возможных
решений я отдавал предпочтение простым по логике, тем, что лежат на
поверхности, предпочитая ясный цикл ПОКА красивой, но, требующей
определенного опыта, рекурсии. Сделано это по двум причинам:

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

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

Задачу о Ханойской башне я не решал, уверенный опять же, что эту
сложнейшую рекурсивную конструкцию построит, по крайней мере Первушин
Данил из Снежинска. Ну, а если он ее не решит (на что мало надежды!),
то задача перейдет на конкурс Корректора следующего года.

Приведенные ниже программные коды предназначены для чтения человеком,
который хочет понять как описанный алгоритм отображается на специфику
программной среды исполнителя. Хотя, конечно, эти коды рабочие. Их можно
"вырезать" из текста описания и запустить.

┌─────────────┐
│Решение задач│
└─────────────┘
1----------------------------------------------------------------------
Задача 1 (2 балла)
--------
Первый член последовательности равен 1. Каждый следующий член
получается приписыванием справа единицы к записи предыдущего.

a  = 1
 1
a    = a 1
 i+1    i

Построить n-й член последовательности, если n кодируется порядковым
номером символа, который Корректор видит в начальный момент в своем
окошке. Считать, что символ "1" кодирует n=1, и в начальный момент на
ленте не могут быть записаны символы с меньшим порядковым номером.

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

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

Решение
-------
А л г о р и т м
Очевидно, что n-ый член последовательности изображается n единицами на
ленте исполнителя. Будем использовать число n, которое изображает
символ на ленте, в качестве начального значения счетчика поставленных
единиц, уменьшая его на один каждый раз при записи новой единицы.
Будем этот процесс повторять в цикле до тех пор, пока счетчик не
станет нулем.

ПОКА n не 0
{
  уменьшаем n на 1
  дописываем 1 к конструируемой записи справа
}

Таким образом, цикл будет работать n раз (n, n-1, .., 1) и на ленте
появится запись из n единиц.

П р о г р а м м а
ЭТО вход
 ПОКА НЕ 0
 {                                     
   МИНУС                               
   ОБМЕН
   ПИШИ 1                              
   ВПРАВО                              
   ОБМЕН
 }
 ОБМЕН                                 
КОНЕЦ                                  

2----------------------------------------------------------------------
Задача 2 (3 балла)
--------
Первый член последовательности равен 1. Каждый следующий член
получается приписыванием справа 0, если последний символ записи
предыдущего члена равен 1, или приписыванием справа 1 в противном
случае.

a  = 1
 1
a  = 10
 2
a  = 101
 3
...

Построить n-й член последовательности, если n кодируется порядковым
номером символа, который Корректор видит в начальный момент в своем
окошке. Считать, что символ "1" кодирует n=1, и в начальный момент на
ленте не могут быть записаны символы с меньшим порядковым номером.

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

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

Решение
-------
А л г о р и т м
Число на ленте изображающее n будем использовать в качестве начального
значения счетчика шагов исполнителя. На каждом шаге исполнитель
приписывает к записи поочередно символы 1 и 0, уменьшая счетчик до тех
пор, пока тот не обнулится.

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

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

П р о г р а м м а
ЭТО вход                   │
 вход1                     │Начинаем работу с записи 1
 ОБМЕН                     │
КОНЕЦ                      │
                           │
ЭТО вход1                  │Проверка счетчика и переход на запись 1
 ЕСЛИ НЕ 0 ТО работа1      │
КОНЕЦ                      │
                           │
ЭТО вход0                  │Проверка счетчика и переход на запись 0
 ЕСЛИ НЕ 0 ТО работа0      │
КОНЕЦ                      │
                           │
ЭТО работа1                │Запись 1, уменьшение счетчика и переход
 МИНУС  ОБМЕН              │на запись 0
 ПИШИ 1 ВПРАВО             │
 ОБМЕН                     │
 вход0                     │
КОНЕЦ                      │
                           │
ЭТО работа0                │Запись 0, уменьшение счетчика и переход
 МИНУС  ОБМЕН              │на запись 1
 ПИШИ 0 ВПРАВО             │
 ОБМЕН                     │
 вход1                     │
КОНЕЦ                      │


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

a  = 10
 1
a  = 1001
 2
a  = 100110
 3
...

Построить n-й член последовательности, если n кодируется порядковым
номером символа, который Корректор видит в начальный момент в своем
окошке. Считать, что символ "1" кодирует n=1, и в начальный момент на
ленте не могут быть записаны символы с меньшим порядковым номером.

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

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

Решение
-------
А л г о р и т м
Последние две цифры записи всегда, либо 10 (и тогда нужно дописать 01),
либо 01 (и тогда нужно дописать 10).

Соорудим "качели", аналогичные тем, что были описаны в решении задачи
2, но записывать будем не по одному, а по два символа.

П р о г р а м м а
ЭТО вход                   │
 вход10                    │Начнем с записи 10
 ОБМЕН                     │
КОНЕЦ                      │
                           │
ЭТО вход10                 │Проверить на окончание и записать 10
 ЕСЛИ НЕ 0 ТО работа10     │
КОНЕЦ                      │
                           │
ЭТО вход01                 │Проверить на окончание и записать 01
 ЕСЛИ НЕ 0 ТО работа01     │
КОНЕЦ                      │
                           │
ЭТО работа10               │Запись 10, уменьшение счетчика и
 МИНУС  ОБМЕН              │переход на запись 01
 ПИШИ 1 ВПРАВО             │
 ПИШИ 0 ВПРАВО             │
 ОБМЕН                     │
 вход01                    │
КОНЕЦ                      │
                           │
ЭТО работа01               │Запись 01, уменьшение счетчика и
 МИНУС  ОБМЕН              │переход на запись 10
 ПИШИ 0 ВПРАВО             │
 ПИШИ 1 ВПРАВО             │
 ОБМЕН                     │
 вход10                    │
КОНЕЦ                      │


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

a  = 110 (например)
 1
a  = 11001
 2
a  = 1100110
 3
...

Построить n-й член последовательности, если n кодируется порядковым
номером символа, который Корректор видит в начальный момент в своем
окошке. Считать, что символ "1" кодирует n=1, и в начальный момент на
ленте не могут быть записаны символы с меньшим порядковым номером.
Сразу справа от n на ленте записан первый член последовательности.

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

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

Решение
-------
А л г о р и т м
Задача отличается от предыдущей тем, что на ленте первый член уже
задан и, следовательно, возможны следующие "качели":

конец первого члена   "качели"             процедуры, образующие качели
-----------------------------------------------------------------------
00                     11 00 11 00 11 ...  вход1_11 <--> вход1_00
01                     10 01 10 01 10 ...  вход2_10 <--> вход2_01
10                     01 10 01 10 01 ...  вход3_01 <--> вход3_10
11                     00 11 00 11 00 ...  вход4_00 <--> вход4_11

Следовательно, можно написать четыре пары процедур, попарно образующие
"качели", определить последние два символа первого члена и запустить
нужную пару. При этом 6 других процедур работать не будут.

Можно поступить и по другому. На каждом шаге проверять последние два
символа записи на ленте и добавлять нужные знаки в конец записи.

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

Ниже приводится реализация второго алгоритма (просто потому, что эта
программа занимает меньше места!).

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

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

a  = 110 (например)
 1
a  = 01101
 2
a  = 1011010
 3
...

Построить n-й член последовательности, если n кодируется порядковым
номером символа, который Корректор видит в начальный момент в своем
окошке. Считать, что символ "1" кодирует n=1, и в начальный момент на
ленте не могут быть записаны символы с меньшим порядковым номером.
Сразу справа от n на ленте записан первый член последовательности.

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

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

Решение
-------
А л г о р и т м
Ничего сложного и нового, но "беготни" много!
ПОКА символ, моделирующий n не 1
{
  уменьшаем n на 1
  дописываем к записи слева и справа по нужному символу
}

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


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

Построить n-й член последовательности, если n кодируется порядковым
номером символа, который Корректор видит в начальный момент в своем
окошке. Считать, что символ "1" кодирует n=1, и в начальный момент на
ленте не могут быть записаны символы с меньшим порядковым номером.
Сразу справа от n на ленте записан первый правильный член
последовательности.

Решение
-------
А л г о р и т м
Получаем новые члены последовательности добавлением:
0 к первому члену,
1 ко второму,
0 к третьему и т.д. (чередуем 0 и 1).

Так поступаем всегда, за исключением случая, когда в первом члене
число нулей на два больше числа единиц. Если такое соотношение имеет
место, то сначала дописываем 1, а потом как обычно чередуем 0 и 1.

Определение соотношения числа единиц и нулей в первом члене за один проход
--------------------------------------------------------------------------
Запишем в ящик символ "ф" (примерно середина алфавита) и пошлем
Корректора вдоль записи первого члена последовательности с таким
заданием:

-- если видишь на ленте 0, увеличивай ящик на один;
-- если видишь на ленте 1, уменьшай ящик на один.

Что получится в результате?
Если после просмотра всей записи в ящике окажется символ "ц" (ф+2),
то число нулей на 2 больше в записи числа единиц и можно начинать строить
новые члены с дописывания 1. В противном случае, начинаем построение
с дописывания 0.

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


7----------------------------------------------------------------------
Задача 7 (7 баллов) НОД двух чисел.
--------
Написать программу для вычисления наибольшего общего делителя двух
чисел. Полагать, что числа по величине меньше длины алфавита
Корректора.

Решение
-------
Будем представлять числа символами алфавита Корректора. При этом число
0 кодируется символом "0", число 1 -- символом "1", число 10 --
символом "а" и так далее по алфавиту Корректора.

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

Начальное состояние            После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬        ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
│░│░║6║9│░│░│░│░│░│░│░│  ─>    │░│░│6│9│░│3│░│░│░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴        ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴

┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬        ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
│░│░║а║3│░│░│░│░│░│░│░│  ─>    │░│░│а│3│░│1│░│░│░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴        ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴


А л г о р и т м нахождения НОД(a,b)
---------------
ПОКА a не равно b
{
  если a=b то НОД=а
  если a<b то переставим числа местами
  a=a-b
}
НОД=a

Программа
---------
ЭТО вход                       │
 ЯЩИК+                         │ Создадим рабочую копию чисел справа.
 ПОВТОРИ 3 ВПРАВО              │
 ЯЩИК-                         │
 ПОВТОРИ 2 ВЛЕВО               │
 ЯЩИК+                         │
 ПОВТОРИ 3 ВПРАВО              │
 ЯЩИК-                         │
 ВЛЕВО                         │ Переходим к процедуре нод имея:
 нод                           │ -- окошко на первом символе
КОНЕЦ                          │ -- в ящике второй символ
                               │
ЭТО нод                        │
 ПОКА Я#Л                      │ ПОКА a не равно b
 {                             │
  ЕСЛИ Я>Л ТО                  │  -- если a<b
  { ОБМЕН ВПРАВО ЯЩИК- ВЛЕВО } │        переставим числа местами
  ИНАЧЕ                        │  -- иначе а=a-b
  {                            │
    ОБМЕН                      │
    ПОКА НЕ 0                  │
    {                          │
      МИНУС                    │
      ОБМЕН                    │
      МИНУС                    │
      ОБМЕН                    │
    }                          │
    ОБМЕН                      │     вычитание выполнено, приводим
    ВПРАВО ЯЩИК+ ВЛЕВО         │     среду к состоянию:
  }                            │     -- окошко на первом символе
 }                             │     -- в ящике второй символ
                               │
 ВПРАВО                        │ Стираем второе число и заканчиваем
 ПИШИ ПУСТО                    │ работу.
КОНЕЦ                          │


8----------------------------------------------------------------------
Задача 8 (8 баллов) Перевод в двоичную.
--------
Написать программу для перевода десятичного числа в двоичную систему
счисления. Полагать, что число по величине меньше длины алфавита
Корректора.

Решение
-------

А л г о р и т м

Пусть x -- исходное число

сфомировать пустую запись
ПОКА x>2
{
  d = остаток от деления x на 2 (очередная цифра)
  добавить найденную цифру d в начало записи
  x = целая часть от деления на 2
}
добавить x в начало записи

Решение
-------
Будем кодировать исходное десятичное число символом алфавита
Корректора. Число 0 кодируется символом "0", число 1 -- символом
"1",..., число 9 -- символом "9", число 10 -- символом "а" и так
далее. Двоичную запись будем формировать слева от исходного числа
(так как добавления придется делать в начало записи, а не в конец).

Спроектируем сначала процедуру для нахождения целой части и остатка от
деления на 2.

// Нахождение остатка и целой
// части от деления на 2
// Вход:  окошко на символе-числе
// Выход: символ заменен на остаток,
//        а справа -- целая часть.
ЭТО деление
 ОБМЕН
 ПИШИ 1
 ОБМЕН
 // сначала целая часть -- 0
 ВПРАВО ПИШИ 0 ВЛЕВО
 // вычитаем из числа 2, прибавляя
 // 1 к целой части
 ПОКА Я<Л
 {
   МИНУС МИНУС
   ВПРАВО ПЛЮС ВЛЕВО
 }
КОНЕЦ

Теперь можно написать целиком всю программу:
                                      │
                                      │Лента                Ящик
                                      │
                                      │┬─┬─┬─┬─╦═╦─┬─┬─┬─┬  ┌─┐
                                      ││░│░│░│░║6║░│░│░│░│  │ │
                                      │┴─┴─┴─┴─╩═╩─┴─┴─┴─┴  └─┘
                                      │
ЭТО вход                              │
 ОБМЕН                                │
 ПИШИ 1                               │┬─┬─┬─┬─╦═╦─┬─┬─┬─┬  ┌─┐
 ОБМЕН                                ││░│░│░│░║6║░│░│░│░│  │1│
                                      │┴─┴─┴─┴─╩═╩─┴─┴─┴─┴  └─┘
 ПОКА Я<Л                             │
 {                                    │перед делением:
                                      │┬─┬─┬─┬─┬─╦═╦─┬─┬─┬  ┌─┐
   // подготовка к делению            ││░│░│░│░│6║6║░│░│░│  │6│
   ЯЩИК+ ВПРАВО ЯЩИК-                 │┴─┴─┴─┴─┴─╩═╩─┴─┴─┴  └─┘
   деление                            │после деления:
                                      │┬─┬─┬─┬─┬─╦═╦─┬─┬─┬  ┌─┐
                                      ││░│░│░│░│6║0║3│░│░│  │1│
                                      │┴─┴─┴─┴─┴─╩═╩─┴─┴─┴  └─┘
                                      │
   // x = целая часть от деления на 2 │
   ВПРАВО ЯЩИК+ ПИШИ ПУСТО            │┬─┬─┬─┬─╦═╦─┬─┬─┬─┬  ┌─┐
   ВЛЕВО ВЛЕВО ЯЩИК-                  ││░│░│░│░║3║0│░│░│░│  │3│
                                      │┴─┴─┴─┴─╩═╩─┴─┴─┴─┴  └─┘
                                      │
   // Добавить найденную цифру        │
   ВПРАВО ЯЩИК+ ПИШИ ПУСТО            │
   ВЛЕВО                              │перед добавить
   добавить                           │┬─┬─┬─┬─╦═╦─┬─┬─┬─┬  ┌─┐
                                      ││░│░│░│░║3║░│░│░│░│  │0│
                                      │┴─┴─┴─┴─╩═╩─┴─┴─┴─┴  └─┘
                                      │после добавить
                                      │┬─┬─┬─┬─╦═╦─┬─┬─┬─┬  ┌─┐
                                      ││░│░│░│0║3║░│░│░│░│  │0│
                                      │┴─┴─┴─┴─╩═╩─┴─┴─┴─┴  └─┘
                                      │
   // Подготовка к новому обороту     │
   ОБМЕН                              │┬─┬─┬─┬─╦═╦─┬─┬─┬─┬  ┌─┐
   ПИШИ 1                             ││░│░│░│0║3║░│░│░│░│  │1│
   ОБМЕН                              │┴─┴─┴─┴─╩═╩─┴─┴─┴─┴  └─┘
 }                                    │       │
                                      │это последняя цифра двоичного
                                      │представления.
                                      │------------------------------
                                      │Цикл закончен. Дописываем слева
 // Добавить x в начало записи        │к записи первую цифру.
                                      │
                                      │перед добавить
 ЯЩИК+ ПИШИ ПУСТО                     ├┬─┬─┬─┬─╦═╦─┬─┬─┬─┬  ┌─┐
 добавить                             ││░│░│1│0║░║░│░│░│░│  │1│
КОНЕЦ                                 ├┴─┴─┴─┴─╩═╩─┴─┴─┴─┴  └─┘
                                      │после добавить
                                      │┬─┬─┬─╦═╦─╥─┬─┬─┬─┬  ┌─┐
                                      ││░│1│1║0║░║░│░│░│░│  │1│
                                      │┴─┴─┴─╩═╩─╨─┴─┴─┴─┴  └─┘
                                      │На ленте осталось двоичное
                                      │представление исходного числа.
                                      │
// Нахождение остатка и целой         │
// части от деления на 2              │
// Вход:  окошко на символе-числе     │
// Выход: символ заменен на остаток,  │
//        а справа -- целая часть.    │
ЭТО деление                           │
 ОБМЕН                                │
 ПИШИ 1                               │
 ОБМЕН                                │
 // сначала целая часть -- 0          │
 ВПРАВО ПИШИ 0 ВЛЕВО                  │
 // вычитаем из числа 2, прибавляя    │
 // 1 к целой части                   │
 ПОКА Я<Л                             │
 {                                    │
   МИНУС МИНУС                        │
   ВПРАВО ПЛЮС ВЛЕВО                  │
 }                                    │
КОНЕЦ                                 │
                                      │
// Добавить цифру в начало записи     │
// Вход:  цифра в ящике, окно справа  │
//        от записи                   │
// Выход: цифра добавлена, окно справа│
//        от записи                   │
ЭТО добавить                          │
 ВЛЕВО                                │
 ПОКА НЕ ПУСТО ВЛЕВО                  │
 ЯЩИК-                                │
 ПОКА НЕ ПУСТО ВПРАВО                 │
 ВЛЕВО                                │
КОНЕЦ                                 │


9----------------------------------------------------------------------
Задача 9 (6 баллов) Проверка программы.
--------

Определение
-----------
<программа>   := <команда>|<программа><команда>
<команда>     := <простая>|<цикл>
<простая>     := л|п|в|н
<цикл>        := ц<повторитель><команда>
<повторитель> := 4|5

Проверить, является ли запись на ленте программой.
В начальный момент окно расположено слева перед записью:

┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬
│░│░║░║з│а│п│и│с│ь│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴

Если проверяемая запись -- программа, написать следом за ней сообщение
"ок":

┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
│░│░│░│з│а│п│и│с│ь│░│о│к│░│
┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴

Если запись -- не программа, записать следом за ней сообщение "ош" и
поставить окно на первый неверный символ:

┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬
│░│░│░│з│а║п║и│с│ь│░│о│ш│░│
┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴

Решение
-------

А л г о р и т м

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

                         л,п,в,н
                        ┌───────┐
                        V       │
┌───────────┐л,п,в,н  ┌─────────┴─┐ПУСТО    ┌───────────┐
│    вход   ├────────>│  простая  │────────>│ программа │
└─────┬─────┘         └─┬─────────┘         └───────────┘
   ^  │ц               ц│
   │  │   ┌─────────────┘
4,5│  V   V
┌───────────┐
│  цикл     │
└───────────┘


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

П р о г р а м м а

ЭТО вход                        │ начальное состояние (вход)
  шаг                           │
  ЕСЛИ       л ТО простая       │
  ИНАЧЕ ЕСЛИ п ТО простая       │
  ИНАЧЕ ЕСЛИ в ТО простая       │
  ИНАЧЕ ЕСЛИ н ТО простая       │
  ИНАЧЕ ЕСЛИ ц ТО цикл          │
  ИНАЧЕ           ошибка        │
КОНЕЦ                           │
                                │
ЭТО простая                     │ состояние (простая)
  шаг                           │
  ЕСЛИ       л     ТО простая   │
  ИНАЧЕ ЕСЛИ п     ТО простая   │
  ИНАЧЕ ЕСЛИ в     ТО простая   │
  ИНАЧЕ ЕСЛИ н     ТО простая   │
  ИНАЧЕ ЕСЛИ ц     ТО цикл      │
  ИНАЧЕ ЕСЛИ ПУСТО ТО программа │
  ИНАЧЕ               ошибка    │
КОНЕЦ                           │
                                │
ЭТО программа                   │ конечное состояние (программа)
  СТОЯТЬ                        │
КОНЕЦ                           │
                                │
ЭТО цикл                        │ состояние (цикл)
  шаг                           │
  ЕСЛИ       4 ТО вход          │
  ИНАЧЕ ЕСЛИ 5 ТО вход          │
  ИНАЧЕ           ошибка        │
КОНЕЦ                           │
                                │
ЭТО ошибка                      │ состояние (ошибка)
 шаг                            │
 ЕСЛИ НЕ ПУСТО ТО ошибка        │
 ИНАЧЕ                          │ Запись сообщения и
 {                              │ возврат к месту ошибки.
   ВПРАВО ПИШИ о                │
   ВПРАВО ПИШИ ш                │
   ВЛЕВО ВЛЕВО                  │
 }                              │
 ВЛЕВО                          │
КОНЕЦ                           │
                                │
ЭТО шаг                         │ Шаг в следующую клетку.
 ВПРАВО                         │
КОНЕЦ                           │
                                │


a----------------------------------------------------------------------
Задача a (9 баллов) Самое длинное слово.
--------
На ленте записан текст, состоящий из слов. Каждое слово завершает один
пробел. Найти самое длинное слово в тексте. Известно, что:

-- в словах нет цифр (символов 0,1,2,3,4,5,6,7,8,9);
-- в тексте нет слов длиннее 10 символов.

Установить окошко Корректора на начало самого длинного слова.
В начальный момент окошко расположено перед текстом.

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

Начальное состояние              После работы программы
╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬    ┬─╥─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬
║░║а│х│ │э│т│о│т│ │к│о│т│ │░│    │░║а│х│ ║э║т│о│т│ │к│о│т│ │░│
╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴    ┴─╨─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴

Решение
-------
Почти четыре прохода.

А л г о р и т м
1) Первый проход. Вычисляем длины и записываем их на место пробела за
   каждым словом.
2) Второй проход. Заносим максимальную длину в ящик.
3) Третий проход. Идем к максимальному числу, по пути заменяя все
   числа на пробелы. Когда первое максимальное число найдено,
   идем до конца записи стирая все числа, закручивая рекурсивную
   пружину. Когда запись пройдена до конца (полный третий проход),
   возвращаемся на место максимального числа при помощи пружины
   (часть четвертого прохода).
4) Сейчас окошко за концом нужного слова. Процедура начало
   перемещает его на начало этого слова.

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


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

Можно рекомендовать такую организацию работы программы.

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

Например:

713

Это означает, что нужно решить задачу о башне с 7 кольцами, перенеся
ее со стержня 1 на стержень 3.

Нужно получить на ленте запись последовательности переносов, которая
решает задачу. Каждый перенос можно кодировать, например, тремя
символами:

-- пробел
-- откуда
-- куда

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

Решение
-------
Решения у куратора нет.
