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

В начальный момент в ячейке памяти Автомата записано число 0, окно
установлено слева от программы, которая представляет собой
последовательность символов-команд "+" и "*". Автомат выполняет
последовательно команды программы и останавливается, когда программа
заканчивается.

Смысл команд:

"+" -- добавить к ячейки памяти 1;
"*" -- умножить ячейку памяти на 2.

Задание.

1) Построить исполнитель Автомат в среде Корректора.

2) Написать программу для Автомата (по возможности, короткую), выполняя
которую исполнитель получил бы в ячейке памяти число 61.

3) Придумать способ получения заданного числа n за наименьшее число
команд для исполнителя Автомат.

Замечание1. Автомат хранит число в ячейке памяти как символ алфавита
Корректора, считая числом порядковый номер этого символа в алфавите:

Символ │ Число
───────┼───────
  0    │ 0
  1    │ 1
  ...  │ ...
  9    │ 9
  а    │ 10
  б    │ 11
  ...  │ ...

Понятно, что Автомат может работать только с такими числами, которые
могут быть представлены символами алфавита Корректора.

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

Замечание 3. Если в программе для Автомата обнаружится ошибка, нужно
написать об этом сообщение "ош" в конце программы на ленте, а окошко
Корректора установить на место ошибки.


Пример. Получение Автоматом числа 11.

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


решение куратора
----------------

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


Приведенный выше код не проверяет правильность программы Автомата.
Для включения такой проверки придется заменить цикл ПОКА в процедуре
"автомат" на рекурсию:

ЭТО вход
 ПИШИ 0                                
 ОБМЕН                                 
 работа
КОНЕЦ                                  
                                       
ЭТО работа                             
 ВПРАВО                                
 ЕСЛИ   ПУСТО ТО ответ
 ИНАЧЕ ЕСЛИ + ТО { плюс работа }       
 ИНАЧЕ ЕСЛИ * ТО { умножить работа }
 ИНАЧЕ           ошибка                
КОНЕЦ                                  
                                       
ЭТО плюс
 ОБМЕН                                 
 ПЛЮС                                  
 ОБМЕН                                 
КОНЕЦ
                                       
ЭТО умножить                           
 ЯЩИК-                                 
 ПОКА НЕ 0
 {                                     
   МИНУС                               
   ОБМЕН
   ПЛЮС                                
   ОБМЕН                               
 }                                     
 ПИШИ *                                
КОНЕЦ
                                       
ЭТО ошибка
 ВПРАВО                                
 ЕСЛИ НЕ ПУСТО ТО ошибка               
 ИНАЧЕ                                 
 {
   ВПРАВО ПИШИ о ВПРАВО ПИШИ ш         
   ВЛЕВО ВЛЕВО                         
 }                                     
 ВЛЕВО
КОНЕЦ                                  
                                       
ЭТО ответ                              
                                       
 ВПРАВО ВПРАВО                         
 ПИШИ 0                                

 ОБМЕН                                 
 ПОКА НЕ 0                             
 {                                     
   МИНУС ОБМЕН                         
   плюс1
   возврат                             
   ОБМЕН
 }                                     
 ОБМЕН                                 
КОНЕЦ                                  

ЭТО возврат                            
 ПОКА НЕ ПУСТО ВПРАВО                  
 ВЛЕВО                                 
КОНЕЦ
                                       
ЭТО плюс1                              
 ПОКА 9                                
 {                                     
   ПИШИ 0                              
   ВЛЕВО                               
 }
 ЕСЛИ ПУСТО ТО ПИШИ 1                  
 ИНАЧЕ         ПЛЮС                    
КОНЕЦ                                  
                                       
Алгоритм построения оптимальной программы для Автомата
-------------------------------------------------------

Построение оптимальной программы надо начинать "с конца".

Покажем это построение на примере получения числа 11.

1) Число 11 может быть получено только командой "+" из числа 10.
Значит последняя команда -- "+".

2) Число 10 получается быстрее всего из числа 5 командой "*". Значит
предпоследняя команда -- "*".

