ВАРИАНТ 17

Часть 1

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

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

Ответ: ______________­__________________ .

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

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

Ответ: ______________­__________________ .

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

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

Ответ: ______________­__________________ .

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

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

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

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

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

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

Ответ: ______________­__________________ .

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

А-10101, В-10010, С-01110.

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

Получено сообщение 00101 11010 11110 10111. Декодируйте это сообщение. В ответе укажите четыре символа без пробелов и запятых.

Ответ: ______________­__________________ .

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

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

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

Ответ: ______________­__________________ .

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

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

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

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

Ответ: ______________­__________________ .

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

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

Ответ: ______________­_________________ .

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

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

Ответ: ______________­_________________ .

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

Ответ: ______________­_________________ .

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

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

Ответ: ______________­_________________ .

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

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

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

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

Ответ: ______________­__________________ .

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

Ответ: ______________­__________________ .

14. Система команд исполнителя РОБОТ, “живущего” в прямоугольном лабиринте на клетчатой плоскости включает 4 команды-приказа и 4 команды проверки условия. Команды-приказы:

вверх

вниз

влево

вправо

При выполнении этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.

Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится и программа прервётся.

Другие четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:

сверху свободно

снизу свободно

слева свободно

справа свободно

Цикл

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

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

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

Сколько клеток лабиринта соответствует требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)?

Ответ: ______________­__________________ .

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

Ответ: ______________­__________________ .

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

Ответ: ______________­__________________ .

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

Запрос	Количество найденных страниц (в тысячах)
Красный	21
Синий	34
Зелёный	28
Красный & Зелёный	6
Синий & Зелёный	11
Красный | Синий | Зелёный	61
Красный & Синий & Зелёный	2

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

Ответ: ______________­__________________ .

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

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

Ответ: ______________­__________________ .

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

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

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

Ответ: ______________­__________________ .

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

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

Ответ: ______________­__________________ .

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

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

Ответ: ________________________ .

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

1. прибавь 1,

2. прибавь 2,

3. прибавь 5.

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

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

Ответ: ________________________ .

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

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

Ответ: ______________­_________________ .

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

Часть 2

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

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

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

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

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

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). У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

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

Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (6,20), (5,21), (8,19) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.

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

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

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

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

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

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

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

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

8

3

4

5

7

8

3

2

9

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

14