Авторские решения задач
-----------------------
Задача 1 "Ёлка"
Автор решения А.В.Рудь

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

Имя файла с программой 001.сос
________________________________________________________
Задача 2 "Точка"
Автор решения А.В.Рудь, при участии Н.Е.Семёновой

Описание алгоритма
Передвигаем кубики на строку ниже, пока не встретим кубик
с точкой. Проверяем, есть ли после точки ещё кубик. Если нет, 
задача решена, иначе устанавливаем кубик с точкой над
оставшейся частью ряда, чтобы дальше передвигаться вместе с ним
до конца ряда. Найдя конец ряда, устанавливаем точку и уплотняем
ряд.

Имя файла с программой 002.сос
________________________________________________________
Задача 3 "Сортировка"
Автор решения А.В.Рудь

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

1) Передвигаем нули на 3 строки вверх, а единицы на одну,
рекурсивно откладывая команду ВЛЕВО для запоминания
количества единиц. Эта "пружинка" сработает, когда ряд
закончится, и уплотнит нули.

2) Сдвигаем нули на строку вниз, запоминая их количество
отложенной командой ВПРАВО. Именно столько раз нужно для
уплотнения единиц и сдвига в нужное положение.

3) Сдвигаем все единицы на ряд вверх.

Имя файла с программой 003.сос
________________________________________________________
Задача 4 "Распилить по метке"
Автор решения А.В.Рудь

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

1) Сдвигаем кубики, стоящие до метки включительно, на строку вверх,
рекурсивно запоминая их количество (отложенная команда ВЛЕВО).

2) Остальные кубики сдвигаем на 2 строки вверх 

3) "Подставляем" исполнителя под рекурсивную "пружинку" ВЛЕВО.
 
Имя файла с программой 004.сос
________________________________________________________
Задача 5 "Разделать на дрова"
Автор решения А.В.Рудь

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

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

1) Запоминает количество кубиков (отложенная команда ВЛЕВО)
2) Найдя правый конец "бревна", "задвигает" его на 2 клетки влево
3) Возвращает исполнителя к "поленнице"

Имя файла с программой 005.сос
________________________________________________________
Задача 6 "Распилить натрое"
Автор решения А.В.Рудь

В главной процедуре записана последовательность действий:

ЭТО Вход                               
 Треть     //Отделить третью часть     
 Половина  //Остаток пополам           
 Средняя   //Установка средней части   
 ПОВТОРИ 3 ВНИЗ                        
 Правая    //Поиск и установка отпи-   
           //ленной правой части       
 ВЛЕВО     //Поправка                  
КОНЕЦ                                  

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

   ПОВТОРИ 2 ВНИЗ  //Пружинка для      
   ПОВТОРИ 2 ВВЕРХ //смещения отпилен- 
   ВЛЕВО           //ной части вниз    

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

Имя файла с программой 006.сос
________________________________________________________
Задача 7 "Кукарача - перевозчик"
Автор решения А.В.Рудь

Описание алгоритма
Главная процедура реализует известный алгоритм решения
задачи о перевозке:

ЭТО Вход                               
 Коза   //Перевезти козу                               
 ВЛЕВО                                 
 Волк   //Перевезти волка                               
 ПОВТОРИ 2 ВПРАВО                      
 Коза_обратно //Перевезти козу обратно                         
 ПОВТОРИ 2 ВЛЕВО
 Капуста //Перевезти капусту                              
 Коза_2  //Перевезти козу                              
КОНЕЦ             

с поправками для установки исполнителя
в удобное положение.

Процедуры "Коза", "Волк", "Коза обратно", "Капуста" 
рекурсивные и устроены одинаково:

1.Сначала отыскивается объект перевозки с "запоминанием"
  количества сделанных шагов;
2.Объект перемещается на правый берег ("Коза обратно" - на левый)
3.Отложенными командами поправляются сдвинутые кубики
  
Имя файла с программой 007.сос
________________________________________________________
Задача 8 "Поменять кубики местами"
Автор решения А.В.Рудь

Описание алгоритма
Исполнитель толкает левый кубик вправо, пока не встретит
второй кубик, рекурсивно откладывая на каждом шаге команду
ВЛЕВО. Найдя правый кубик, устанавливает на его место левый,
устанавливает правый кубик слева от себя.
Здесь срабатывает "пружинка", передвигающая исполнителя влево
на столько же шагов, сколько было сделано вправо.
Осталось только поправить окончательное положение- передвинуть
бывший "правый" кубик в ту же строку.

