ВАРИАНТ 19

Часть 1

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

1. Во сколько раз 34₈ меньше чем 3400₈? В ответе запишите только число в десятичной системе счисления.

Ответ: __________________________ .

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

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

Ответ: __________________________ .

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

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

Ответ: __________________________ .

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

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

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

Имеется список из нескольких масок:

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

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

Ответ: ______________­_________________ .

5. По каналу связи передаются сообщения, каждое из которых содержит:

8 букв А, 8 букв Б, 16 букв В и 32 буквы Г (других букв в сообщениях нет).

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

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

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

Какова суммарная длина всех четырёх кодовых слов?

Ответ: ______________­_________________ .

6. В некоторой информационной системе информация кодируется двоичными числами, имеющими ровно 4 значащих разряда. При передаче данных возможны их искажения, поэтому в конец каждого числа дописывается ещё один (контрольный) разряд таким образом, чтобы сумма разрядов нового числа, считая контрольный, была чётной. Например, к слову 1011 справа будет добавлена 1, а к слову 1010 — 0.

После этого, для увеличения надежности кодирования, к полученному двоичному числу дописывается сумма его разрядов в двоичном виде. Например, исходное слово 0010 превратится в 0010110.

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

Ответ: ______________­_________________ .

7. В электронной таблице в ячейке С5 записана формула, которая вычисляет результат сложения значения ячейки Е4 со значением ячейки D3. Формулу из ячейки С5 скопировали в ячейку В6. Какое количество следующих утверждений не противоречит условию?

1) В ячейке В6 вычисляется результат сложения значения ячейки D5 со значением ячейки С4.

2) В ячейке В6 вычисляется результат сложения значения ячейки D5 со значением ячейки D3.

3) В ячейке В6 вычисляется результат удвоения значения ячейки D4.

4) В ячейке В6 вычисляется результат сложения значения ячейки Е4 со значением ячейки D3.

Ответ: ______________­_________________ .

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

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

Ответ: ______________­_________________ .

9. Музыкальный фрагмент был оцифрован и записан в виде файла без использования сжатия данных. Получившийся файл был передан в город А по каналу связи за 90 секунд. Затем тот же музыкальный фрагмент был оцифрован повторно с разрешением в 2 раза меньше и частотой дискретизации в 1,5 раза меньше, чем в первый раз. Сжатие данных не производилось. Полученный файл был передан в город Б; пропускная способность канала связи с городом Б в 3 раза ниже, чем канала связи с городом А. Сколько секунд длилась передача файла в город Б?

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

Ответ: ______________­__________________ .

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

Ответ: ______________­__________________ .

11. Даны рекурсивные алгоритмы F и G. Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(15)?

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

Ответ: ______________­_________________ .

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

255.255.255.192?

Ответ: ______________­_________________ .

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

Ответ: ______________­_________________ .

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

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

Цикл

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

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

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

Ответ: ______________­_________________ .

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

Ответ: ______________­_________________ .

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

Ответ: ______________­_________________ .

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

Запрос	Количество найденных страниц (в тысячах)
Авторучка | Карандаш | Линейка	45
Линейка	23
Карандаш	18
Авторучка	15
Карандаш & Линейка	0
Авторучка & Карандаш	8

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

Ответ: ______________­_________________ .

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

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

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

Ответ: ______________­_________________ .

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

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

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

Ответ: ______________­_________________ .

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

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

Ответ: ______________­_________________ .

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

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

Ответ: ______________­_________________ .

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

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

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

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

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

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

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

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

Ответ: ______________­__________________ .

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

(*i = х₂) V ((*₃ Л *₄) V (^*₃ Л ^*₄)) = ¹

(*з - *4> Л ((*5 Л *₆) V А ^6” ^{= 0}

(*₅ = ^Лб) V ((*₇ А ^хв) V Ьх₇ л -Х₈)) = 1

(х₇ = х₈) Л((Хд Лх₁₀) V(-Хд Л ^ю)) ^{= 0}

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

Ответ: ______________­__________________ .

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

Часть 2

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

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

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

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

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

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

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

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

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

Паскаль	Бейсик
Си	Алгоритмический язык
Русский (естественный) язык
Объявляем массив А из 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). У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

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

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

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

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

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

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

27. На вход программе подаётся: в первой строке — число N (1 < N < 10⁹).

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

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

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

8

3

4

5

-7

-8

3

2

9

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

-72