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

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

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


Задача 1 "От и до"

Описание алгоритма
Сначала проверим, есть ли в алфавите Корректора искомые символы. 
Их нет в двух случаях:
1) когда правый символ- ПУСТО и левый можно не проверять;
2) когда порядковый номер левого символа больше или равен
   порядковому номеру правого символа, уменьшенного на единицу.

Если случаи 1) и 2) не имеют места, последовательно записываем
на ленту символы, "большие" левого до тех пор, пока они 
"меньше" правого символа, уменьшенного на единицу.

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

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

Проверяем данные и выводим на ленту "нет", если имеют место случаи 1) и 2).
(После проверки в ящике остается символ, на единицу меньший правого).
В противном случае 
1. перемещаем окно на левый символ и заменяем символ в окне
   на следущий по алфавиту 
3. Пока символ на ленте меньше символа в ящике:
   3.1 меняеем символы на ленте и в ящике местами;
   3.2 сдвигаем окно на одну ячейку вправо и копируем символ из ящика 
       на ленту;
   3.3 увеличиваем символ на ленте на единицу;
   3.4 сдвигаем окно влево и опять меням местами симолы на ленте и в ящике,
       восстанавливая в ящике символ, который будет выведен последним;
   3.5 сдвигаем окно вправо




Задача 2 "Сколько нулей, сколько единиц?"
Описание алгоритма

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

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

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

Для подсчета нулей записываем в ящик символ "0". Перемещаем
окошко Корректора вправо.
Если очередной символ- "0", увеличиваем содержимое ящика на 1,
стираем символ и рекурсивно запускаем процедуру без отложенных команд.
Если очередной символ "1", то стираем его и перезапускаем процедуру, 
откладывая команду ПЛЮС.
Если очередной символ "ПУСТО", то копируем на ленту содержимое ящика,
передвигаем окошко вправо, записываем на ленту символ "0". Отложенные
команды ПЛЮС увеличат "0" на количество единиц в записи. 
                  

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

Первые три цифры суммируем с помощью ящика, а последние три прямо 
на ленте. Сравнивая число на ленте и число в ящике, выводим на ленту
"Да" или "Нет".

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

1. Скопируем в ящик первый символ записи, удалим его с ленты.
2. Добавим к содержимому ящика два следующих числа, стирая их с ленты
   по стандартному алгоритму (уменьшаем на 1 число на ленте и увеличиваем
   на 1 число в ящике до тех пор, пока на ленте не 0)
3. Сложим 4-е и 5-е число прямо на ленте без использования ящика,
   но по тому же алгоритму. При этом 4-е число уменьшаем до 0, а 5-е
   увеличиваем. Ячейку, где было 4-е число, очищаем.
4. Аналогично прибавим к сумме 4-го и 5-го чисел последнее, 6-е число
5. Сравниваем символы на ленте и в ящике

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

Рекурсивно двигаемся вдоль записи, делая по два шага вправо, 
запоминая количество пар символов отложенной командой ВЛЕВО.
Обнаружив символ ПУСТО, записываем символ слева от него в ящик.
Рекурсивная пружина возвратит окно к середине записи.

Если в ящике оказался символ "ПУСТО", значит количество символов 
в записи было четно и нужно сдвинуть правую половину записи вправо
на один символ и вернуться к "разрыву". В противном случае сдвиг не нужен,
окно показывает на середину записи с нечетным количеством символов.

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

Задача 5 "Смешаное сложение"
Описание алгоритма

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

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

Задача 6 "Горка из чисел"
Описание алгоритма

Рекурсивно уменьшаем исходный символ до ПУСТО, последовательно
вычитая по единице и запоминая в стеке количество этих вычитаний.
Отложенные команды записывают на ленту все символы от ПУСТО до 
исходного в порядке возрастания. (В гору)

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

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