Имя файла с программой 008.сос
________________________________________________________
Задача 9  "Треугольник"
Автор решения А.В.Рудь с ценной подсказкой Н.Е.Семёновой

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

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

Чтобы "не забыть" эти растояния, движение от А к В и от В к С
надо организовать рекурсивно, причем первая пружинка, "отвечающая"
за "расстояние АВ", должна сработать после "пружинки ВС".

Рекурсивно повторяя шаги для доставки А на место Б, доходим до Б,
но не отпускаем пружину (отложенную команды ВЛЕВО), а в ветви ИНАЧЕ
"закручиваем" вторую пружину (рекурсивную процедуру Тащи_2),
заставляя исполнителя откладывать команду ВВЕРХ:

ЭТО Тащи_1                           ЭТО Тащи_2
 Шаг                                  ВЛЕВО
 ЕСЛИ ПУСТО                           ЕСЛИ ПУСТО
  ТО Тащи_1                            ТО
  ИНАЧЕ                                {
  {                                     ВПРАВО ВНИЗ
    Установка_1                         Тащи_2
    Тащи_2     // К второй пружине     }
    ВПРАВО ВВЕРХ                       ИНАЧЕ Установка_2
  }                                   ВВЕРХ    //Вторая пружина
 ВЛЕВО   // Первая пружина           КОНЕЦ
КОНЕЦ                                  

Установка А на место В и В на место С (процедуры "Установка_1"
и "Установка_2") - дело техники, хотя при этом нужно еще и
исполнителя "приготовить" к продолжению работы. Нужно установить
Кукарачу и кубик в положение, удобное для толкания.

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

Но вопросы Н.Е.Семеновой навели меня на идею "тащить" кубик С
вверх и влево не внутри, а снаружи треугольника (т.е. справа от ВС
и выше АВ):
            ┌────┐
            .   А│
                 С
                В┘

Тогда "соседние" кубики друг другу не мешают, и
задача решается даже для плотно стоящих кубиков: АВ !
                                                  С

Интересно, найдут ли такое решение другие команды.


Имя файла с программой 009.сос
________________________________________________________
Задача а  "Проще некуда"
Автор решения А.В.Рудь

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

Но когда за дело берутся любители, не сильно отягощенные знанием
теории (имею в виду 6-классницу Катю- автора задачи и себя- автора
"неакадемического" решения), иногда случаются "неправильные
чудеса" :-)

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

ЭТО Вход                               
 ВПРАВО                                
 ЕСЛИ ПУСТО                            
  ТО                                   
  {                                    
   Вход                                
   Возврат  // Пружинка для возврата   
  }                                    
  ИНАЧЕ Обход
КОНЕЦ                                  

Вся хитрость- в отложенной процедуре "Возврат". Она должна
и кубик вернуть на место, и не дать Кукараче "забыть", откуда
начато обратное движение. А что, если к очевидной команде ВЛЕВО
добавить нечто пружиноподобное :-), чтобы, толкнув кубик влево
один раз, исполнитель возвращался назад?

ЭТО Возврат   // Передвинуть кубик     
 ВЛЕВО        // ВЛЕВО и вернуться     
 ЕСЛИ ПУСТО                            
  ТО Возврат                           
 ВПРАВО                                
КОНЕЦ                                  

Возможно, эти "дерганья" влево-вправо не достойны
академической науки, но какая красивая задача решена!

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

________________________________________________________
Задача b  "Проверка записи"

Решение 1 (Автор А.А.Дуванов)

------------из переписки с автором--------------------------------
Здесь задание не формулируется на языке БНФ (не надо его изучать).
Не предполагается предварительно строить синтаксическую диаграмму.
Но на этапе разбора полезно, конечно, привести и такое решение.
Для учителей и готовых это воспринять школьников.
---------------конец цитаты---------------------------------------

<нули> ::= 0|0<нули>
<единицы> ::= 1|11
<запись>::= <пусто>|<нули>|<единицы>|<нули><запись>|<единицы><нули><запись>


Определение не слишком красивое. И не помогает решению задачи.
А вот диаграмма очень красивая и помогает решению на 100%.


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

                0
     0    ┌────────────────────────┐
  ┌────┐  │     0                  │
  │    │  │ ┌────────┐             │
  V    │  V V        │             │
