ВАРИАНТ 20

Часть 1

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

1. Во сколько раз 101110000₂ больше чем 10111₂? В ответе запишите только число в десятичной системе счисления.

Ответ: ___________________________ .

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

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

Ответ: ___________________________ .

3. На рисунке справа схема дорого Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги и пункта Б в пункт Д. В ответе запишите целое число — так, как оно указано в таблице.

Ответ: ___________________________ .

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

Таблица 1				Таблица 2
ID	Фамилия И.О.	Пол		ID_Родителя	ID_Ребёнка
1453	Дени К.Д.	Ж		5363	4218
2185	Ирта О.Б.	Ж		2185	4218
2605	Гано И.Е.	Ж		7148	5363
3474	Ивенко Д.Я.	М		1453	5363
4218	Бабенко А.Е.	М		3474	1453
5363	Марченко Е.Е.	М		7814	1453
5771	Арне А. А.	М		7148	2605
7148	Камо Е.А.	М		1453	2605
7814	Исава Г. А.	Ж		2605	8208
8208	Сорт А.К.	Ж		5771	7814
	...			...	...

Ответ: ______________­_________________ .

5. По каналу связи передаются сообщения, каждое из которых содержит: 16 букв А, 32 буквы Б, 64 буквы В и 16 букв Г (других букв в сообщениях нет).

Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:

а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);

б) общая длина закодированного сообщения должна быть как можно меньше.

Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?

В ответе перечислите через запятую кодовые слова для букв А, Б, В, Г в указанном порядке.

Ответ: ______________­_________________ .

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

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

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

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

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

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

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

Ответ: ______________­_________________ .

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

	А	В	С	D
1	3		7
2	=(B1-D2)/5	=С1-А1	=А1-2	=С2*3

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

Ответ: ______________­_________________ .

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

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

Ответ: ______________­_________________ .

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

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

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

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

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

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

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

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

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

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

Ответ: ______________­_________________ .

10. Вася составляет 6-буквенные слова, в которых есть только буквы И, В, А, Н, причём буква А используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Ответ: ______________­_________________ .

11. Дан рекурсивный алгоритм F. Приведите последовательность чисел (без пробелов), напечатанных на экране при выполнении вызова F(1, 2)?

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

Ответ: ______________­_________________ .

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

Ответ: ______________­__________________ .

13. Кабельная сеть проводит голосование среди зрителей о том, какой из 7-ми фильмов они хотели бы посмотреть вечером. Автоматизированная система голосования использует для кодирования номера каждого фильма минимально возможное и одинаковое количество бит. Кабельной сетью пользуются 5000 человек. В голосовании участвовало 2000 человек. Каков объём информации (в байтах), записанный автоматизированной системой голосования?

Ответ: ______________­__________________ .

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

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

Цикл

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

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

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

Ответ: ______________­__________________ .

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

Ответ: ______________­__________________ .

16. Сколько единиц содержится в двоичной записи значения выражения: 4⁴⁰ - 8¹⁵ + 2⁵⁴ + 7?

Ответ: ______________­__________________ .

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

Запрос	Количество найденных страниц (в тысячах)
Лампа | Книга | Блокнот	63
Книга	32
Лампа	40
Лампа & Блокнот	15
Лампа & Книга	21
Книга & Блокнот	0

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

Ответ: ______________­__________________ .

18. Обозначим через т & п поразрядную конъюнкцию неотрицательных целых чисел тип.

Так, например, 14 & 5 = 1110₂ & 0101₂ = 0100₂ = 4.

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

Ответ: ______________­_________________ .

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

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

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

Ответ: ______________­_________________ .

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

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

Ответ: ______________­_________________ .

21. Ниже на четырёх языках представлен алгоритм. Напишите в ответе число различных значений входной переменной k, при которых алгоритм выдаёт тот же ответ, что и при входном значении k = 60. Значение k = 60 также включается в подсчёт различных значений k.

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

Ответ: ______________­_________________ .

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

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

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

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

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

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

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

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

Ответ: ______________­_________________ .

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

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

Ответ: ______________­__________________ .

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

Часть 2

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

24. Требовалось написать программу, которая вводит с клавиатуры последовательность из n целых чисел (n = 4), и выводит на экран порядковый номер первого отрицательного числа этой последовательности. Если в последовательности нет отрицательных чисел, программа должна вывести на экран “NO”. Известно, что вводимые числа не превышают по модулю 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. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. Назовём позицией игры указание количества камней в обеих кучах. Например, позиция (15,20) означает, что в первой куче 15 камней, а во второй — 20. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной из куч в два раза. Например, имея количество камней в кучах (15,20), за один ход можно получить положение (16,20), (30,20), (15,21) и (15,30). У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

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

Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (6,24), (7,25), (9,24) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.

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

1. Для исходных позиций (6,25) и (8,24) укажите, кто из игроков выигрывает. Сколько ходов необходимо для выигрыша? Опишите выигрышную стратегию. Обоснуйте ответ.

2. Для исходных позиций (6,24), (8,23) и (7,24) укажите, кто из игроков выигрывает. Сколько ходов необходимо для выигрыша? Опишите выигрышную стратегию. Обоснуйте ответ.

3. Для исходной позиции (7,23) укажите, кто из игроков выигрывает. Сколько ходов необходимо для выигрыша? Опишите выигрышную стратегию. Приведите дерево игры. Обоснуйте ответ. На рёбрах дерева указывайте, кто делает ход, в узлах — позицию игры.

27. На вход программы подаётся последовательность символов, заканчивающихся символом “#”.

Других символов “#” во входной последовательности нет.

Будем называть словом любую последовательность подряд идущих символов, отделённую пробелами. Также слово может начинаться с начала строки.

Известно, что во входной последовательности не более 10⁹ символов, при этом слова имеют длину не более 100 символов.

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

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

Day, mice. "Year" - a mistake#

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