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


З А Д А Ч И
- - - - - -
март, 2002 (C) А.В.Рудь,
предисловие частично заимствовано из
сборника задач турнира Корректора,
2001 (С) А.А.Дуванов

                                От малого большое зарождается.
                                (русская поговорка)

                                Non multum, sed multa.
                                "Не много, но многое"
                                (латинское крылатое выражение)
                                


  В конкурсе  Корректора  2001/2002 года предлагается 15 задач.
Вовсе не обязательно решить все задачи. Выбирайте по вкусу и по
силам, учитывая ограниченное время. Первые 6  задач - разминка.
Надеюсь, их решат все. Уверен, что будут разные решения. Будьте
внимательны, найдите самое оптимальное решение, тщательно  про-
тестируйте ваши программы, чтобы не потерять  баллы по невнима-
тельности. Остальные задачи потруднее и пообъемнее, для любите-
лей повозиться с Корректором как следует. Здесь очень пригодит-
ся опыт решения задач из турниров прошлых лет. Последняя задача,
как и в турнире Кукарачи, творческая.

Для всех задач действуют следующие соглашения:

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

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

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

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

В целях повышения удобочитаемости кода (что особенно важно при
перекрестных проверках) настоятельно рекомендуется:

-- Главную процедуру (с которой код начинает свою работу) именовать
   "Вход".
-- Имена всех процедур записывать в нижнем регистре, кроме первой
   буквы (не "ПРОХОД1", а "Проход1").
-- Использовать для процедур осмысленные имена, которые как-то
   документируют их работу ("фас!" -- это смешно, но "Поиск_цифры"
   -- гораздо лучше).
-- В кодах использовать краткие, но содержательные комментарии.
   Комментарии должны пояснять логику, а не "физику" работы кода.
   Такой комментарий плох (пуст):

   ВПРАВО // сдвигаем окошко вправо

   Этот лучше:

   ВПРАВО // к следующему символу записи

   Для каждой важной процедуры записывайте комментарий в виде:

   // <назначение процедуры>
   // Вход:  <где окно, что в ящике и на ленте>
   // Выход: <где окно, что в ящике и на ленте>

   Уверен, что эти рекомендации помогут, в первую очередь самим
   разработчикам, поэтому не откладывайте комментирование
   на последние полчаса перед посылкой работы на конкурс (чтобы
   удовлетворить "причудам" куратора).

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


Успехов вам в конкурсе и приятных минут рождения красивого решения!


Задача 1 "Сколько палочек?" (2 балла)
-----------------------------------
  На ленте записано палочное число. Окошко  Корректора слева от
него. Написать  на ленте справа от  палочек знак "="  и символ,
соответствующий количеству палочек.

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

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

Задача 2 "Поиск максимума" (3 балла)
-------------------------------------------
  Окошко Корректора  установлено на первом символе записи. Тре-
буется установить окошко на символ с наибольшим порядковым номером,
а все остальные символы удалить с ленты.

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

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

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

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

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

Задача 4 "Среднее арифметическое" (5 баллов)
-------------------------------------------
  На ленте в соседних ячейках находятся  два символа, изобража-
ющие числа.  Требуется  получить  на ленте символ, изображающий
среднее арифметическое исходных чисел. Если результат  - не це-
лое число, то на ленте должны быть два  соседних символа, изоб-
ражающие числа, наиболее близкие к результату.  В начальный мо-
мент в окошко Корректора виден левый символ.

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

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

Задача 5 "Разгадай шифр 1" (6 баллов)
-------------------------------------------
  На ленте некоторый набор символов, в окошко Корректора виден
первый слева символ. По приведенному примеру разгадайте шифр
и напишите программу для дешифровки.

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

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

Задача 6 "Разгадай шифр 2" (5 баллов)
-------------------------------------------
  На ленте  непонятная  запись:  "азагкда", в окошко Корректора
виден первый слева символ. Разгадайте шифр безо всяких примеров
и напишите программу для дешифровки. После  работы программы на
ленте должна быть расшифрованная запись.

Задача 7 "Умножение" (7 баллов)
-----------------------------
  На ленте в соседних ячейках находятся  два символа, изобража-
ющие перемножаемые числа. Эти числа таковы, что результат умно-
жения не превышает числа  69.  Требуется получить на ленте сим-
вол, изображающий  произведение исходных чисел. В начальный мо-
мент в окошко Корректора виден левый символ, после работы прог-
раммы в окошке виден символ, изображающий результат умножения.

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

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

