ВАРИАНТ 13

Часть 1

Ответами к заданиям 1—23 являются число, последовательность букв или цифр, которые следует записать в БЛАНК ОТВЕТОВ № 1 справа от номера соответствующего задания, начиная с первой клеточки, без пробелов, запятых и других дополнительных символов. Каждый символ пишите в отдельной клеточке в соответствии с приведёнными в бланке образцами.

1. Число X в шестнадцатеричной системе счисления оканчивается на 9₁₆, а в восьмеричной системе счисления — трёхзначное и начинается на 23₈. Укажите это число в десятичной системе счисления.

Ответ: ______________­__________________ .

2. Логическая функция F задаётся выражением Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных х, у, z.

Перем. 1	Перем. 2	Перем. 3	Функция
???	???	???	F
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

В ответе напишите буквы х, у, z в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая 1-му столбцу; затем — буква, соответствующая 2-му столбцу; затем — буква, соответствующая 3-му столбцу). Букве в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример

Пусть задано выражение х → у, зависящее от двух переменных х и у, и таблица истинности:

Перем. 1	Перем. 2	Функция
???	???	F
0	0	1
0	0	0
0	1	1
0	1	1

Тогда 1-му столбцу соответствует переменная у, а 2-му столбцу соответствует переменная х. В ответе нужно написать: ух.

Ответ: ______________­__________________ .

3. Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам).

Ответ: ______________­_________________ .

4. Для групповых операций с файлами используются маски имён файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также могут встречаться следующие символы:

Символ “?” (вопросительный знак) означает ровно один произвольный символ.

Символ “*” (звёздочка) означает любую последовательность символов произвольной длины, в том числе “*” может задавать и пустую последовательность.

Определите, какие из указанных имён файлов удовлетворяют маске:

В ответе перечислите номера файлов в порядке возрастания без пробелов и знаков препинания.

Ответ: ______________­_________________ .

5. Для кодирования некоторой последовательности, состоящей из букв А, В, С, D и Е, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код:

А-011, В-000, С-10, D-010, Е-001. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны.

Запишите ответ в виде: буква, кодовое слово. Например, если бы ответ был “Для буквы F новый код будет 110”, ответ нужно записать как: F110. Если невозможно ничего сократить, запишите в ответе просто цифру 0.

Ответ: ______________­_________________ .

6. Автомат получает на вход два однозначных шестнадцатеричных числа. Каждое из этих чисел не превосходит 5 (если число больше 5, автомат отказывается работать). По этим двум числам вычисляется новое шестнадцатеричное число как произведение полученных чисел.

Ученик проанализировал алгоритм и выписал все шестнадцатеричные числа, которые могут быть получены в результате работы алгоритма:

1,2,3,4,5,6,8,9,А,С,E,F,10,12,14,18,19.

Определите, сколько чисел он выписал лишних.

Ответ: ______________­_________________ .

7. Дан фрагмент электронной таблицы.

	А	В	С	D
1		3	5	4
2		=D1+B1	1	2
3		=С$2+$С3	6	7

Чему станет равным значение ячейки А2, если в нее скопировать формулу из ячейки В3?

Примечание: знак $ обозначает абсолютную адресацию.

Ответ: ______________­__________________ .

8. Определите, что будет напечатано в результате выполнения следующего фрагмента программы:

Бейсик	Паскаль
Си	Алгоритмический язык

Ответ: ______________­__________________ .

9. Музыкальный фрагмент был записан в формате 7.1 (восьмиканальная запись), оцифрован и сохранён в виде файла без использования сжатия данных. Размер полученного файла — 48 Мбайт. Затем тот же музыкальный фрагмент был оцифрован повторно в формате стерео (двухканальная запись) и оцифрован с разрешением в 1,5 раза меньше и частотой дискретизации в 2 раза больше, чем в первый раз. Сжатие данных не производилось. Укажите размер файла в Мбайт, полученного при повторной записи. В ответе запишите только целое число, единицу измерения писать не нужно.

Ответ: ______________­__________________ .

10. Для записи результатов соревнований используется таблица, в которой для каждой из 20-ти команд по каждому из 10-ти видов состязаний записано 1,2 или 3 (если команда заняла соответствующее место в этом состязании) или прочерк (если не заняла призовое место или не участвовала). Какое количество информации (бит) содержит таблица?

Ответ: ______________­__________________ .

11. Определите, сколько звёздочек будет напечатано в результате вызова F(7) приведённой подпрограммы:

Бейсик	Паскаль
Си	Алгоритмический язык

Ответ: ______________­__________________ .

12. В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IР-адрес, — в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого разряда — нули.

Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.

Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.

Для узла с IP-адресом 83.242.102.102 адрес сети равен 83.242.96.0. Чему равно наименьшее возможное значение третьего слева байта маски? Ответ запишите в виде десятичного числа.

Ответ: ______________­_________________ .

13. В некоторой стране автомобильный номер состоит из 7 символов: сначала 2 буквы, затем 3 цифры, затем ещё 2 буквы. При этом буквы могут быть выбраны только из 12 строчных букв местного алфавита. Среди цифр не используются цифры 6 и 9. Автоматизированная система хранит номера автомобилей следующим образом. Используется посимвольное кодирование и в памяти системы для кодирования каждого символа используется минимально возможное и одинаково целое количество бит. А для хранения всего пароля используется минимально возможное целое количество байт. Какое количество информации (в байтах) требуется для хранения номеров 160 автомобилей?

Ответ: ______________­_________________ .

14. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды

заменить (222, 34)