3) Число 5 может быть получено только командой "+" из числа 4.

4) Число 4 получается командой "*" из числа 2.

5) Число 2 получается командой "*" из числа 1 (или командой "+")

6) Число 1 получается командой "+" из числа 0.

Таким образом получаем две оптимальные программы для Автомата,
получающие число 11 из числа 0 за 6 команд: "+**+*+" и "++*+*+"

Алгоритм автоматического построения программы для автомата
----------------------------------------------------------

ЭТО построение
  программа = ""
  ПОКА n не равно 0
  {
    ЕСЛИ n четное
     ТО
     {
       программа = "*" + программа
       n = n/2;
     }
    ИНАЧЕ
     ТО
     {
       программа = "+" + программа
       n = n-1;
     }
  }
КОНЕЦ

Замечание. Алгоритм записан на условном языке. Переменная "программа"
-- строковая. В начальный момент этой переменной присваивается пустая
строка:

программа = ""

Команды:

программа = "*" + программа

программа = "+" + программа

описывают соединение символа со строкой (операция конкатенации).

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

новая задача
------------
Возникает новая интересная задача для Корректора: по заданному на
ленте числу построить программу для Автомата, по которой это число
вычисляется.


                        * * *

Команды представили очень разнообразные алгоритмы для перевода
символа в десятичное число. Хотя никто не счел нужным описать свои
алгоритмы перевода, что конечно, плохо.

Типичные ошибки:

-- проверка правильности записи отдельным проходом
-- вычисление операций "+" и "*" не на месте, а на ленте за пределами
   записи


                        * * *

Команда 3101
------------
.\01\01.txt
.\01\010501.kor
Автор решения Казанцев Лёва
Оценка: 10

Описание алгоритма
------------------
Сначала я вношу в ящик нуль, затем в зависимости от знака я или
прибавляю к ящику единицу (если попадется +), или увеличиваю
содержимое ящика вдвое (если попадется *), потом, в зависимости от
символа в ящике (если он - не цифра), завершаю программу расшифровкой.

Программа для получения числа 61: +*+*+*+**+

Чтобы получить заданное число n, нужно выполнить обратные действия:
деление на 2 или, если число нечётное, вычитание 1 пока не получим 0,
например: 100-50-25-24-12-6-3-2-1-0. Затем двигаемся от 0 к числу n
справа налево и записываем действия, приводящие к результату.

комментарий куратора
--------------------
Грамотное решение. Явное пристрастие к рекурсии. Спецперевод символа в
двухзначное десятичное число:

ЭТО Конец                              
 ПОВТОРИ 2 ВПРАВО
 ОБМЕН
 ЕСЛИ НЕ ЦИФРА ТО Расшифровка
КОНЕЦ

ЭТО Расшифровка
 ЕСЛИ НЕ ЦИФРА ТО {
                   ПОВТОРИ 10 МИНУС    
                   Расшифровка         
                                       
                   ПЛЮС
                  }
            ИНАЧЕ {                    
                   ВЛЕВО               
                   ПИШИ 0              
                  }                    
КОНЕЦ                                  
                                       
Алгоритм этого кода ребята не объяснили, а комментарий не помешал бы.
Вроде такого:

Команда "ПОВТОРИ 10 МИНУС", выполняемая над символом из  ящика,
оставляет в ячейке младшую цифру результата (число единиц)
одновременно "считая" десятки при помощи отложенной команды ПЛЮС.
Когда младший разряд на ленте сформирован, окошко сдвигается влево, в
ячейку записывается 0 и "отпускается" рекурсивная пружина "ПЛЮС" -- на
ленту записывается число десятков.


Команда 3102
------------
.\02\02.txt
Авторы решения: Богатырев Геннадий
Оценка: 9.5

описание алгоритма
------------------
1) Записывает 0 в ящик и переходит к первому символу записи 
2) Организация цикла (условие окончания - конец записи) для вычисления
   суммы:
