Решения задач от куратора
--------------------------

Задача 1 "Снежная горка"
Автор решения А.В.Рудь

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


Имя файла с программой 00011.сос
________________________________________________________
Задача 2 (о малышах)
Автор решения А.В.Рудь

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

Толкнуть верхний кубик. В зависимости от символа на нём
выполнить один из 4-х алгоритмов передвижения его к одной из "стен"
и возвращения к нижнему кубику.

Толкнуть нижний кубик. Если на нём символы К или Ж, то выполнить
точно те же действия, что и для верхнего кубика, только без возврата,
в противном случае выполнить те же действия с поправкой на 2 шага вверх.


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

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

Передвинуться вправо, затем вниз. Пока есть кубик (НЕ ПУСТО),
перевигаться вверх-вправо-вниз, двигая весь верхний ряд вправо
и постепенно сдвигая нижний ряд на строку вниз.

После этого (дойдя до пустой клетки) опустить верхний ряд на 2 
строки вниз и сдвинуть на клетку влево.


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

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

Найти начало левого ряда кубиков, затем его конец. С помощью 
рекурсии запомнить количество пустых клеток, откладывая 
команду ВЛЕВО.

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

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

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

Двигаем исполнителя вверх и дважды вниз, рекурсивно повторяя эти 
действия, пока кубики в одном из рядов не закончатся. При этом 
накапливаем отложенные команды ВЛЕВО.

Если обнаружится, что кончился верхний ряд, то проверяем, 
не кончился ли в этом же месте и нижний. 

 Если да, то устанавливаем исполнителя между рядами и рекурсивная
 пружина сработает "вхолостую", вернув Кукарачу к началу рядов.

 Если нет, то выравниваем нижний ряд (рекурсивно дойдя до его конца
 и откладывая команды ВЛЕВО) и удаляем его.

Если же раньше обнаружен конец нижнего ряда, то сразу ровняем верхний 
(тоже рекурсивно, с отложенной командой влево) и удаляем его,
"отпустив" рекурсивную "пружину".
 
Имя файла с программой 00051.сос
________________________________________________________
Задача 6 "Джип от джина"
Автор решения А.В.Рудь

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

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

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

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

Опускаясь по "ступенькам", откладываем только команду ВВЕРХ,
а после "подъёма" кубика находиим букву Н и заменяем на П.

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

________________________________________________________
Задача 7 "Выстроить в ряд"
Автор решения А.В.Рудь

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

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

1) Рекурсивно смещаем ряд справа от Кукарачи до тех пор, пока
   не кончится ряд на строку ниже. При этом откладываем команды
   ВЛЕВО.
2) Опускаем сдвинутый вправо ряд на 2 строки ниже, тоже запоминая
   количество кубиков в нём отложенной командой ВЛЕВО
3) "Подставляем" исполнителя под обе рекурсивные "пружины".
   Они срабатывают в обратном порядке, возвращая исполнителя
   к левому краю рядов.
4) смещаемся вниз-вправо-вниз, проверяя, есть ли внизу ещё ряды

  

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

Описание алгоритма
В этой задаче удобно применить теорию лексических анализаторов,
которая объясняется в книге для чтения. Формулы Бэкуса- Наура тут
не помогут, зато очень облегчает решение составление диаграммы 
переходов:

  ┌────────┐
  │  ┌───┐ │      ┌──┐
  │  │ ┌─v─v──────v┐ │     В зависимости от символа
  │  │ │   Вход    │ │     переход к процедуре его
  │  │ └──┬──┬───┬─┘ │     обработки ("во" означает "все остальное")
  │  │    ж  п   во  │
  │  │    ш  у   └───┘ ┌────────┐
  │  │    │  сто───────┤ Выброс │
  │  │    │   ┌──┐     └────────┘
  │  │ ┌──v───v─┐│
  │  │ │Проверка││  После ж или ш может опять идти
  │  │ └─┬──┬─┬─┘│  буква ж или ш!
  │  │   во ы жш─┘  Если ы - исправляем
  │  └───┘  │       Если все остальное - идем
  │    ┌────┴───┐   к следующему символу
  │    │ Замена │
  │    └───┬────┘
  └────────┘

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

Все рекурсивные вызовы, естественно, откладывают команду ВЛЕВО
для последующей "уборки"- выброса кубиков с буквой "Ы". 

Некоторую трудность представляет сам алгоритм замены Ы на И.
Я сделал так: Найдя кубик с буквой "Ы" после "Ж" или "Ш",
токнуть снизу следующую букву (чтобы отделить "И"), затем
поставить "И" на место, где была "Ы" и поправить ряд.

Буква "Ы" остается ниже, ожидая, когда рекурсия "погонит" 
Кукарачу обратно и он вытолкнет все "Ы" с поля. 

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

Описание алгоритма
Сдвигаем нижний ряд на 2*n клеток вправо, при этом рекурсией "измеряем" 
сторону квадратной доски. Причем "считаем" кубики парами, т.к. 
их количество заведомо чётно. Таким образом, в рекурсивном стеке мы 
запомнили число "n" из условия. 

В отложенную процедуру (тоже рекурсивную) включаем такие действия:

1)Подъём "выдвинутого" ряда на две строки вверх
2)Возврат к левому краю этого ряда

Таким образом, мы передвинем нижний ряд на 2*n строк вверх.
А нужно ещё на одну. И это нам "на руку", т.к. придётся ещё "задвигать
этот ряд влево на 2*n клеток. Опять рекурсией: поднимая- запоминаем 2*n,
а затем "пружина" двигает на столько же влево. Красота! 
Ещё раз- спасибо Виктору Петровичу!


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

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

Идея: отделить левую половину кубиков и каждый кубик из этой половины
заменить на "инверсивный" из правой половины. При этом не допустить
повторных замен.

Значит, кубики по ходу решения должны быть разделены на 3 части:

1) левая половина (каждый из этих кубиков будем заменять)
2) часть правой половины, ещё "не обменянная"
3) часть правой половины, уже участвовавшая в обмене

Разобьём ряд кубиков на 2 равные части (рекурсивно передвигаясь 
слева направо и запоминая каждый второй). Отложим команды для смещения
кубиков из правой половины на 3 ряда вниз. Вернём исполнителя к правому
краю левой половины ряда.

Пока слева от Кукарачи есть кубик (проверяется толканием),
выполняем обмен:

--------начало обмена--------------------

1. двигаем очередной кубик вниз, на строку ниже правой половины исходного
ряда;
2. рекурсивно двигаем этот кубик вправо, пока не найдём соответствующий
кубик для замены (если "тащим" 0- то единицу, иначе ноль).

Причем:
2.1 если "толкаем воздух", т.е встречаем ПУСТО, то откладываем просто
команду ВЛЕВО для возврата;
2.2 если толкаем "неподходящие" кубики, то откладываем команды, 
возвращающие их на место (для будущих обменов)
2.3 найдя нужный кубик, оставляем ему "замену" на строку выше, чем остальные,
чтобы не обменять повторно

3. Благодаря замечательному свойству рекурсии и стека вообще, сначала
"выстрелит" пружинка 2.2 и поправит неиспользованные в обмене кубики,
а затем сработает другая пружинка- 2.1, которая и вернёт исполнителя 
вместе с кубиком точно к месту,  откуда он пришёл. 

4. Устанавливаем "выменянный" кубик на место унесённого

5. Проверяем, остались ли слева ещё кубики

-----конец обмена--------------------------------------------

После всех обменов вновь соединяем левую часть ряда с правой.


Имя файла с программой 000a1.сос

________________________________________________________
