Роботландский Университет 00/01
31 Азы программирования
Задачи турнира Кукарачи
-------------------------------


З А Д А Ч И
- - - - - -
ноябрь, 2000 (C) А.А.Дуванов

                             Но я раздумал о том,
                             Нельзя ли павиана
                             Заставить в бубен бить хвостом
                             И петь под фортепьяно.
                                                  Л.Кэрролл


Вступительное слово
-------------------

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

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

Для решения задач "9" и "a", необходимо повторить язык Бэкуса-Наура.
Перед записью программного кода обязательно нарисуйте диаграмму
переходов и эту схему прилагайте к решению как его составную часть.



Задача 1. (3 балла)  Программируемое перемещение.
Исполнитель расположен в левом верхнем углу поля, клетке (1,1). Где-то
в первом столбце расположен кубик с цифрой, справа от которого еще один
кубик с символом:

   1 2 3 4 5 6 7 8 9
  ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬
 1│¤│ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
 2│ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
 3│5│К│ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
 4│ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼

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

   1 2 3 4 5 6 7 8 9
  ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬
 1│¤│ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
 2│ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
 3│5│ │ │ │ │ │K│ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼
 4│ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼

Дополнительные условия:
1) Поле исполнителя бесконечно вправо и вниз.
2) Надпись на символьном кубике может быть любой.

Задача 2. (5 баллов)  Деление пополам.
На поле исполнителя из кубиков собран вертикальный столбик.
Исполнитель расположен слева перед первым кубиком основания:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │6│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │5│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │4│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │3│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │2│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │¤│1│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─

Разделить столбик на два, не нарушая вертикального расположения
кубиков:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │3│6│ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │2│5│ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │1│4│ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─


Дополнительные условия:
1) Поле исполнителя бесконечно по всем четырем направлениям.
2) Число кубиков в исходном столбике не меньше двух и четно.
3) Надписи на кубиках могут быть любыми.

Задача 3. (5 баллов)  Ракета.
На поле исполнителя из кубиков собран вертикальный столбик.
Исполнитель расположен слева перед первым кубиком основания:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │5│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │4│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │3│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │2│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │¤│1│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─

Построить из кубиков "ракету":

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │3│ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │2│ │5│ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │1│ │4│ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─


Дополнительные условия:
1) Поле исполнителя бесконечно по всем четырем направлениям.
2) Число кубиков в исходном столбике -- любое нечетное число большее одного.
3) Надписи на кубиках могут быть любыми.

Задача 4. (8 баллов) Опрокидывание столбика.
На поле исполнителя из кубиков собран вертикальный столбик.
Исполнитель расположен слева перед первым кубиком основания:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │5│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │4│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │3│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │2│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │¤│1│ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─

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

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─
   │¤│1│2│3│4│5│ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─

Дополнительные условия:

1) Поле исполнителя бесконечно по всем четырем направлениям.
2) Число кубиков в исходном столбике не меньше двух.
3) Надписи на кубиках могут быть любыми.


Задача 5. (7 баллов) Разобрать по бревнышку.
На поле исполнителя из кубиков собран прямоугольник высотой в четыре
кубика. Исполнитель расположен слева перед первым кубиком основания:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │a│b│c│ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │7│8│9│ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │4│5│6│ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │¤│1│2│3│ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼

Преобразовать прямоугольник в горизонтальный отрезок:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │ │ │ │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │ │ │ │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │ │ │ │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │¤│a│b│c│7│8│9│4│5│6│1│2│3│
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼


Дополнительные условия:

1) Поле исполнителя бесконечно по всем четырем направлениям.
2) Ширина прямоугольника -- любое число кубиков.
3) Надписи на кубиках могут быть любыми.

З а м е ч а н и е
Решение следующей задачи, конечно, решает и эту, частную. Но для
решения частной задачи можно придумать лучший алгоритм. С другой
стороны, решение частной задачи может подсказать алгоритм для решения
более общей.