- проверяет символ записи:
  если +, то сравнивает содержимое ящика с символом "@" (последним символом
  к которому еще можно прибавлять 1) если больше, то выдает сообщение об ошибке,
  иначе увеличивает содержимое ящика на 1,
  если *, то сравнивает содержимое ящика с символом "э" (последним символом
  который еще можно умножать) если больше, то выдает сообщение об ошибке,
  иначе выполняет умножение (копирует содержимое ящика на ленту и пока не
  пусто вычитает 1 из содержимого окна и прибавляет к содержимому ящика 1,
  используя команду ОБМЕН)
3) Интерпретация результата вычисления:
- за записью написать 00
- пока содержимое ящика не станет равным 0:
  выполнять над содержимым ящика операцию МИНУС и содержимое окна ленты
  увеличивать на 1


Программа для Автомата получения числа 61:
   + * + * + * + * * +

Алгоритм получения заданного числа n за наименьшее число команд
  Пока число не станет равно 0 повторять следующие действия:
- проверить делится ли заданное число без остатка на 2,
- если да, то разделить  число на 2 и записать *
  иначе - вычесть единицу и записать +
  Выполнять операции * и + с конца


комментарий куратора
--------------------

Проверка на "переполнение" ящика не требовалась по условию задачи.
Корректор сам сообщит об этой ошибке своим "Не могу". В алгоритме вашей
проверки есть ошибки:

> если +, то сравнивает содержимое ящика с символом "@" (последним
> символом к которому еще можно прибавлять 1) если больше, то выдает
> сообщение об ошибке,

К символу "@" уже нельзя прибавить 1.

> если *, то сравнивает содержимое ящика с символом "э" (последним
> символом который еще можно умножать) если больше, то выдает сообщение
> об ошибке,

Символ "э" уже нельзя умножать на 2. На два умножаются только символ
"ш" и те, которые левее него в алфавите Корректора.

Достаточно сложный перевод символа в десятичное число.


Команда 3104
------------
.\04\04.txt
.\04\0451.kor
Коллективное решение
Оценка: 7

Описание алгоритма.
Отсутствует.

Нет построения программы для числа 61 и алгоритма построения
оптимальной программы.

комментарий куратора
--------------------

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

ЭТО РЕЗУЛЬТАТ                          
 ВПРАВО
 ЯЩИК-
 ЕСЛИ ЦИФРА                            
  ТО  СТОЯТЬ                           
  ИНАЧЕ                                
    {
     ПИШИ 0
     ОБМЕН                             
     ПОКА НЕ ЦИФРА                     
       {
        ПОВТОРИ 10 МИНУС               
        ОБМЕН                          
        ПЛЮС
        ОБМЕН
       }                               
     ОБМЕН                             
     ВПРАВО
     ЯЩИК-
    }                                  
КОНЕЦ

Замечание. Вместо

 ЕСЛИ ЦИФРА
  ТО  СТОЯТЬ                           
  ИНАЧЕ ...

лучше писать:

ЕСЛИ НЕ ЦИФРА ТО ...

Команда 3105
------------
.\05\05.txt
.\04\0551.kor
Автор: Решение коллективное
Оценка: 7

описание алгоритма
------------------
1. Осуществляем проверку правильности записи программы для Автомата (в
записи могут встречаться только + и * ). В случае обнаружения ошибки
перемещаемся в конец записи и пишем <ош>, затем используя отложенную
команду ВЛЕВО возвращаемся в ту позицию, где обнаружена ошибка. Если в
записи ошибок нет, то как только обнаружили ПУСТО, используя процедуру
Ошибок_нет возвращаемся на начало записи.

2. Помещаем в ящик нуль.

3. Двигаясь вдоль записи пока она не закончится проверяем какой знак в
окне. Используя процедуру Выполнение увеличиваем содержимое ящика на
единицу, если в окне +, или увеличиваем содержимое ящика в два раза
если в окне * (процедура Умножить_на_два). Умножение на два
осуществляется следующим образом: движемся в конец записи, при этом
закручивается рекурсивная пружина (чтобы вернуться на тот же символ на
котором остановились), используя процедуру Сложение увеличиваем
содержимое ящика вдвое и убираем вспомогательные записи, с помощью
отложенной команды ВЛЕВО возвращаемся в нужное место на ленте.

