6. Турнир Корректора (сетевой Университет 98/99 учебного года)

                            ЗАДАЧИ
                            ~~~~~~

                            март 1999 (C) А.А.Дуванов и П.А.Кук

                                    А вы
                                    ноктюрн сыграть
                                    могли бы
                                    на флейте водосточных труб?

                                                 В.В.Маяковский


   В первых  6  задачах  нужно написать лексические анализаторы
для выражений, определяемых при помощи формул Бэкуса-Наура. Ос-
тальные задания конкурса посвящены "геометрическим" упражнениям
в среде исполнителя.


Задача 1. (5 баллов)
 Введем следующее определение:
Определение
-----------
<число> ::= <целое> | <дробь>
<целое> ::= <цифра> | <целое><цифра>
<дробь> ::= <простая> | <десятичная>
<простая> ::= <целое>/<целое>
<десятичная> ::= .<целое> | <целое>. | <целое>.<целое>
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

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

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

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

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


Задача 2. (8 баллов)
 Введем следующее определение:
Определение
-----------
<выражение> ::= <число>+<число> | <выражение>+<число>
<число> ::= <целое> | <дробь>
<целое> ::= <цифра> | <целое><цифра>
<дробь> ::= .<целое> | <целое>. | <целое>.<целое>
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

   Задание. Напишите программу, которая проверяет запись на лен-
те и помещает результат проверки справа от нее в виде  двух букв:
   ош - запись не является ни числом, ни выражением;
   чс - запись есть "число";
   вр - запись есть "выражение";

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

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

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

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

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

Задача 3. (9 баллов)
 Введем следующее определение:
Определение
-----------
<выражение> ::= <число> | <выражение>+<число>
<число>   ::= 0 | 1 | 2

   Задание. Напишите программу, которая вычисляет выражение, ес-
ли оно правильное,  или записывает на ленту сообщение "ош", если
запись содержит  ошибку. Если запись ошибочная, то дополнительно
к сообщению "ош" окошко должно указывать на первый неверный сим-
вол.
   Замечание 1. Значение выражения должно быть записано на ленте
в виде обычного целого десятичного числа.
   Замечание 2. Предполагается, что результат вычисления выраже-
ния не превышает длины алфавита Корректора.

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

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

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

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

Задача 4. (9 баллов)
 Введем следующее определение:
Определение
-----------
<выражение> ::= <число> | <выражение>+<число> | <выражение>-<число>
<число>   ::= 0 | 1 | 2

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

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

Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─┬─┬─╥─┬─╦═╦─┬─┐
│░│░║░║1│-│1│+│2│░│░│    ─────>     │░│░│░│1│-│1║+│2║=║2│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─┴─┴─╨─┴─╩═╩─┴─┘
Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┐
│░│░║░║1│░│░│░│░│░│░│    ─────>     │░│░│░│1║=║1│░│░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┘
Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐
│░│░║░║1│.│7│+│1│░│░│    ─────>     │░│░│░│1║.║7│+│1│░│о│ш│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘
Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐
│░│░║░║1│-│2│+│1│░│░│    ─────>     │░│░│░│1║-║2│+│1│░│а│в│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘

Задача 5. (10 баллов)
 Введем следующее определение:
Определение
-----------
<выражение> ::= <число> |
                <выражение>+<выражение> |
                <выражение>-<выражение> |
                (<выражение>)

<число>   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

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

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

Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─┬─┬─╥─┬─╦═╦─┬─┬─┐
│░│░║░║1│+│(│8│)│░│░│    ─────>     │░│░│░│1│+│(║8│)║░║о│к│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─┴─┴─╨─┴─╩═╩─┴─┴─┘
Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐
│░│░║░║1│░│░│░│░│░│░│    ─────>     │░│░│░│1║░║о│к│░│░│░│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘
Начальное состояние                 После работы программы
┬─┬─╦═╦─┬─┬─┬─┬─┬─┬─┐               ┬─┬─┬─┬─┬─┬─╦═╦─┬─┬─┬─┬─┐
│░│░║░║1│-│2│)│░│░│░│    ─────>     │░│░│░│1│-│2║)║░│о│ш│░│░│
┴─┴─╩═╩─┴─┴─┴─┴─┴─┴─┘               ┴─┴─┴─┴─┴─┴─╩═╩─┴─┴─┴─┴─┘

Задача 6. (15 баллов)
 Введем следующее определение:
Определение
-----------
<выражение> ::= <число> |
                <выражение>-<выражение> |
                <выражение>+<выражение> |
                (<выражение>)

<число>   ::=  1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

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

   Замечание 1. Значение выражения должно быть записано на ленте
в виде обычного целого десятичного числа.
   Замечание 2. Предполагается, что результат вычисления выраже-
ния  и  все промежуточные результаты не превышают числа,  равного
длине алфавита Корректора.
   Замечание 3. Считается, что конечный и  все промежуточный ре-
зультаты вычислений неотрицательные.

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

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


                 Геометрия на ленте Корректора

   Введем следующее определения.

   Определение 1. Под точкой в среде Корректора понимается любая
клетка  на  ленте. При письме будем обозначать точки  маленькими
латинскими буквами.

   Определение 2. Расстоянием  между двумя точками a и b называ-
ется неотрицательное целое  число  Pab, на единицу большее мини-
мального числа клеток между этими точками на ленте.
   Например, если a и b соседние клетки, то расстояние между ни-
ми равно единице (а не l-1, если за l обозначить длину склеенной
в кольцо ленты Корректора).
   Очевидно, что расстояние  между точками a и b равно минималь-
