Городская олимпиада по информатике 1989 г. (теоретический тур)

Задача 1. (10 баллов)

Множество К строится следующим образом:

Два натуральных числа а, в включены в множество К.
Для любых х, у, входящих в К, число х+у+х*у включается в К.
Других элементов в К нет.

Составить алгоритм, определяющий, является ли z элементом множества К, если заданы числа а, в.

Ответ

Задача 2. (10 баллов)

В русском тексте на 1000 букв в среднем приходится:

а - 62 б - 14 в - 38 г - 13 д - 25 е, е - 72 ж - 7
з - 16 и - 62 й - 10 к - 28 л - 35 м - 26 н - 53
о - 90 п - 23 р - 40 с - 45 т - 53 у - 21 ф - 2
х - 9 ц - 4 ч - 12 ш - 6 щ - 3 ъ, ь - 14 ы - 16
э - 3 ю - 6 я - 18 - 175

Придумать кодирование букв последовательностями из 0 и 1 (необязательно одинаковой длины) так, чтобы:

- сообщение однозначно раскодировалось;
- имело минимальную длину.

Ответ

Задача 3. (8 баллов)

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

Ответ

Задача 4. (8 баллов)

Цифры двух положительных двоичных чисел хранятся в двух линейных таблицах. Получить третью таблицу, хранящую их произведение.

В двоичной системе счисления используются цифры 0 и 1, действия в двоичной системе определяются следующим образом:

0+0=0 0*0=0
0+1=1 0*1=0
1+0=1 1*0=0
1+1=10 1*1=1

Ответ

Задача 5. (5 баллов)

На клетчатой бумаге нарисовали окружность целого радиуса R с центром на пересечении линий. Найти К - количество клеток, целиком лежащих внутри этой окружности.

Ответ

Задача 6. (5 баллов)

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

шаг на север + 1 (в счетчик бортового вычислителя)
шаг на юг - 1 (в счетчик бортового вычислителя)
шаг на запад сброс счетчика
шаг на восток показать значение счетчика

Робот умеет вычислять логические функции:

на севере свободно на севере закрашено
на юге свободно на юге закрашено
на западе свободно на западе закрашено
на востоке свободно на востоке закрашено

Можно также конструировать сложные логические функции с помощью операций И, ИЛИ, НЕ. При составлении алгоритма для робота можно использовать команды:

ЕСЛИ условие ПОКА условие
ТО серия команд 1 НЦ
[ИНАЧЕ серия команд 2] серия повторяющихся команд
ВСЕ КЦ

Ответ

Задача 7. (3 балла)

Новобранцы выстроились в ряд и старшина скомандовал: "НАПРАВО", после чего каждый повернулся в произвольном направлении на 90, но увидев лицо соседа, тут же повернулся на 180. Перестанут ли они когда-нибудь вертеться? Результат обосновать.

Ответ

Задача 8. (2 балла)

Сформулировать, что делает данный фрагмент программы:

А:=А+В
В:=В-А
А:=А+В
В:=-В

Ответ

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