4. Пройдя всю запись, преобразовываем содержимое ящика в десятичное число.
Для этого записываем 0=00. Увеличиваем первое число и второй символ
второго числа  на 1 до тех пор пока первое число не совпадет с символом в
ящике, при этом как только второй символ во втором числе равен а , меняем его 
на ноль, а первый символ этой числа увеличиваем на 1. Трехзначные числа на
ленте Корректора не получаются (по условию задачи).

Мы предлагаем такую программу получения числа 61 для Автомата
       + + + * + * + * * + , и считаем ее оптимальной.

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

комментарий куратора
--------------------

Очень хорошее (понятное) описание алгоритма.
В алгоритме есть следующие неоптимальности:

-- проверка правильности отдельным проходом
-- выполнение команды "*" не на месте, а на ленте за программой.

Описание алгоритма получения оптимальной программы для автомата
верное, но программа для получения 61 является оптимальной.


Команда 3106
------------
Оценка: 9



Команда 3107
------------
.\07\07.txt
.\07\0751.kor
Автор решения Кондратюк Лена
Оценка: 3

описание алгоритма
------------------
1 поместить 0 в ящик
2 включить счетчик
3 записать результат

комментарий куратора
--------------------

Описание алгоритма очень туманно, программа -- полуфабрикат.


Команда 3108
------------
.\08\08.txt
.\08\0852.kor
Автор:  Екатерина Витальевна Мороз.
Оценка: 6

описание алгоритма
------------------
Проходя по программе Автомата выполнять команды "+" и "*" .
Выполнение команды Автомата "+" командой ПЛЮС .
Выполнение команды Автомата "*" командами МИНУС и ПЛЮС, 
где команда МИНУС заводит рекурсивную пружину, а команда ПЛЮС
раскручивает. Десятичное число записывается с помощью рекурсивной 
пружины и команды ПОВТОРИ  10 МИНУС. 

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

Команда 3110
------------
.\10\10.txt
Авторы: Хромов А. и Блем Д. 7 класс
Оценка:5

описание алгоритма
------------------
Данная программа работает в случае когда программа для автомата
записана корректно.
- в конце программы организуем счетчик через 7 -
  (-------- используем для умножения на два)                                     
-проходим последовательно всю программу
     если очередной символ + , то счетчик увеличить на 1
     если очередной символ *, то счетчик увеличиваем
        в 2 раза                                      


программа для получения с помощью автомата числа 61
     +*+*+*+**+

Алгоритм  получения любого числа N.
1.Если N четное, то в программу справа ставим операцию *, далее N:=N/2
  Если N не четное, то в программу справа ставим операцию +, далее N:=N-1
2. Пока N<>0, выполнять первый шаг.
3. КОНЕЦ.

комментарий куратора
--------------------
Нет проверки корректности программы Автомата.
Не оптимальное выполнение операций "+" и "*". Вместо вычислений с
ящиком используются вычисления на ленте.

Команда 3112
------------
.\12\12.txt
Авторы: Борисов Саша, Бурмистрова Юля, Полянинова Наташа.
Оценка:5.5

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

комментарий куратора
--------------------
Нет программы для получения числа 61.
Выполнение операции "*" выполняется не эффективно (не на месте,
а за пределами записи).

Первая звездочка в программе автомата расценивается Корректором как
ошибка.




Команда 3114
------------
.\14\14.txt
Авторы решения: не указаны
Оценка: 4

описание алгоритма
------------------
Отсутствует.

комментарий куратора
--------------------

Нет построения программы для числа 61. Нет алгоритма построения
оптимальной программы для автомата.

Проверка правильности программы Автомата делается отдельным проходом и
нет установки окошка на место ошибки.

Исходная запись стирается с ленты.