Задача 7 "Жребий на пальцах"
Описание алгоритма
Идея решения: если сумма пальцев нечетна, то жребий падает на того,
кто выбросил меньше пальцев, иначе на партнера.

1. Получаем сумму двух символов стандартным способом (уменьшая один до 0
   и увеличивая другой). При этом один из символов копируем на 
   ленту, т.к. необходимо сохранить исходные символы.
2. Определяем четность- нечетность суммы. Вычитаем из суммы по 2, 
   пока не получим 1 или 2. Если получаем 1, ставим окошко на символ
   с меньшим порядковым номером, иначе на соседний.

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

Задача 8 "Кому выходить?"
Описание алгоритма

Идея решения: если слов в считалочке не больше, чем людей, то результат
равен количеству слов в считалочке. В противном случае результат равен 
остатку от деления количества слов на количество людей.

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

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

Задача 9 "Кто останется?"

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

1. Выпишем номера считающихся на ленту справа налево в порядке
убывания, рекурсивно запомнив количество раз, которое необходимо
выполнить считалочку. Слева допишем символ "0"- место начала счета.

2. Вернемся к исходному символу m, обозначающему количество слов
в считалочке, уменьшим его на единицу (в связи с тем, что "0" считать
не нужно) и скопируем в ящик.

3. "Отпустим" рекурсивную пружину. 
    Каждое выполнение считалочки состоит в:
    3.1 поиске символа "0"
    3.2 удалением нуля со сдвигом 
    3.2 перемещению вдоль выписанных номеров с уменьшением содержимого
        ящика на единицу на каждом шаге, причем
        3.2.1 при достижении правого края выписанных номеров
              следует вернуться к левому краю и продолжить перемещение
        3.2.2 при достижении нуля в ящике записать "0" на ленту
              и вернуться к символу, хранящему число m-1, чтобы
              восстановить его в ящике для следующего прохода

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

Задача а "Умножение палочек"

Описание алгоритма
Удаляем с ленты палочки первого числа, запоминая в рекурсивном стеке
их количество. При выходе из рекурсивного повторения получим в ящике
символ, равный второму палочному числу, путем счета в ящике. 

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

Как не потерять второе число в ящике? Ведь мы будем уменьшать его до нуля,
рисуя на ленте палочки. Значит, вычитать из ящика по единице придется
тоже рекурсивно, закручивая "внутреннюю пружинку" и откладывая команду
ПЛЮС. Когда в ящике останется символ "ноль", пружинка сработает и восстановит
второе число.

Таким образом, пружина, "закрученная" в самом начале, будет запускать
"внутреннюю" пружинку нужное количество раз.

Еще раз восхищаюсь красотой задачи и её автором Артёмом!

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

Задача b "Простые числа"

Описание алгоритма
Идея решения (от автора задачи В.П.Семенко): 
использовать алгоритм "решето Эратосфена".

Суть "решета" в том, чтобы удалять (прокалывать) на числовой оси целые числа,
кратные двум:

2 3 0 5 0 7 0 9 0 11 0 13 0 ...,

затем- кратные следующему "непроколотому" числу, т.е. трем:

2 3 0 5 0 7 0 0 0 11 0 13 0 ... и так далее. 

Здесь нули- это "дырки", оставшиеся от составных чисел.

Именно символ "0" удобно использовать для "выкалывания" чисел на ленте
Корректора.

Алгоритм:

1. Копируем исходный символ на ленте справа через пустую клетку (его следует
   сохранить по условию задачи)
