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

З А Д А Ч И
- - - - - -
март, 2000 (C) А.А.Дуванов

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

                                                Олег Какаулин

Будем считать, что лента Корректора достаточно длинная и краевые
эффекты в решениях можно не учитывать. (Известно, что длина ленты
настраивается в файле kor.ini.)

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

При оценке решений будет учитываться:

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


Задача 1  (5 баллов)
--------
На ленте записана последовательность нулей и единиц. Выяснить, какая
цифра встречается чаще. Разместить ее справа от записи числа через
пустую клетку. Если число нулей и единиц одинаково, в качестве ответа
записать символ "=".

Длина последовательности меньше длины алфавита Корректора. В начальный
момент окошко расположено перед записью числа.

Пример работы программы:

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

Задача 2 (8 баллов)
--------
На ленте расположены две записи через пустую клетку друг от друга.
Сформировать третью запись, состоящую из одинаковых символов первых
двух записей.


Пример работы программы:

Начальное состояние                 После работы программы
╦═╦─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬     ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─╦═╦─┬─┬
║░║п│а│п│а│░│п│а│ш│а│░│  ─> │░│п│а│п│а│░│п│а│ш│а│░║п║а│░│
╩═╩─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴     ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─╩═╩─┴─┴

Задача 3 (5 баллов)
--------
На ленте записана последовательность из цифр 0, 1 и 2. Переставить
члены последовательности так, чтобы сначала располагались все нули,
затем все единицы и, наконец, все двойки.

Длина последовательности меньше длины алфавита Корректора. В начальный
момент окошко расположено перед записью.

Пример работы программы:

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

Задача 4 (5 баллов)
--------
На ленте записана последовательность символов. Известно, что
среди символов два и только два одинаковые. Установить окно
на первый из этих символов.

Длина последовательности меньше длины алфавита Корректора. В начальный
момент окошко расположено перед записью.

Пример работы программы:

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

Задача 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│
┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┘             ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴

Задача 6 (10 баллов)
--------
На ленте Корректора записано целое положительное число в двоичной
системе счисления. Перевести это число в десятичную систему.

В начальный момент окошко установлено перед записью числа.


Пример работы программы:

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

Задача 7 (10 баллов)
--------
На ленте Корректора записано натуральное число в римской системе
счисления. Перевести это число в десятичную систему.

Для обозначения цифр римской системы счисления используйте следующие
обозначения:

I - 1  (единица)
V - 5  (пять)
X - а  (десять)
L - (  (пятьдесят)

В начальный момент окошко установлено перед записью числа.


Пример работы программы:

Начальное состояние                После работы программы
┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┐              ┬─┬─┬─┬─┬─┬─┬─┬─┬─╦═╦
│░║░║а│а│а│1│5│░│░│░│   ──────>    │░│░│а│а│а│1│5│=│3║4║
┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┘              ┴─┴─┴─┴─┴─┴─┴─┴─┴─╩═╩

Задача 8 (30 баллов)
--------
Построим в среде Корректора вычислительную машину Малыш.

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

Будем считать, что в алфавите Корректора:

ПУСТО 0 1 2 3 4 5 6 7 8 9 а б в г д е ж з и й к л
м н о п р с т у ф х ц ч ш щ ъ ы ь э ю я   - + / *
= < > ( ) [ ] { } . , ! ? ; : ' " # | $ % ~ @

символы пронумерованы, начиная с символа "0", а символ ПУСТО занимает
особое положение и номера не имеет.

Символ "0" имеет  номер 0
Символ "1" имеет  номер 1
....
Символ "9" имеет  номер 9
Символ "а" имеет  номер 10
Символ "б" имеет  номер 11
Символ "в" имеет  номер 12
....


Система команд Малыша
---------------------

Каждая команда занимает две клетки на ленте Корректора.

┌─┬─┐
│з│z│ записать символ z в ящик  (я:=z)
└─┴─┘
┌─┬─┐
│+│z│ сложить содержимое ящика с символом z (я:=я+z)
└─┴─┘
Сложение работает так: складываются порядковые номера символов и
результатом является символ с результирующим порядковым номером в
алфавите Корректора. Например:
8+4=в
а+а=к

┌─┬─┐
│-│z│ вычесть из содержимого ящика символ z (я:=я-z)
└─┴─┘

Вычитание работает так: результатом является символ, порядковый номер
которого равен разности порядковых номеров символов, участвующих в
операции. Например:
ю-ю=0
9-5=4
д-9=5

┌─┬─┐
│п│z│ Повторить выполнение следующей команды (повтори z)
└─┴─┘
Число повторов определяется порядковым номером символа "z" в алфавите
Корректора. В программе эта команда не может следовать подряд
несколько раз, то есть, программа, в которой, например, встречается
запись "п5п5" считается неверной.
Пример:

з2п2+3 -- в результате работы этой программы в ящике окажется символ "8".

┌─┬──────┐
│я│ПРОБЕЛ│ Повторить выполнение следующей команды столько раз,
└─┴──────┘ каков порядковый номер символа в ящике перед началом
           работы команды (повтори "я"). Эта команда также не может
           следовать в программе несколько раз подряд.

Пример:
з2я +3 -- в результате в ящике окажется символ "8".

Алгоритм выполнения программы
------------------------------
В начальный момент Малыш записывает в ящик символ "0", затем выполняет
программу последовательно слева направо. Когда выполнена последняя
команда, Малыш печатает через пустую клетку от программы содержимое
ящика в виде: символ=числовое значение. Например, если в ящике
оказался символ "в", Малыш напечатает:
в=12

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

Задание
-------
1) (7 баллов) Запишите определение программы для Малыша формулами
Бэкуса-Наура, нарисуйте синтаксическую диаграмму переходов для
построенного определения. Пустую ленту можно считать корректной
программой.

2) (4 баллов) Напишите программу синтаксического анализатора для
проверки правильности записи программы Малыша. Если в записи
обнаруживаются ошибка, Корректор пишет в конце программы Малыша слово
"ош" и устанавливает окошко на место обнаруженной ошибки, если ошибок
нет, окошко устанавливается перед началом программы Малыша.

3) (10 баллов) Напишите для Корректора программу-интерпретатор. Эта
программа должна читать с ленты Корректора программу Малыша и
выполнять ее. Если выполнение программы заканчивается без авоста,
Корректор должен справа от программы записать на ленту содержимое
ящика в виде: символ=числовое значение.

4) (1 балл) Объедините синтаксический анализатор и интерпретатор в
одну программу: сначала должен работать анализатор, затем, если ошибок
в записи программы нет -- интерпретатор. Какой ответ получит Малыш,
выполняя такую программу:

+2па+1

Проверьте ваш ответ на построенной модели.

5) (3 балла) Напишите для Малыша программы нижеприведенных задач,
затем проверьте их работу на построенной модели.

Вычислить:
    2
а) x + x, при x = 3, 4, 5

     2
б) 2x  + 1, при x = 3, 4, 5

    2
в) x  + 2x, при x = 5, 6, 7


6) (6 баллов) Придумайте для Малыша три новых задачи, напишите их
решение, проверьте работу полученных программ на построенном
трансляторе.
