ВАРИАНТ 6

Часть 1

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

1. Сколько единиц содержится в двоичной записи шестнадцатеричного числа 3В5Е₁₆?

Ответ: __________________________ .

2. Дан фрагмент таблицы истинности выражения F, зависящего от трёх аргументов X, Y, Z:

Перечислите в порядке возрастания без запятых и пробелов номера логических выражений, которые соответствуют 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	Сорт А.К.	Ж		5363	5771
	...			...	...

Ответ: ______________­_________________ .

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

А-01, Б-101, В-11, Г-00. Каким кодовым словом должна кодироваться буква Д? Если таких вариантов несколько, укажите самый короткий.

Ответ: ______________­_________________ .

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

1. умножь на 3,

2. прибавь 1.

Первая из них утраивает число на экране, вторая — увеличивает его на 1.

Запишите порядок команд в программе преобразования числа 4 в число 41, содержащей не более 5 команд, указывая лишь номера команд. (Например, 21211 — это программа

прибавь 1

умножь на 3

прибавь 1

умножь на 3

умножь на 3,

которая преобразует число 1 в 63.)

(Если таких программ более одной, то запишите любую из них.)

Ответ: ______________­_________________ .

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

	А	В	С	D
1	3		5
2	=C1-3	=(А1+С1)/2	=А1/3	=(В1+А2)/2

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

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

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

Ответ: ______________­_________________ .

9. Саша хочет скачать из Интернета видеоролик, объём которого 120 Мбайт. Единственный способ это сделать — на перемене. Но, к сожалению, в этот момент канал перегружен и скорость скачивания файла ограничена 256 Кбит/с. Сколько минут потребуется Саше? В ответе запишите только целое число, единицу измерения писать не нужно.

Ответ: ______________­__________________ .

10. Для кодирования 38-ми различных сообщений используют флажки 3-х видов (красный, зелёный и синий). Сколько флажков нужно использовать для одного сообщения (каждое сообщение кодируется одинаковым числом флажков)?

Ответ: ______________­_________________ .

11. Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = F(n - 1) + n/2, при n > 1 и n кратно 2

F(n) = F(n - 1) + 1, при n > 1 и n не кратно 2

F(1) = 1

Чему равно значение функции F(8)?

(В ответе запишите только натуральное число.)

Ответ: ______________­_________________ .

12. На месте преступления были обнаружены четыре обрывка бумаги. Следствие установило, что на них записаны фрагменты одного IP-адреса. Криминалисты обозначили эти фрагменты буквами А, В, С и D. Восстановите IР-адрес.

В ответе укажите последовательность букв, обозначающих фрагменты, в порядке, соответствующем IP-адресу.

А	В	С	D

Ответ: ______________­_________________ .

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

Ответ: ______________­_________________ .

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

вверх

вниз

влево

вправо

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

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

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

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

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

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

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

Цикл

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

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

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

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

Ответ:______________­________________ .

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

Ответ:______________­________________ .

16. Укажите наибольшее основание системы счисления, в которой запись десятичного числа 40 имеет ровно 3 значащих разряда.

Ответ: ______________­__________________ .

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

Запрос	Количество найденных страниц (в тысячах)
Гуси	56
Гуси | Лебеди	138
Гуси & Лебеди	26

Какое количество страниц будет найдено по запросу: Лебеди?

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

Ответ: ______________­__________________ .

18. Какое количество натуральных чисел удовлетворяет логическому условию:

Ответ: ______________­__________________ .

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

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

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

Ответ: ______________­__________________ .

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

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

Ответ: ______________­__________________ .

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

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

Ответ: ______________­_________________ .

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

1. прибавь 3,

2. умножь на 2.

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

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

Ответ: ______________­_________________ .

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

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

Ответ: ______________­_________________ .

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

Часть 2

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

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

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

Последовательно выполните следующее.

1. Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (А, В, С, D, Е, F, G и Н).

Точки, лежащие на границах областей, отдельно не рассматривать.

Область	Условие 1 (х*х+у*у<=1)	Условие 2 (y>= х)	Условие 3 (x<= 0)	Программа выведет	Область обрабатывается верно
А
В
С
D
Е
F
G
Н

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

2. Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы.)

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

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

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

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

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

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

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

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

1. а) При каких значениях числа S Петя может выиграть первым ходом? Укажите все такие значения.

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

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

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

27. При программировании школьной тестирующей системы по английскому языку выяснилось, что файлы с вопросами к тестам легко доступны, и каждый может перед тестом открыть их и заранее узнать вопросы. Было решено закодировать файлы. Для этого придумали следующий алгоритм.

Каждая строка файла кодируется отдельно.

В каждой строке ищутся отдельные слова, и все символы слова сдвигаются по алфавиту циклически вправо на длину слова.

Словом считается любая последовательность подряд идущих символов латинского алфавита, строчных и прописных.

Циклический сдвиг символа по алфавиту вправо на X — замена символа на символ, стоящий в алфавите на X позиций дальше. Если при этом происходит выход за пределы алфавита, счёт начинается с начала алфавита.

Пример циклического сдвига символов на 3 позиции:

буква “Е” превращается в букву “Н”, буква “t” — в букву “w”, буква “Y” — в букву “В”.

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

На вход программе подается строка, состоящая из не более чем 250 символов латинского алфавита, пробелов, знаков препинания, разного рода скобок, кавычек и других символов. Строка заканчивается символом “#”. Других символов “#” в строке нет.

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

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

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