Муниципальное общеобразовательное учреждение

средняя общеобразовательная школа №4 

(территориальный ресурсный центр)

 Тверская область, г. Нелидово, ул. Карбышева 14А

((848266) 3-14-42

e-mail: nel_shkola_4@mail.ru

Международная олимпиада по информатике 1991 года

Русский язык

г. Анависсос, Греция,

19—24 мая 1991 г.

ЗАДАЧА ПЕРВОГО ТУРА

"МАТРИЦА 5*5"

Пронумеровать позиции в матрице (таблице) размером 5*5 следующим образом. Если номер i (l<i<25) соответствует позиции с координатами (х, у), то номер i+1 может соответствовать позиции с координатами (z, w), вычисляемыми по одному из следующих правил:

1)  (_Z,w)=(x±3,y);

2) (z,w)=(x,y±3);

3) (z,w)=(x±2,y±2).

Требуется:

а)  написать программу, которая последователь­но нумерует позиции матрицы 5*5 при заданных ко­ординатах позиции, в которой проставлен номер 1 (результаты должны быть представлены в виде за­полненной матрицы);

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

Пример. Если в качестве начальной позиции в матрице выбрана позиция с координатами (2, 2), то на данном шаге координаты позиции с номером 2 в соответствии с представленными правилами могут быть: (2, 5), (5, 2) или (4, 4) (на рис. они помечены звездочкой).

Примечание. Будет оцениваться, похож ли вывод вашей программы на наш пример.

Разбалловка:

 Пункт а) 50 баллов

Пункт б) 25 баллов

Вывод        15 баллов

Жюри        10 баллов (стиль программирования, элегантность)

ЗАДАЧА ВТОРОГО ТУРА

 "S-ТЕРМЫ"

S-терм — это последовательность символов S и скобок, определяемая рекурсивно следующим образом:

1) символ S есть S-терм;

2)  если М и N — S-термы, то выражение (MN) есть также S-терм.

Пример S-терма: ((((SS)(SS))S)(SS)).

Правые скобки не несут информации и могут опускаться. В этом случае вышеприведенный S-терм выглядит так:

((((SS(SSS(SS.

1. Напишите процедуру "gensterm" для порожде­ния S-термов. Она должна для заданного n запол­нять n текстовых файлов (n = длина = число симво­лов 'S'), каждый из которых содержит все S-термы длины 1, 2,..., n соответственно. Внутри файла S-термы разделяются символом ';'. В конце каждого файла должен стоять символ '. '(точка).

Напишите программу, которая по заданному целому n (n<=10) выполняет описанную выше процедуру и выдает на дисплей все сгенерированные S-термы.

Рассмотрим исчисление S-термов. Единственное алгебраическое правило (S-правило). которое может быть использовано, состоит в следующем: любой подтерм S-терма, имеющий вид (((SA)B)C), где А, В и С — также S-термы, может быть переписан как ((АС)(ВС)), т. е.

Contextl(((SA)B)C)Context2->Contextl((AC)(BC))Context2

Применение этого правила к S-терму называет­ся редукцией S-терма. Возможны разные способы (стратегии) выбора подтермов для применения S-правила. Последовательное применение S-правила к S-терму до тех пор, пока это возможно, называется нормализацией.

Пример цепочки редукции S-терма:

((((SS)(SS))S)(SS)) ((S(SS))(((SS)S)(SS)))^((S(SS))((S(SS))(S(SS)))).

2.  Предложите эффективную структуру данных для представления S-термов, облегчающую примене­ние S-правила. Написать две процедуры: "readterm" и "printterm".  Первая из них преобразует  S-термы  в вашу  структуру  данных   из   формы,   порождаемой процедурой  "gensterm"; вторая преобразует S-термы из вашей структуры в форму, порождаемую процедурой  "gensterm". Ваша программа должна демонстрировать эти преобразования.

3.   Напишите процедуру  "reduce",  выполняющую один шаг редукции в соответствии с S-правилом над заданным подтермом S-терма в вашем представлении. Программа должна продемонстрировать это.

4.   Напишите процедуру   "normalize",  которая в заданном S-терме должна последовательно выбирать подтермы и применять S-правило до тех пор, пока дальнейшие редукции  станут   невозможными,  либо число шагов достигнет некоторого максимума, например 30. Программа должна продемонстрировать это.

5.   Объедините все процедуры в одну программу, которая:

а) запрашивает у пользователя длину n;

б)   порождает с помощью процедуры   "gensterm" все S-термы заданной длины;

в) преобразует эти S-термы в ваше представление;

г) нормализует их (если это возможно);

д)  выводит в качестве результата нормализованные S-термы;

е)  выводит последовательно число шагов редук­ции, совершенных над каждым S-термом, либо сооб­щение  "not normalized",  если нормализация требует более 30 шагов;

ж)  выводит число ненормализованных термов и общее число всех S-термов заданной длины n.

Разбалловка:

Пункт 1       20 баллов

Пункт 2       25 баллов

Пункт 3       15 баллов

Пункт 4       20 баллов

Пункт 5       10 баллов

Жюри          10 баллов (стиль программирования, элегантность)

Место проведения

Участники

Скачать задания в Word

Начало