ВАРИАНТ 18

Часть 1

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

1. Сколько существует различных 2-значных чисел в восьмеричной системе счисления?

Ответ: ____________________________ .

2. Дан фрагмент таблицы истинности выражения F. Значения в пустых клетках таблицы неизвестны и могут быть любыми из возможных.

Перечислите в порядке возрастания без запятых и пробелов номера логических выражений, которые могут соответствовать F:

Ответ: ____________________________ .

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

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

Ответ: ____________________________ .

4. Дан фрагмент базы данных, содержащий информацию о родственных отношениях. Определите, сколько потомков Кименко З.Т. упомянуто в таблице.

Таблица 1				Таблица 2
ID	Фамилия И.О.	Пол		ID_Родителя	ID_Ребёнка
1518	Гираб В.А.	М		1885	3472
1885	Жуйко А.И.	М		6109	3472
2946	Калпен Л.В.	М		9657	1885
3472	Арно В.А.	Ж		4705	1885
4705	Иваненко И.Л.	М		2946	4705
5624	Ирита Е.О.	Ж		5624	4705
6109	Кирта У.Т.	Ж		8434	2946
7296	Олинг К.Л.	Ж		1518	2946
8434	Кименко З.Т.	Ж		2946	7296
9657	Вирк Я.М.	Ж		5624	7296
	...			...

Ответ: ____________________________ .

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

А-01101, В-11000, С-10110.

Любые два из этих трех кодовых слов отличаются не менее чем в трёх позициях. Поэтому, если принятое кодовое слово отличается от допустимого не более чем в одной позиции, можно однозначно определить, какая буква передавалась (говорят, что “код исправляет одну ошибку”). Так, получив кодовое слово 10000, можно догадаться, что передавалась буква В (отличие от кодового слова для В только в одной позиции, для остальных кодовых слов отличий больше). Если принятое кодовое слово отличается от всех допустимых кодовых слов более, чем в одной позиции, считается, что произошла ошибка (она обозначается “х”)

Получено сообщение 01001 00011 10101 11001. Декодируйте это сообщение. В ответе укажите четыре символа без пробелов и запятых.

Ответ: ______________­________________ .

6. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1) Строится двоичная запись числа N.

2) К этой записи дописываются справа ещё два разряда по следующему правилу:

а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

Укажите минимальное число R, которое превышает 49 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.

Ответ: ______________­________________ .

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

	А	В	С	D
1			8
2	=В1/2	=С1-А2	=D2-А2-В2	=В1*2

Какое число должно быть записано в ячейке В1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек A2:D2 соответствовала рисунку?

Ответ: ______________­________________ .

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

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

Ответ: ______________­_________________ .

9. Документ объёмом 320 Мбайт можно передать с одного компьютера на другой двумя способами:

А. Сжать архиватором, передать по каналу связи, распаковать.

Б. Передать по каналу связи без использования архиватора.

Какой способ быстрее и на сколько, если:

• средняя скорость передачи данных по каналу связи составляет 2²⁴ бит в секунду;

• объем сжатого архиватором документа равен 50% исходного;

• время, требуемое на сжатие документа, — 60 секунд, на распаковку — 30 секунд?

В ответе напишите букву А, если быстрее способ А, или Б, если быстрее способ Б. Сразу после буквы напишите число, обозначающее, на сколько секунд один способ быстрее другого.

Так, например, если способ Б быстрее способа А на 23 секунды, в ответе нужно написать Б23.

Единиц измерения “секунд”, “сек.”, “с.” к ответу добавлять не нужно.

Ответ: ______________­_________________ .

10. Сотрудник полиции собирает статистику нарушений ПДД на оживлённом перекрестке.

При этом в каждом случае он фиксирует, был ли нарушитель: пешеход или автомобилист, мужчина или женщина, на какой сигнал светофора он при этом пересекал перекресток (красный, жёлтый, зелёный или красно-жёлтый), шёл ли при этом дождь. За день сотрудник собрал информацию о 150 нарушителях. Какое количество информации (число бит) получил полицейский?

Ответ: ______________­_________________ .

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

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

Ответ: ______________­_________________ .

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

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

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

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

Ответ: ______________­__________________ .