Задача 6. (8 баллов) Разобрать по бревнышку 2.
На поле исполнителя из кубиков собран прямоугольник.
Исполнитель расположен слева перед первым кубиком основания:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │a│b│c│ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │7│8│9│ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │4│5│6│ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │¤│1│2│3│ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼

Преобразовать прямоугольник в горизонтальный отрезок:

  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │ │ │ │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │ │ │ │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │ │ │ │ │ │ │ │ │ │ │ │ │ │
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
   │¤│a│b│c│7│8│9│4│5│6│1│2│3│
  ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼


Дополнительные условия:

1) Поле исполнителя бесконечно по всем четырем направлениям.
2) Ширина и высота прямоугольника - произвольные.
3) Надписи на кубиках могут быть любыми.

Задача 7. (7 баллов) Кирпич на другой столбик.
На поле два столбика кирпичей. Снять верхний кирпич с первого
столбика, положить на второй столбик и вернуться в исходное положение
(слева от нижнего кирпича первого столбика). Столбики отстоят друг от
друга на две клетки:

  ├─┼─┼─┼─┼─┼─┼─┼─┼         ├─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │         │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼         ├─┼─┼─┼─┼─┼─┼─┼─┼
  │ │1│ │ │ │ │ │ │         │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼         ├─┼─┼─┼─┼─┼─┼─┼─┼
  │ │2│ │ │ │ │ │ │  ───>   │ │2│ │ │1│ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼         ├─┼─┼─┼─┼─┼─┼─┼─┼
  │¤│3│ │ │Ш│ │ │ │         │¤│3│ │ │Ш│ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼         ├─┼─┼─┼─┼─┼─┼─┼─┼
  │ │ │ │ │ │ │ │ │         │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼         ├─┼─┼─┼─┼─┼─┼─┼─┼

Дополнительные условия:

1) Поле исполнителя бесконечно вверх, вниз и вправо.
2) В первом столбике есть хотя бы один кирпич.
3) Во втором столбике кирпичи могут отсутствовать вовсе.
4) После выполнения задания столбики остаются на прежних местах.

Задача 8. (15 баллов) Ханойская башня.
Написать программу, которая решает на поле исполнителя задачу о
Ханойской башне.

П о с т а н о в к а  з а д а ч и
Имеются 3 стержня и кольца разных размеров. В начальный момент все
кольца нанизаны на первый стержень, при этом чем ниже кольцо, тем оно
больше. Надо перенести все кольца с первого стержня на третий (второй
стержень можно использовать как промежуточный). Правила переноса:
- за один ход можно перемещать только одно кольцо;
- кольцо можно перемещать либо на пустой стержень, либо на кольцо
большего размера.

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

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

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

¤запись

Если проверяемая запись - программа, установить Кукарачу в конец
записи:

 запись¤

Если запись - не программа, поставить исполнитель под первым неверным
символом:

запись
  ¤

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

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

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

¤запись

Если проверяемая запись - программа, установить Кукарачу в конец
записи:

 запись¤

Если запись - не программа, поставить исполнитель под первым неверным
символом:

запись
  ¤

Задача b (10 баллов) Исполнитель Кроха.

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

Определение
-----------
<программа>   := <команда>|<программа><команда>
<команда>     := л|п

Среда Крохи -- пятая строка поля Кукарачи без первой клетки. Кроха
отображается кубиком с надписью "К". В начальный момент Кроха может
быть в любом месте своей среды.

Напишите интерпретатор команд Крохи. Интерпретатор должен выполнять
программы, написанные для Крохи. В начальный момент Кукарача
расположен перед программой в клетке (3,1).


   1 2 3 4 5 6 7 8 9 10
  ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
1 │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
2 │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
3 │¤│п│р│о│г│р│а│м│м│а│
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
4 │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
5 │ │К│ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
6 │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
7 │ │ │ │ │ │ │ │ │ │ │
  ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼

С е м а н т и к а  к о м а н д
л - на одну клетку влево
п - на одну клетку вправо