┌──────┴────┐   1  ┌─┴────┐   1  ┌─┴────┐ПУСТО ┌──────┐
│вход       ├─────>┤ед1   ├─────>┤ед11  ├─────>┤запись│
└──────┬────┘      └─┬────┘      └─┬────┘      └──────┘
       │             │             │     ПУСТО    ^
       └─────────────┴─────────────┴──────────────┘

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

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

ЭТО вход
  шаг                                  
  ЕСЛИ       0     ТО вход
  ИНАЧЕ ЕСЛИ 1     ТО ед1              
  ИНАЧЕ ЕСЛИ ПУСТО ТО запись           
  ИНАЧЕ               ошибка           
КОНЕЦ                                  
                                       
ЭТО ед1                                
  шаг                                  
  ЕСЛИ       0     ТО вход             
  ИНАЧЕ ЕСЛИ 1     ТО ед11             
  ИНАЧЕ ЕСЛИ ПУСТО ТО запись           
  ИНАЧЕ               ошибка           
КОНЕЦ
                                       
ЭТО ед11
  шаг
  ЕСЛИ       0     ТО вход             
  ИНАЧЕ ЕСЛИ ПУСТО ТО запись
  ИНАЧЕ               ошибка           
КОНЕЦ                                  
                                       
ЭТО запись                             
  ВВЕРХ
КОНЕЦ                                  
                                       
ЭТО ошибка                             
  шаг                                  
  ЕСЛИ НЕ ПУСТО ТО ошибка              
  ВЛЕВО                                
КОНЕЦ                                  
                                       
ЭТО шаг                                
  ВНИЗ                                 
  ВПРАВО                               
  ВВЕРХ
КОНЕЦ                                  



Решение 2 (Автор А.В.Рудь)

Определение 

<нули> ::=0|0<нули>
<единицы> ::=1|11
<запись>::=<нули>|<единицы>|<нули запись>|<единицы нули запись>


Диаграмма переходов 
                       ┌─────────┐
                       │  Вход   │
                       └─┬─┬──┬──┘
                         │ 1  0  ┌──────────┐
              ┌──────в.о.┘ │  │  │ ┌──────┐ │
              │            │  │  │ │┌───┐ │ │
              │            │┌─┴──┴─┴┴─┐ │ │ │
              │            ││  Ноль   │ │ │ │
              │            │└┬──┬─┬─┬─┘ │ │ │
          ┌───┴──┐         │ │  1 │ └0──┘ │ │   ┌───────┐
          │Ошибка├───в.о.──┼─┘  │ └─пусто─┼─┼───┤ Верно │
          └┬───┬─┘         │    │         │ │   └──┬──┬─┘
           │   │          ┌┴────┴──┐      │ │      │  │
           │   │          │Единица1│      │ │      │  │
           │   │          └─┬─┬─┬─┬┘      │ │      │  │
           │   └─────в.о.───┘ 1 0 └─пусто─┼─┼──────┘  │
           │                  │ └─────────┘ │         │
           │              ┌───┴────┐        │         │
           │              │Единица2│        │         │
           │              └─┬──┬─┬─┘        │         │
           └─────────в.о.───┘  0 └──пусто───┼─────────┘
                               └────────────┘

Примечание: в.о. означает "все остальное"

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


Как видите, решения отличаются. Привожу фрагметы нашего с А.А.Дувановым
обсуждения этой задачи.


АР> Но мне кажется, что по условию Вашей задачи пустая запись
АР> не является правильной!
АР>
АР> > Запись состоит из нулей и единиц. В ней не должно быть более двух
АР> > единиц, идущих подряд. Проверить правильность записи. 

АР> Прошу Вашего авторского согласия на такое понимание задачи.

ААД>Согласие даю, хотя и не исключаю варианта при котором число нулей и
ААД>единиц в записи окажется нулевым! Ведь явно не сказано про
ААД>неправильность пустоты, а что не запрещено, то...

ААД>Пустая запись состоит из нуля нулей и нуля единиц и в ней нет более
ААД>двух единиц идущих подряд!

ААД>Думаю, что не надо снижать оценку при любом варианте понимания
ААД>условия.

Как Вы думаете, коллеги, позволяет ли фраза из условия

> Запись состоит из нулей и единиц...

считать пустую запись правильной? 

Я думаю, что нет. Ведь пустая запись не состоит из нулей и единиц.
Она состоит из ... пустоты, или вообще ни из чего не состоит!