2. Выписываем все целые числа от исходного до 2 на ленту влево
3. Установим окно на символ "2"
4. ПОКА не пройдем весь ряд, выполняем "решето":
   4.1 Копируем символ на ленте в ящик
   4.2 ПОКА не дойдем до конца ряда:
       4.2.1 запускаем рекурсивную поцедуру "прокалывай", которая:
         4.2.1.1 Двигает окно вправо на одну ячейку, уменьшая содержимое 
         ящика на 1, запоминая в рекурсивном стеке количество шагов 
         (отложенная команда ПЛЮС) до получения нуля в ящике.
         4.2.1.2 Если окно попадает на ПУСТО (конец ряда), то помещаем его 
         в ящик как признак достижения конца ряда, пользуясь командой ОБМЕН.
         Пружинка 4.2.1.1 после этого увеличит содержимое ленты на количество
         сделанных ранее шагов.
         4.2.2.2 Если в ящике получен 0, та же пружинка 4.2 восстановит
         в ящике "шаг прокалывания".
      4.2.2 Проверяем содержимое ящика. 
        4.2.2.1 Если в ящике не символ "ПУСТО", то делаем "прокол", 
        т.е. заменяем число на ленте нулем;
        4.2.2.2 Если в ящике символ "ПУСТО", то возвращаемся к числу, с которого
        начинали "прокалывание", т.е передвигаем окошко влево до совпадения
        символов на ленте и в ящике.
     4.2.3 Сдвигаем окно Корректора вправо к следующему символу записи
     4.2.4 Пока в окошке ноль, двигаем окно вправо
5. Уплотняем ряд простых чисел, удаляя нули и выполняя стандартный сдвиг
6. Восстанавливаем исходный символ.

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

Задача c "Хохотунчики"

Диаграмма переходов полностью описывает алгоритм и позволяет
очень бысто и надёжно составить программу.

Для демонстрации полного соответствия кода процедуры диаграмме
переходов справа приведен текст процедуры "Слово".
Сокращение в.о. на диаграмме означает "всё остальное".

   ┌──────────┐             
   │ ┌──────┐ │             
   │ │    ┌─v─v──────┐             
   │ │    │   Вход   │       
   │ │    └───┬────┬─┘ в.о.
   │ │ ┌───┐ х│    └────────────┐
   │ │ │  ┌v──┴──────┐          │
   │ │ │  │   Слог   │          │
   │ │ │  └───┬────┬─┘ в.о.    ┌v─────┐
   │ │ │ а|и|о│    └───────────>Ошибка│
   │ │ │ ┌────┴──────┐         └^──^──┘
   │ │ │ │   Слово   │          │  │ ЭТО Слово
   │ │ │ └┬─┬──┬─┬──┬┘ в.о.     │  │  ВПРАВО
   │ │ │ х│ │  │,│! └───────────┘  │  ЕСЛИ       х      ТО Слог
   │ │ └──┘ │  │ │ ┌───────────┐   │  ИНАЧЕ ЕСЛИ ПРОБЕЛ ТО Вход
   │ └пробел┘  │ └─┤ Выражение │   │  ИНАЧЕ ЕСЛИ ,      ТО Запятая
   │           │   └───────────┘   │  ИНАЧЕ ЕСЛИ !      ТО Выражение
   │     ┌─────┴─────┐             │  ИНАЧЕ                Ошибка
   │     │ Запятая   │             │ КОНЕЦ
   │     └──┬────┬───┘ в.о.        │
   └─пробел─┘    └─────────────────┘

Процедура "Ошибка" рекурсивная. Она перемещает окно в конец записи,
откладывая команду ВЛЕВО для возврату к месту ошибки. Достигнув конца
записи, эта процедура выводит на ленту сообщение "ош" (ветвь ИНАЧЕ),
после чего срабатывает "пружинка" ВЛЕВО. Окно смещается к месту 
ошибочного символа:

ЭТО Ошибка                             
 Шаг                                   
 ЕСЛИ НЕ ПУСТО  //в конец              
  ТО Ошибка     //записи               
  ИНАЧЕ                                
  {                                    
   ВПРАВО ПИШИ о   //Вывод сообщения   
   ВПРАВО ПИШИ ш   //об ошибке         
   ПОВТОРИ 2 ВЛЕВО                     
  }                                    
 ВЛЕВО         //возврат к месту       
КОНЕЦ          //ошибки                



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