Задача 8 "Деление с остатком" (7 баллов)
----------------------------------------

  На ленте  находятся  два  символа,  разделенные символом "/",
изображающие пример на деление целого числа на целое. Например,
а/3 означает десять разделить на 3. Требуется получить на ленте
результат деления нацело, а в ящике - остаток от деления. В на-
чальный момент в окошко Корректора виден символ "/".

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

Начальное состояние          После работы программы
           ╔═╗                              ╔═╗
           ║ ║                              ║1║
           ╚═╝                              ╚═╝
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬        ┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬
│░│а║/║3│░│░│░│░│░│░│░│  ─>    │░│░│░║3║░│░│░│░│░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴        ┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴

Задача 9 "Возведение в степень" (9 баллов)
------------------------------------------
  На ленте  находятся  два  символа,  разделенные символом "~",
изображающие пример  на  возведение числа в целую положительную
степень. Например, 2~3 означает два в третьей степени. Требует-
ся получить на  ленте результат возведения в степень в десятич-
ном виде. Исходные  два символа таковы, что результат вычисления
не превышает числа 69.  В  начальный момент в окошко Корректора
виден символ "~".

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

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

Задача а "Сократить дробь" (10 баллов)
--------------------------------------
  На ленте  находятся  два  символа,  разделенные символом "/",
изображающие правильную обыкновенную дробь. Например, 4/в озна-
чает четыре  двенадцатых.  Требуется,  если возможно, сократить
дробь. В начальный момент в окошко Корректора виден символ "/".

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

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


Задача b "Антиавтомат" (8 баллов) ( Соавтор задачи Лев Казанцев,
---------------------------------   учащийся школы 119 г. Снежинска)

  В системе  команд  Роботландского исполнителя Автомат всего 2
команды: + и *. Среда Автомата - индикатор, который в начальном
состоянии показывает число 0.
По команде "+" Автомат прибавляет к числу на индикаторе единицу;
по команде "*" Автомат умножает число на индикаторе на 2.
Например, выполняя программу "+**+*", Автомат получит число 10, т.к.
((0+1)*2*2+1)*2=10.
  На ленте Корректора единственный символ, видимый в окошко, изображающий
число, полученное Автоматом в результате выполнения некоторой программы.
Требуется восстановить и записать на ленту самую короткую программу для
получения этого числа.

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

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

Задача с "Скобки" (7 баллов)
-----------------------------
Запись на ленте состоит только из круглых скобок.
Запись считается неправильной в двух случаях:
1) в ней встретится закрывающая скобка, перед которой не было
непарной открывающей, например ())(, или
2) количество открывающих и закрывающих скобок во всей записи
неодинаково, например: ()(()
Проверить правильность записи. Если запись правильная, написать
после нее на ленте сообщение "ок", в противном случае написать
после нее "ош" и установить окошко Корректора на место ошибки.
В начальный момент окошко Корректора установлено перед записью.

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

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

Задача d (12 баллов) Проверка выражения.
----------------------------------------
  Выражение содержит  только  цифры, знаки "+", круглые скобки.
Все скобки парные, вложенных  скобок  нет, в скобках может быть
только сумма двух цифр. Выражение  не  может  ни начинаться, ни
заканчиваться знаком "+".
  Примеры выражений: 4 ; 7+2+3 ; (4+6) ; 8+(3+5)+(0+3)+2+(5+8)

1) Напишите определение выражения в нотации Бэкуса-Наура (до 3 баллов)
2) Составьте диаграмму переходов (до 4 баллов)
3) Запрограммируйте лексический анализатор, проверяющий, является ли
   запись на ленте выражением. Если запись - выражение, вычислите его 
   значение (до 5 баллов).

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

┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬─┬
│░│░║░║з│а│п│и│с│ь│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴─┴

Если проверяемая запись -- выражение, написать следом за ней знак =
и символ, изображающий значение выражения:

┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─╦═╦─┬
│░│░│░│5│+│(│3│+│4│)│=║в║░│
┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─╩═╩─┴

Если запись -- не выражение, записать следом за ней сообщение "ош" и
поставить окно на первый неверный символ:

┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┬
│░│░│░│з│а║п║и│с│ь│░│о│ш│░│
┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┴

Задача е (до 15 баллов).
-------------------------
Придумать собственную задачу для Корректора и решить ее.
Будет оцениваться:
1) качество формулировки - до 3 баллов;
2) новизна и красота задачи - до 6 баллов;
3) качество решения - до 6 баллов, но не более оценки 2)