13. При передаче сообщения используются только десятичные цифры, а также строчные и прописные буквы местного алфавита. В местном алфавите 30 букв. При этом используется посимвольное кодирование и каждый символ кодируется минимально возможным количеством бит. Каков объём информации (в байтах), записанный устройством после передачи 120 символов?

Ответ: ______________­__________________ .

14. Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (а, b), где а, b — целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, у) в точку с координатами (х + а; у + b).

Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, 3) переместит Чертёжника в точку (6, 1).

Цикл

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

Чертёжнику был дан для исполнения следующий алгоритм (буквами n, а, b обозначены неизвестные числа, при этом n > 1):

Укажите наименьшее возможное значение числа n, для которого найдутся такие значения чисел а и b, что после выполнения программы Чертёжник возвратится в исходную точку.

Ответ:__________________________ .

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

Ответ:__________________________ .

16. В системе счисления с основанием 4 записано четырёхзначное число. Известно, что все цифры числа разные. Какое самое маленькое число удовлетворяет этому условию? Ответ запишите в десятичной системе счисления.

Ответ: ______________­_________________ .

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

Запрос	Количество найденных страниц (в тысячах)
Стул	24
Табурет	23
Стул & Кресло	10
Стул & Табурет	11
Кресло & Табурет	8
Стул | Кресло | Табурет	47
Стул & Кресло & Табурет	3

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

Ответ: ______________­_________________ .

18. Обозначим через ДЕЛ(n, m) утверждение “натуральное число n делится без остатка на натуральное число m”.

Для какого наименьшего натурального числа А формула тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Ответ: ______________­_________________ .

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

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

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

Ответ: ______________­_________________ .

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

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

Ответ: ______________­_________________ .

21. Ниже на четырёх языках представлен алгоритм. Определите, при каком наибольшем значении b в результате выполнения следующего алгоритма будет напечатано такое же число, как и при b — 300:

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

Ответ: ______________­_________________ .

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

1. прибавь 1,

2. прибавь 2,

3. прибавь 4.

Первая из них увеличивает число на экране на 1, вторая — на 2, третья — на 4. Программа для Прибавлятеля — это последовательность команд.

Сколько есть программ, которые число 1 преобразуют в число 11?

Ответ: ______________­_________________ .

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

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

Ответ: ______________­__________________ .

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

Часть 2

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

24. Требовалось написать программу, которая вводит с клавиатуры последовательность из n целых чисел (n = 4), и выводит на экран максимальное число этой последовательности. Известно, что вводимые числа не превышают по модулю 1000. Программист торопился и написал программу неправильно.

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

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

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

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

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

25. Дан целочисленный массив из 40 элементов. Элементы массива могут принимать значения от -10000 до 10000. Опишите на русском языке или на одном из языков программирования алгоритм, который проверяет, упорядочен ли массив по возрастанию (каждый последующий элемент больше предыдущего). Если да, программа должна вывести “YES”, в противном случае— “NO”.

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

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

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

26. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

В начальный момент в первой куче было 4 камня, во второй куче — S камней;

1 ≤ S ≤ 25.

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

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

Задание 1

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

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

Задание 2

Укажите такое значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Для указанного значения S опишите выигрышную стратегию Пети.

Задание 3

Укажите значение S, при котором одновременно выполняются два условия:

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

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Вани.

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

В заданиях 2 и 3 указать одно значение S и объяснить, почему это значение удовлетворяет условию соответствующего задания.

27. Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору.

Итоговая оценка выставляется как максимальная из оценок за задания А и Б.

Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 0 баллов.

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

Напишите программу, которая должна вывести на экран минимальное чётное произведение двух элементов последовательности, номера которых различаются не меньше чем на 6.

Если такой пары элементов нет, программа должна вывести ноль.

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

Перед программой укажите версию языка программирования.

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

Максимальная оценка за выполнение задания А — 2 балла.

Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).

Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.

Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 Кбайта.

Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.

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

Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.

Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.

Напоминаем! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.

Входные данные представлены следующим образом. В первой строке задается число N — общее количество элементов последовательности (N < 10 000).

В каждой из следующих N строк задается одно положительное целое число — очередной элемент последовательности.

Известно, что каждое число положительное и не превышает 1000.

Пример входных данных:

8

1

4

5

7

8

3

2

9

Пример выходных данных:

2