ному числу команд ВПРАВО (или ВЛЕВО),  необходимых для перемеще-
ния окна из точки a в точку b.

   Определение 3. Точка b  расположена  на ленте правее точки a,
если потребуется  Pab  команд  ВПРАВО Корректора для перемещения
окна из  точки a в  точку b. Соответственно, точка a расположена
левее точки b, если потребуется Pab команд ВЛЕВО для перемещения
окна из точки b в точку a.
   Обозначение операций отношений в этом тексте:
a = b  - точки совпадают
a # b  - точки не совпадают
а < b  - точка a левее точки b
а > b  - точка a правее точки b
а <= b - точка a левее точки b или совпадает с ней
а >= b - точка a правее точки b или совпадает с ней

   Вопрос 1.  Может ли точка  a быть одновременно левее и правее
точки b?
   Ответ. Да, если  точки  совпадают (то есть изображаются одной
клеткой). В этом случае записывают a = b.
   Вопрос 2.  Может ли точка  a быть одновременно левее и правее
точки b, если она с ней не совпадает?
   Ответ. Да. Например,  при длине ленты  равной 6, точка  a  на
следующем рисунке одновременно и левее и правее точки b:

                          ┌─┬─┬─┬─┬─┬─┐
                          │░│a│░│░│b│░│
                          └─┴─┴─┴─┴─┴─┘

   В наших рассмотрениях такие случаи учитывать не будем, считая
что длина ленты всегда существенно больше длины отрезка ab.

   Определение 4. Пусть a <= b. Отрезком ab  на ленте называется
множество точек c, таких что а <= c и одновременно c <= b. Точку
a называют началом отрезка, точку b - концом.

   Упражнение. Рассмотрим определение 4 без ограничения "Пусть a
<= b". Закрасьте клетки отрезка ab для 10-клеточной ленты:

                      ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
                      │ │ │ │b│ │ │a│ │ │ │
                      └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘

   Определение 5. Длиной отрезка ab называется число Pab равное
расстоянию между точками a и b.

   Заметим, что в силу определений, если точка c принадлежит от-
резку ab, то Pac + Pcb = Pab.

   Вопрос. Рассмотрим определение 4 без ограничения  "Пусть a <=
b". Верно ли при этом, что  для любой точки c из отрезка ab:
Pac + Pcb = Pab?

   Определение 6. Окружностью на ленте называется любой отрезок,
у которого длина  выражается четным числом. Длина отрезка в этом
случае называется диаметром окружности, а половина длины - ради-
усом. Центром окружности ab называется точка c такая,  что Pac =
Pcb.

   Упражнение. Докажите, что любая окружность имеет центр.
   Вопрос 1. Может ли окружность иметь несколько центров?
   Вопрос 2. Могут ли несколько окружностей иметь один центр?


   Определение 7. Две окружности пересекаются, если отрезки, их
изображающие, имеют общие точки.

   Вопрос. Могут  ли  не  пересекаться окружности, имеющие общий
центр?

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

   Задача 7. (3 балла)
   Окно установлено  в  центр окружности. Закрасить пробелом все
точки окружности  (кроме центра), если радиус окружности помещен
в клетку-центр в виде  символа  из алфавита Корректора. При этом
числовое значение радиуса равно порядковому номеру символа в ал-
фавите  исполнителя.

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

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

   Задача 8. (8 баллов)
   На ленте Корректора заданы две окружности с центрами в разных
точках a  и b.  Известно, что a < b  и радиусы обеих окружностей
меньше 50.
   В клетках, изображающих центры окружностей, записаны символы,
задающие радиусы окружностей (как в условии задачи 7).
   Написать программу,  которая  закрасит  пробелами все клетки
пересечения окружностей (кроме точек a и b, даже если они попа-
дают в пересечение).
  В начальный момент окошко установлено в точке a.

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

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

 Задача 9. (6 баллов) Последовательность Фибоначчи.
   Последовательность чисел:

        1, 1, 2, 3, 5, 8, 13, ...

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

              Фрагмент ленты с результатом

        ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
        │░│░│░│1│1│░│2│░│░│3│░│░│░│░│5│░│░│░│░│░│
        ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴


 Задача a. (8 баллов)
   В условиях предыдущей задачи построить  на  ленте  n  первых
членов последовательности Фибоначчи (n > 2).
   В начальный момент окно  смотрит  на клетку, символ в которой
задает своим порядковым номером в алфавите Корректора число n.


 Задача b. (3 балла)  Разметка отрезка.
   Отрезок ab (a < b) имеет длину кратную 3.
   Поделить его на три  равных  части и в клетках-точках деления
поставить символ "#". Начальная и конечная точки отрезка обозна-
чены на ленте не пустыми (заранее не известными) символами.
   В начальный момент окошко установлено на левый конец отрезка.

              Фрагмент ленты с результатом

             ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬
             │░│░│.│░│░│#│░│░│#│░│░│,│░│░│
             ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴


Задача c. (5 баллов)
   Окошко смотрит на ячейку, в которой записан символ, порядковый
номер которого (в алфавите Корректора) задает длину отрезка ab.
Известно, что Pab > 0.
   Построить отрезок на ленте, используя символ  "." для обозна-
чения его  концов и поделить его  пополам, если это  возможно. В
качестве обозначения средней точки использовать символ "#".

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

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

   Задача  d  (10 баллов) Придумать свою собственную задачу  для
Корректора, написать ее условие  и  решение. Балл за это задание
определяется оригинальностью условия и качеством решения.
