Олимпиада по информатике (Болгария 1990 г.)

Олимпиада по информатике (Болгария 1990 г.)

Задача 1

Даны N, N>1 прямоугольников, для которых предполагается, что:

a) стороны любого прямоугольника параллельны координатным осям и прямоугольник задается концами одной из диагоналей.

b) Каждый прямоугольник имеет общие внутренние точки с хотя бы одним из остальных и не имеет общих вершин, сторон или частей сторон ни с одним из остальных прямоугольников.

Составить программу, которая решает следующие задачи:

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

2. Определить содержит ли фигура F "дырки", т. е. замкнутые фигуры, которые ей не принадлежат.

3. Разложить фигуру на наименьшее возможное число не пересекающихся прямоугольников, которые могут иметь общие стороны или части сторон, а их объединение дает фигуру F.

4. Вычислить периметр и площадь фигуры F.

Примечание.

1. Задачи 3, 4 решаются только для фигур, которые содержат "дырки".
2. Полное решение содержит:

- анализ (обоснование) решения
- текст программы с соответствующими комментариями
- выполнение текстового примера, который будет дан при приемке работы

Объединение прямоугольников Ai Bi Ci Di, i=1, 2, 3, 4 есть фигура F=A2 B2 X1 B1 X2 B4 C4 D4 X3 X4 C2 D2 фигура F содержит единственную "дырку" PQRS

Задача 2

На фигуре 1 показана вычислительная система, содержащая достаточное количество процессоров, использующих общую память из 26 числовых переменных A, B, C, ..., Z. Система работает шагами. На каждом шаге, каждый процессор выполняет либо оператор присваивания либо пустой оператор. Оператор присваивания - это конструкция вида (переменная)=(арифметическое выражение) где арифметическое выражение без скобок и содержит не более 2 переменных и арифметические операции. Процессоры вычисляют выражения и присваивают их значения переменным из левых частей операторов, а потом приступают к следующим операторам (притом одновременно). Не допускается одновременное выполнение 2 или больше операторов присваивания с одинаковой левой частью. Пустой оператор обозначаем символом &. Выполняя его, процессор простаивает 1 шаг.

(фигура 1)

n последовательности операторов (присваивания или пустых) с одинаковой длиной L называем n - программой с длиной L (выполняется за L шагов на первых n процессоров), если на каждом шаге имеем не более 1 оператора с заданной левой частью.n-программы P и Q называем эквивалентными, если начиная с одного и того же начального состояния переменных A, B, ..., Z после выполнения как P, так и Q получается одинаковый результат.

Напишите программу, которая:

Зад. 1. Вводит целое k (k<25) и 1-программу, содержащую k операторов присваивания,

Зад. 2. Проверяет правильность введенных операторов,

Зад. 3. Преобразует 1-программу в эквивалентную m-программу c минимальной длиной (добавляя если надо пустые операторы) и выводит полученный результат,

Зад. 4. Не увеличивая длину построенной в Зад. 3. n-программой, преобразует ее в эквивалентную m-программу, m - как можно меньше, и выводит полученный результат.

Замечание. На фигуре 2. показана 1-программа из 6 операторов, 3-программа и 2-программа - возможные решения задач 3(б) и 4(в).

а) D=A*D	б) A=B+C	B=C+D	D=D-E
A=B+C	A=A-E	&	&
A=A-E	E=A*B	D=A*D	&
B=C+D	в) A=B+C	B=C+D
D=D-E	A=A-E	D=D-E
E=A*B	E=A*B	D=A*D

(фиг. 2.)




	© ярославский ?ентр телекоммуникаций и информационных систем в образовании, 2003.