преобразует строку 77222277 в строку 7734277.

Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б) нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение “истина”, в противном случае возвращает значение “ложь”. Строка исполнителя при этом не изменяется.

Цикл

выполняется, пока условие истинно.

В конструкции

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 69 идущих подряд цифр 7? В ответе запишите полученную строку.

Ответ: ______________­__________________ .

15. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, 3, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Ответ: ______________­__________________ .

16. Запись числа 46₁₀ в системе счисления с основанием N оканчивается на 1 и содержит 3 цифры. Чему равно основание этой системы счисления N?

Ответ: ______________­__________________ .

17. В языке запросов к поисковому серверу для обозначения логической операции “ИЛИ” используется символ |, а для логической операции “И” — &. В таблице приведено количество страниц, которое находит поисковая система по каждому запросу.

Запрос	Количество найденных страниц (в тысячах)
Стекло	26
Бетон	25
Кирпич	31
Стекло & Бетон	10
Стекло & Кирпич	16
Бетон & Кирпич	12
Стекло & Бетон & Кирпич	3

Какое количество страниц (в тысячах) будет найдено этой поисковой системой по запросу: Стекло | Бетон | Кирпич?

Ответ: ______________­__________________ .

18. На числовой прямой даны отрезки Р = [5, 13] и Q = [8, 19]. Укажите наименьшую возможную длину такого отрезка А, что формула верна при любых значениях х.

Ответ: ______________­_________________ .

19. В программе используется целочисленный массив А с индексами от 0 до 9. Значения элементов массива равны 6; 5; 4; 7; 10; 6; 9; 11; 7; 8 соответственно, т.е. А[0] = 4; А[1] = 5 и т.д.

Определите значение переменной k после выполнения следующего фрагмента программы, записанной ниже на разных языках программирования.

Бейсик	Паскаль
Си	Алгоритмический язык

Ответ: ______________­_________________ .

20. Ниже на четырёх языках записан алгоритм. Получив на вход число х, этот алгоритм печатает число М. Укажите наибольшее число х, при вводе которого алгоритм печатает 7.

Бейсик	Паскаль
Си	Алгоритмический язык

Ответ: ______________­_________________ .

21. Ниже на четырёх языках представлен алгоритм. Определите, при скольких значениях b на экран будет выведено такое же число, как и при b = 100 (включая b = 100).

Бейсик	Паскаль
Си	Алгоритмический язык

Ответ: ______________­_________________ .

22. Исполнитель Июнь15 преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2.

Программа для исполнителя Июнь15 — это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 45 и при этом траектория вычислений содержит число 18?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Ответ: ______________­_________________ .

23. Сколько существует различных наборов значений логических переменных x₁, х₂, ... х₁₁, х₁₂, которые удовлетворяют всем перечисленным ниже условиям?

В ответе не нужно перечислять все различные наборы значений x₁, х₂, ... х₁₁, х₁₂, при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

Ответ: ______________­_________________ .

Не забудьте перенести все ответы в бланк ответов № 1 в соответствии с инструкцией по выполнению работы.

Часть 2

Для записи ответов на задания этой части (24—27) используйте БЛАНК ОТВЕТОВ № 2. Запишите сначала номер задания (24, 25 и т. д.), а затем полное решение. Ответы записывайте чётко и разборчиво.

24. Требовалось написать программу, которая вводит с клавиатуры последовательность натуральных чисел, оканчивающихся нулем, и выводит на экран сумму чётных чисел среди этой последовательности. Известно, что в последовательность не пуста и в ней есть чётные числа. Программист торопился и написал программу неправильно.

Паскаль	Бейсик
Си	Алгоритмический язык

Выполните следующие действия:

1. Напишите, что выведет программа при вводе чисел 50 2 14 0.

2. Приведите пример такой входной последовательности, при которой программа работает верно.

3. Укажите все ошибки в программе и исправьте их. Для этого для каждой ошибки: выпишите строку, которая написана неправильно и приведите правильный вариант строки.

25. Дан целочисленный массив из 40 элементов. Элементы массива могут принимать значения от -10000 до 10000. Опишите на русском языке или на одном из языков программирования алгоритм, который находит и выводит пару с наименьшей суммой среди непересекающихся пар соседних элементов. То есть, первая пара — 1-й и 2-й элементы, вторая пара — 3-й и 4-й элементы, и т.д. На языке Си, соответственно, первая пара — 0-й и 1-й элементы, 2-я пара — 2-й и 3-й элементы, и т.д.

Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них.

Паскаль	Бейсик
СИ	Алгоритмический язык
Русский (естественный) язык
Объявляем массив А из 40 элементов. Объявляем целочисленные переменные I, J, MIN. В цикле от 1 до 40 вводим элементы массива А с 1-го по 40-й. ...

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

26. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два или три камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 17, 18 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 40. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 40 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 39.

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

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

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

б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.

2. Укажите два значения S, при которых у Пети есть выигрышная стратегия, причём (а) Петя не может выиграть за один ход и (б) Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите выигрышную стратегию Пети.

3. Укажите такое значение S, при котором:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах — количество камней в куче.

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

В каждой из последующих N строк: информация о тоннаже и количестве железнодорожных вагонов, обработанных сортировочной станцией в течение нескольких лет (не раньше 1980 года).

В формате:

mm.уууу tttt kkk

mm — номер месяца, уууу — год, tttt — тоннаж, kkk — количество обработанных вагонов (число положительное, если вагоны прибывающие, отрицательное — если убывающие).

Пример: 11.2001 45322 -8657

Необходимо вывести на экран номера лет, в которые наибольший тоннаж одного прибывшего вагона превышает наименьший тоннаж одного убывшего.