Центр профориентации абитуриентов и адаптации студентов

ПРОГРАММА ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ март – апрель 2010 г.

Программа

à  Информация и ее кодирование.

à  Алгоритмизация и основы программирования

à  Основы логики; логические функции

à  Системы счисления

à  Начала теории множеств

à  Комбинаторика простых чисел

à  Основы моделирования

Типовой вариант

1. Определить число байт, необходимое для кодирования числа 244

2. Определить значение переменной Sk по завершению работы алгоритма

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

4. Перевести число (21202)12 в десятичную систему счисления.

5. Сложить числа (167)8 и (66)8. Результат привести в десятеричной и восьмеричной системе счисления.

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

7. На рисунке приведена блок-схема алгоритма, который должен складывать числа от 4 до 12. Алгоритм содержит ошибку. Найти ошибку и сделать одно исправление в блок-схеме так, чтобы алгоритм верно работал.

8. Упростить данную форму:

9. Даны два множества A и B.

A={(x, y), x и y являются вещественными числами | x2+y2<=4};

B={(x, y), x и y являются вещественными числами | y>ex}.

Изобразить в декартовых координатах множества A, B, , , A|B, AB, .

НЕ нашли? Не то? Что вы ищете?

10. Найти двухзначное число в семеричной системе счисления, которое равно сумме своих десятков и квадрата единиц, если известно, что разница между количеством десятков и количеством единиц не равна двум.

11. Представить целое число 7 с помощью числа . Допускается использовать только число , знаки сложения, вычитания, умножения, деления, извлечения квадратного корня, а также символ функции «антье от X» (операция взятия «антье от X», обозначаемая квадратными скобками, определяет собой нахождение наибольшего целого числа, не превосходящего X). Также можно пользоваться круглыми скобками, как в алгебре, никакие другие символы не разрешаются.

12. Один фермер потратил 100 долларов на покупку 100 различных домашних животных. Каждая корова обошлась ему
в 10 долларов, свинья – в 3 доллара, а овца – по 50 центов за голову. Предполагая, что фермер приобрел по крайней мере одну корову и одну овцу, подсчитать, сколько голов скота каждого вида он купил? (найти одно решение задачи, если таковое существует)

Система определения рейтинга

Максимально возможный рейтинг – 100 баллов. Каждый вариант работы содержит 12 заданий разного уровня сложности. Задания оцениваются определенным количеством баллов в зависимости от степени сложности. Баллы, начисляемые за каждую правильно решенную задачу, зависят от сложности задачи и указаны в билете рядом с номером задачи. Правильно решенной считается задача, в которой дано обоснование получения ответа и выполнены все задания, указанные в условии задачи.

Ниже указаны баллы, ответы и краткое пояснение решений к заданиям типового варианта

№ задачи

Баллы

Ответы и решения

1

4

Ответ: 6 байт. Решение: Число 244 можно разместить в 44 двоичных разрядах. Округляя до ближайшего большего числа кратного 8, получаем 48 бит или 6 байт.

2

4

Ответ 17: X будет уменьшен, а Sk увеличен дважды (10-2=8, Sk=16, 8-2=6, Sk=17)

3

5

Ответ: А меньше чем (В + 20). Во избежание зацикливания алгоритм не должен пойти по правой ветви алгоритма после условия A<B, так как переменная A не меняется, переменная B увеличивается, а переменная I на правой ветви уменьшается на единицу. Таким образом, условие I=10 никогда не будет выполнено. Следовательно, 10 раз переменная A должна оказываться меньше, чем переменная B. В процессе прохождения алгоритма A увеличивается на 2, следовательно, исходно A должно быть меньше, чем B+20.

4

5

Ответ: 43490. Решение: Число можно перевести в 10-ю систему счисления так 2×124 + 1×123 + 2×122 + 0×121 + 2×120 = 2×20736 + 1×1728 + 2×144 + 0×121 + 2×1 = 41472 + 1728 + 288 + 0 + 2 = 43490.

5

6

Ответ: (173)10 и (255)8.

Решение.

167

+ 66

255

После сложения самого правого разряда и второго справа возникает перенос в 1. Полученное в восьмеричной системе число (255)8 переводим в десятеричную систему 2×82 + 5×81 + 5×80 = 2×64 + 5×8 + 5×1 = 128 + 40 + 5 = 173.

6

6

Ответ: Исходно переменная C<12, при прохождении по алгоритму значение переменной не меняется, следовательно, алгоритм зацикливается. Надо увеличивать переменную C при прохождении правой ветви алгоритма после условия C<12.

7

7

Ошибка заключается в том, что первое прибавляемое к сумме слагаемое равно не 4, а 5. Сначала надо увеличить сумму, и только потом слагаемое I.

8

10

Ответ можно искать с помощью таблицы истинности.

X

y

z

[…] […]

1

1

1

0

0

1

1

1

1

1

1

1

0

0

0

1

1

1

1

1

1

0

1

1

0

0

0

0

1

0

1

0

0

1

0

0

0

0

1

0

0

1

1

1

1

1

1

1

1

1

0

1

0

1

1

1

1

1

1

1

0

0

1

0

1

1

1

1

0

0

0

0

0

0

1

1

1

1

0

0

Ответ: y

9

12

Решение: На рисунке приведены множество А и множество В. Соответственно определяются и изображаются объединение множеств А и В, пересечение множеств А и В, разность множеств А и В, симметрическая разность (объединение множеств А и В, исключающее пересечение множеств А и В), множество «не А».

10

12

Ответ. Число равно (56)7.

Решение. Обозначим число десятков в искомом числе а, число единиц – b. Тогда имеем: а∙7 + b = a + b2. Отсюда получаем такое соотношение: а∙7 - a = b2 - b, которое после преобразования выглядит так: 6∙a = b(b - 1).

Число аb двузначное, значит, а может принимать значения от 1 до 6. а и b целые числа, значит b может принимать значения от 3 до 6. Рассмотрим варианты: b = 3 (получается ответ 13), b = 4 (получается ответ 24), b = 5 (не получается решение в целых числах) и b = 6 (получается ответ 56). Разница между количеством десятков и количеством единиц не должна быть равна двум, следовательно, 13 и 24 не подходят. Ответ 56. Проверим результат в десятичной системе счисления. а+ b2 = 5 + 36 = 5∙7 + 6 = 41.

11

14

Ответ: .

12

15

Решение: Формализуем задачу:

10x+3y+z/2=100

x+y+z=100

исключая z, получаем 19x+5y=100

5y=100-19x

y=(100-19x)/5

y=20-3x-4x/5

y целое число, значит 4x/5 должно быть числом, кратным 5, то есть x должно быть кратным 5. Наименьшее такое число и есть 5, тогда y=1, z=94.

Ответ: Фермер купил 5 коров, 1 свинью, 94 овцы

Информация о порядке проведения работы

Работа проводится в порядке, соответствующем положению о проведении мероприятий Олимпиады в МИСиС. Время, отводимое абитуриенту на выполнение заданий, – 3 часа (180 минут).

Абитуриент должен прибыть в университет не позднее указанного в приглашении времени. При себе абитуриент обязан иметь паспорт, пропуск, приглашение и пару авторучек синего или черного цвета.

Основное требование к абитуриенту – самостоятельное выполнение работы: использование справочной, учебной литературы или шпаргалок, а также какой-либо обмен мнениями между участниками работы являются грубым нарушением, за которое абитуриент может быть сразу удален из аудитории.

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

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

При проведении работы в аудиториях не допускается использование устройств мобильной связи (пейджеры, телефоны и т. д.).