РЕШУ ЕГЭ — информатика

Вариант № 243733

ЕГЭ по информатике 08.07.2013. Вторая волна. Вариант 501.

Дано N = 167₈, M = 79₁₆. Какое из чисел K, записанных в двоичной системе, отвечает условию N < K < M?

1)  1001100₂

2)  1011100₂

3)  1011011₂

4)  1111000₂

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

	A	B	C	D	E	F
A		3	4	4		16
B	3			5
C	4			2
D	4	5	2		6	10
E				6		3
F	16			10	3

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

Дан фрагмент таблицы истинности выражения F.

x1	x2	x3	x4	x5	x6	x7	x8	F
1	1	0	1	1	1	1	0	0
1	0	1	0	1	1	0	1	0
0	1	0	1	1	0	0	0	1

Каким из приведённых ниже выражений может быть F?

1)  ¬x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ ¬x6 ∨ x7 ∨ ¬x8

2)  x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ x8

3)  ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8

4)  x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 ∨ x8

Решение. Сначала выясним, является F конъюнкцией или дизъюнкцией.

Каковы бы ни были логические переменные х1, х2, ... х8 и отрицания к ним, их конъюнкция может быть равна 1 только в одном случае  — когда все они равны 1. Из таблицы истинности следует, что функция F принимает значение 1 для одного набора переменных и их отрицаний. Таким образом, F  — конъюнкция. Следовательно, первый и четвёртый варианты ответа не подходят.

Подставим второй вариант ответа. В третьей строке данной таблицы значение F равно 1. Это значит, что все переменные из x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ x8 должны быть равны 1. Значит, второй вариант не подходит.

Подставим третий вариант ответа. В третьей строке данной таблицы значение F равно 1. Это значит, что все переменные из ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8 должны быть равны 1. Значит, третий вариант подходит.

Проверим первую строку таблицы. Конъюнкция равна нулю в том случае, когда хотя бы одна из переменных ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8 равна 0. И такая переменная есть: ¬x7  =  0.

Проверим вторую строку таблицы. Конъюнкция равна нулю в том случае, когда хотя бы одна из переменных ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8 равна 0. И такая переменная есть: ¬x8  =  0.

Правильный ответ указан под номером 3.

Для групповых операций с файлами используются маски имён файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также могут встречаться следующие символы. Символ «?» (вопросительный знак) означает ровно один произвольный символ. Символ «*» (звездочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность. В каталоге находится 6 файлов:

fan.dat

fan.data

ifan.dat

cfat.dat

ofar.dat

fagot.dat

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

fan.dat

ifan.dat

cfat.dat

ofar.dat

1)  *fa?.dat

2)  *fa?.dat?

3)  ?fa*.dat

4)  *?fa?*.*?dat?*

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

После приёма слова производится его обработка. При этом проверяется сумма его разрядов, включая контрольный. Если она нечётна, это означает, что при передаче этого слова произошёл сбой, и оно автоматически заменяется на зарезервированное слово 0000000. Если она чётна, это означает, что сбоя не было или сбоев было больше одного. В этом случае принятое слово не изменяется. Исходное сообщение 1011100 0000011 0001010 было принято в виде 1011110 0000011 0001001.

Как будет выглядеть принятое сообщение после обработки?

1)  1011110 0000000 0001010

2)  1011110 0000000 0000000

3)  0000000 0001011 0000000

4)  0000000 0000011 0001001

Ниже представлены две таблицы из базы данных. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных ID племянницы Гранта Б. А.

Пояснение: племянницей считается дочь брата или сестры.

Таблица 1
ID	Фамилия_И. О.	Пол
28	Грант М. Д.	Ж
38	Грант А.Б	М
39	Грант Б. А.	М
40	Грант Б. Б.	М
48	Степаненко З. А.	Ж
49	Степаненко Т. Л.	Ж
50	Степаненко Л. Л.	М
58	Кривец Д. Н.	Ж
59	Кривец Р. Д.	М
60	Степаненко Е. Л.	М
61	Колос А. Е.	М
68	Кроха М. Б.	Ж
78	Волченко Т. Д.	Ж

Таблица 2
ID_Родителя	ID_Ребенка
38	39
58	39
39	40
78	40
38	48
58	48
48	49
50	49
28	50
48	60
50	60
39	68
78	68

Коле нужно с помощью электронных таблиц построить таблицу сложения чисел от 6 до 9.

Для этого сначала в диапазонах В1:Е1 и А2:А5 он записал числа от 6 до 9. Затем в ячейку Е5 записал формулу сложения, после чего скопировал её во все ячейки диапазона B2:E5. В итоге на экране получился фрагмент таблицы

сложения (см. рис.).

	A	B	C	D	E
1		6	7	8	9
2	6	12	13	14	15
3	7	13	14	15	16
4	8	14	15	16	17
5	9	15	16	17	18

Какая формула была записана в ячейке Е5?

1)  =$A5+$Е1

2)  =$A5+Е$1

3)  =А5+Е1

4)  =A$5+$Е1

Производится двухканальная (стерео) звукозапись с частотой дискретизации 64 кГц и 32-битным разрешением, результаты записываются в файл, сжатие данных не используется. Размер файла с записью не может превышать 12 Мбайт. Какая из приведённых ниже величин наиболее близка к максимально возможной продолжительности записи?

1)  25 секунд

2)  37 секунд

3)  87 секунд

4)  98 секунд

1) 25 секунд

2) 37 секунд

3) 87 секунд

4) 98 секунд

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

A  — 00000, Б  — 10011, В  — 11100.

При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 11011, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается ‘x’).

Получено сообщение 11000 00001 11110 01001. Декодируйте это сообщение  — выберите правильный вариант.

1)  ВАВБ

2)  хххх

3)  ВАВх

4)  хАВх

10.  

На числовой прямой даны два отрезка: P = [22, 72] и Q = [42, 102]. Выберите из предложенных отрезков такой отрезок A, что логическое выражение

¬((x ∈ A) ∧ (x ∈ Q)) ∨ (x ∈ P)

тождественно истинно, то есть принимает значение 1 при любом значении переменной х.

1)  [15, 50]

2)  [24, 80]

3)  [35, 75]

4)  [55, 100]

11.  

Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина пароля  — ровно 11 символов. В качестве символов могут быть использованы десятичные цифры и 32 различные буквы местного алфавита, причём все буквы используются в двух начертаниях: как строчные, так и прописные (регистр буквы имеет значение!). Под хранение каждого такого пароля на компьютере отводится одинаковое и минимально возможное целое количество байтов. При этом используется посимвольное кодирование, и все символы кодируются одинаковым и минимально возможным количеством битов. Определите объём памяти, который используется для хранения 50 паролей. (Ответ дайте в байтах.)

12.  

В программе описан одномерный целочисленный массив A с индексами от 0 до 10 и целочисленная переменная i. Ниже представлен фрагмент этой программы, записанный на разных языках программирования.

Бейсик	Паскаль
FOR i = 0 TO 10     A(i) = i-1 NEXT i FOR i = 10 TO 1 STEP -1     A(i) = A(i-1) NEXT i	for i := 0 to 10 do     A[i] := i-1; for i := 10 downto 1 do     A[i] := A[i-1];
Си++	Алгоритмический язык
for (i = 0; i <= 10; i++)     A[i] = i-1; for (i = 10; i >= 1; i--)     A[i] = A[i-1];	нц для i от 0 до 10     A[i] := i-1 кц нц для i от 10 до 1 шаг -1     A[i] := A[i-1] кц
Python
for i in range(0, 11):     A[i] = i-1 for i in range(10, 0, -1):     A[i] = A[i-1]

Чему окажутся равны элементы этого массива после выполнения фрагмента программы?

1)  0 1 2 3 4 5 6 7 8 9 9

2)  0 1 2 3 4 5 6 7 8 9 10

3)  9 9 9 9 9 9 9 9 9 9 9

4)  –1 –1 0 1 2 3 4 5 6 7 8

13.  

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, включает в себя 4 команды-приказа и 4 команды проверки условия. Команды-приказы: вверх, вниз, влево, вправо. При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится, и программа прервётся.

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

ПОКА условие

последовательность команд

КОНЕЦ ПОКА

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

ЕСЛИ условие

ТО команда1

ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

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

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

НАЧАЛО

ПОКА сверху свободно ИЛИ справа свободно

ЕСЛИ сверху свободно

ТО вверх

ИНАЧЕ вправо

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

14.  

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

1.  прибавь 1,

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

Выполняя первую из них, Калькулятор прибавляет к числу на экране 1, а выполняя вторую, умножает его на 4. Запишите порядок команд в программе, которая преобразует число 4 в число 83 и содержит не более 6 команд. Указывайте лишь номера команд. (Например, программа 21211  — это программа умножь на 4, прибавь 1, умножь на 4, прибавь 1, прибавь 1. Эта программа преобразует число 2 в число 38.)

15.  

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

Бейсик	Паскаль
a = 25 b = 6 a = a - 3 * b IF a > b THEN c = a - b ELSE c = 2 * a - b ENDIF	a := 25; b := 6; a := a - 3 * b; if a > b then c := a - b else c := 2 * a - b;
Си++	Алгоритмический язык
a = 25; b = 6; a = a - 3 * b; if (a > b) c = a - b; else c = 2 * a - b;	a := 25 b := 6 a := a - 3 * b если a > b то c := a - b иначе c := 2 * a - b все
Python
a = 25 b = 6 a = a - 3 * b if a > b:     с = a - b else:     с = 2 * a - b

16.  

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

	A	B	C
1	2		2
2	=B2	=(B1–5)/A1	=B2+C1

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

Известно, что все значения диапазона, по которым построена диаграмма, имеют один и тот же знак.

17.  

Световое табло состоит из четырёх светящихся элементов, каждый из которых может светиться одним из трёх различных цветов. Каждая комбинация из четырёх цветов кодирует определённый сигнал. Сколько различных сигналов можно передать при помощи табло при условии, что все элементы должны светиться?

18.  

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

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 0 WHILE S <= 267 S = S + 25 N = N + 10 WEND PRINT N	var n, s: integer; begin     n := 0;     s := 0;     while s <= 267 do     begin         s := s + 25;         n := n + 10     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 0;     s = 0;     while (s <= 267)     {         s = s + 25;         n = n + 10;     }     cout « n « endl; }	алг нач цел n, s n := 0 s := 0 нц пока s <= 267     s := s + 25     n := n + 10 кц вывод n кон
Python
n = 0 s = 0 while s <= 267:     s += 25     n += 10 print(n)

19.  

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

F(n)  =  n при n ≤ 2;

F(n)  =  F(n − 1) · F(n − 2) при n> 2.

Чему равно значение функции F(6)? В ответе запишите только натуральное число.

20.  

В системе счисления с некоторым основанием десятичное число 13 записывается в виде 111. Укажите это основание.

21.  

Ниже на пяти языках записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: a и b. Укажите наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 13, а потом 7.

Бейсик	Паскаль
DIM X, A, B, C AS INTEGER INPUT X A = 0: B = 0 WHILE X > 0     C = X MOD 10     A = A + C     IF C > B THEN B = C     X = X \ 10 WEND PRINT A PRINT B	var x, a, b, c: integer; begin     readln(x);     a := 0; b := 0;     while x>0 do         begin             c := x mod 10;             a := a+c;             if c>b then b := c;             x := x div 10;         end;     writeln(a); write(b); end.
Си++	Алгоритмический
#include <iostream> using namespace std; int main() {     int x, a, b, c;     cin >> x;     a = 0; b = 0;     while (x>0) {         c = x%10;         a = a+c;         if (c>b)             b = c;         x = x/10;     }     cout << a << endl << b endl; }	алг нач цел x, a, b, c ввод x a := 0; b := 0 нц пока x>0     c := mod(x,10)     a := a+c         если c>b         то b := c     все     x := div(x,10) кц вывод a, нс, b кон
Python
x = int(input()) a = 0 b = 0 while x > 0:     c = x % 10     a += c     if c > b:         b = c     x //= 10 print(a) print(b)

Решение. Рассмотрим цикл, число шагов которого зависит от изменения переменной x:

while x > 0 do begin

...

x:= x div 10;

end;

Т. к. оператор div оставляет только целую часть от деления, то при делении на 10 это равносильно отсечению последней цифры. Из приведенного цикла видно, что на каждом шаге от десятичной записи x отсекается последняя цифра до тех пор, пока все цифры не будут отсечены, то есть x не станет равно 0; поэтому цикл выполняется столько раз, сколько цифр в десятичной записи введенного числа.

При этом, переменной c присваивается остаток от деления x на 10, переменная a увеличивается на остаток от деления х на 10. Если остаток от деления x на 10 больше переменной b, то переменной b присваивается значение переменной c. Поскольку требуется ,чтобы программа напечатала сначала 13, необходимо, чтобы сумма цифр числа x была равна 13. Поскольку вторым должно быть напечатано число 7, необходимо, чтобы одной из цифр числа x была цифра 7. Наименьшее такое число  — 67.

Ответ: 67.

Приведём другое решение на языке Python.

for i in range(1, 1000):

x = i

a = 0

b = 0

while x > 0:

c = x % 10

a += c

if c > b:

b = c

x //= 10

if a == 13 and b == 7:

print(i)

break

22.  

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

23.  

Документ объёмом 12 Мбайт можно передать с одного компьютера на другой двумя способами. А. Сжать архиватором, передать архив по каналу связи, распаковать. Б. Передать по каналу связи без использования архиватора. Какой способ быстрее и насколько, если:

средняя скорость передачи данных по каналу связи составляет 2²² бит в секунду;
объём сжатого архиватором документа равен 75% исходного;
время, требуемое на сжатие документа,  — 13 секунд, на распаковку  — 3 секунды?

В ответе напишите букву А, если быстрее способ А, или Б, если быстрее способ Б. Сразу после буквы напишите число, обозначающее, на сколько секунд один способ быстрее другого. Так, например, если способ Б быстрее способа А на 23 секунды, в ответе нужно написать Б23. Единицы измерения «секунд», «сек.», «с.» к ответу добавлять не нужно.

24.  

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

IP-⁠адрес узла: 128.64.208.32

Маска: 255.255.224.0

При записи ответа выберите из приведённых в таблице чисел четыре элемента IP-⁠адреса сети и запишите в нужном порядке соответствующие им буквы без использования точек.

A	B	C	D	E	F	G	H
0	32	64	128	192	208	224	255

Пример.

Пусть искомый IP-⁠адрес: 192.168.128.0 и дана таблица:

A	B	C	D	E	F	G	H
128	168	255	8	127	0	17	192

В этом случае правильный ответ будет записан в виде: HBAF.

25.  

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет:

Запрос	Найдено страниц (в тысячах)
Динамо & Зенит & Спартак	150
Динамо & Спартак	380
Динамо & Зенит	310

Компьютер печатает количество страниц (в тысячах), которое будет найдено по следующему запросу:

Динамо & (Зенит | Спартак).

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

26.  

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

1.  прибавь 1,

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

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

27.  

Напишите в ответе число, которое будет напечатано в результате выполнения следующего алгоритма (для Вашего удобства алгоритм представлен на четырёх языках).

Бейсик	Паскаль
DIM A, B, T, M, R AS INTEGER A = 5: B = 35 M = A: R = F(A) FOR T = A TO B     IF F(T) > R THEN         M = T         R = F(T)     END IF NEXT T PRINT M FUNCTION F(x)     F = 3(x-1)(x-1)+37 END FUNCTION	var a,b,t,M,R: integer;     Function F(x:integer): integer;         begin             F := 3(x-1)(x-1)+37         end; begin     a := 5; b := 35;     M := a; R := F(a);     for t := a to b do begin         if (F(t) > R) then begin             M := t;         R := F(t)         end     end;     write(M); end.
Си++	Алгоритмический
#include <iostream> using namespace std; int F(int x) {     return 3(x-1)(x-1)+37; } void main() {     int a, b, t, M, R;     a = 5; b = 35;     M = a; R = F(a);     for (t = a; t <= b; t++) {         if (F(t) > R) {             M = t; R = F(t);         }     }     cout « M « endl; }	алг нач цел a, b, t, M, R a := 5; b := 35 M := a; R := F(a) нц для t от a до b если F(t) > R то M := t; R := F(t) все кц вывод M кон алг цел F(цел x) нач знач := 3(x-1)(x-1)+37 кон
Python
def f(x):     return 3(x-1)(x-1)+37 a = 5 b = 35 M = a R = f(a) for t in range(a, b+1):     if (f(t) > R):         M = t         R = f(t); print(M)

28.  

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

(x₁ ∧ ¬x₂) ∨ (¬x₁ ∧ x₂) ∨ (x₃ ∧ x₄) ∨ (¬x₃ ∧ ¬x₄) = 1

(x₃ ∧ ¬x₄) ∨ (¬x₃ ∧ x₄) ∨ (x₅ ∧ x₆) ∨ (¬x₅ ∧ ¬x₆) = 1

...

(x₇ ∧ ¬x₈) ∨ (¬x₇ ∧ x₈) ∨ (x₉ ∧ x₁₀) ∨ (¬x₉ ∧ ¬x₁₀) = 1

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

Решение. Построим древо решений для первого уравнения.

Первое уравнение имеет 12 решений. Второе уравнение связано с первым только через переменные x₃ и x₄. На основании древа решений для первого уравнения выпишем пары значений переменных x₃ и x₄, которые удовлетворяют первому уравнению и укажем количество таких пар значений.

Количество пар значений	x₃	x₄
×4	1	1
×4	0	0
×2	1	0
×2	0	1

Поскольку уравнения идентичны с точностью до индексов переменных, древо решений второго уравнения аналогично первому. Следовательно, пара значений x₃  =  1 и x₄  =  1 порождает два набора переменных x₃, ..., x₆, удовлетворяющих второму уравнению. Поскольку среди наборов решений первого уравнения данных пар четыре, всего получаем 4 · 2  =  8 наборов переменных x₁, ..., x₆, удовлетворяющих системе из двух уравнений. Рассуждая аналогично для пары значений x₃  =  0 и x₄  =  0, получаем 8 наборов переменных x₁, ..., x₆. Пара x₃  =  1 и x₄  =  0 порождает четыре решения второго уравнения. Поскольку среди наборов решений первого уравнения данных пар две, получаем 2 · 4  =  8 наборов переменных x₁, ..., x₆, удовлетворяющих системе из двух уравнений. Аналогично для x₃  =  0 и x₄  =  1  — 8 наборов решений. Всего система из двух уравнений имеет 8 + 8 + 8 + 8 = 32 решения.

Проведя аналогичные рассуждения для системы из трёх уравнений, получаем 80 наборов переменных x₁, ..., x₈, удовлетворяющих системе. для системы из четырёх уравнений существует 192 набора переменных x₁, ..., x₁₀, удовлетворяющих системе.

Ответ: 192.

29.  

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

Бейсик	Паскаль
INPUT x, y IF y<=1 THEN IF y>=x THEN IF x>=-1 THEN IF xx+yy<=1 THEN PRINT "принадлежит" ELSE PRINT "не принадлежит" END IF END IF END IF END IF END	var x,y: real; begin readln(x,y); if y<=1 then if y>=x then if x>=-1 then if xx+yy<=1 then write('принадлежит') else write('не принадлежит'); end.
Си++	Алгоритмический
#include <iostream> using namespace std; int main() { float x,y; cin >> x >> y; if (y<=1) if (y>=x) if (x>=-1) if (xx+yy<=1) cout << "принадлежит"; else cout << "не принадлежит"; }	алг нач вещ x,y ввод x,y если y<=1 то если y>=x то если x>=-1 то если xx+yy<=1 то вывод 'принадлежит' иначе вывод 'не принадлежит' все все все все кон
Python
x = float(input()) y = float(input()) if y<=1:     if y>=x:         if x>=-1:             if xx+yy<=1:                 print("принадлежит")             else:                 print("не принадлежит")

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

1.  Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (A, B, C, D, E, F, G, H, I, J, K). Точки, лежащие на границах областей, отдельно не рассматривать. Координатные оси не являются границами областей. В столбцах условий укажите «да», если условие выполнится, «нет», если условие не выполнится, «—» (прочерк), если условие не будет проверяться, «не изв.», если программа ведёт себя по-разному для разных значений, принадлежащих данной области. В столбце «Программа выведет» укажите, что программа выведет на экран. Если программа ничего не выводит, напишите «—» (прочерк). Если для разных значений, принадлежащих области, будут выведены разные тексты, напишите «не изв.». В последнем столбце укажите «да» или «нет».

Область	Условие1 (y<=1)	Условие 2 (y>=x)	Условие 3 (x>=−1)	Условие 4 (xx+yy<=1)	Программа выведет	Область обрабатывается верно
A
В
С
D
Е
F
G
Н
I
J
K

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

Критерии проверки:

Критерии оценивания выполнения задания	Баллы
Выполнены все три действия	3
Правильно выполнены два действия из трёх. При этом при написании операций сравнения допускается одно неправильное использование строгих/нестрогих неравенств (считается несущественной ошибкой, погрешностью записи). Например, вместо «y>=x» один раз используется «y>x». В работе (во фрагментах программ) допускается наличие отдельных синтаксических ошибок, не искажающих замысла автора решения	2
Правильно выполнено только одно действие из трёх, то есть либо только приведена таблица, которая содержит ошибки в не более чем одной строке, либо таблица не приведена (или приведена и содержит ошибки более чем в одной строке), но исправлена одна ошибка программы. При оценивании этого задания на 1 балл допускается не учитывать корректность работы программ на точках границ областей (вместо нестрогих неравенств в решении были использованы строгие неравенства или наоборот). В работе (во фрагментах программ) допускается наличие отдельных синтаксических ошибок, не искажающих замысла автора решения	1
Ни один из пунктов задания не выполнен, то есть не выполнены критерии, позволяющие поставить ученику 1 балл	0
Максимальный балл	3

30.  

Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от –1000 до 1000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести минимальное значение среди положительных элементов массива, кратных 8. Если в исходном массиве нет элемента, значение которого положительно и делится на 8, то вывести сообщение «Не найдено». Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.

Бейсик	Паскаль
N = 20 DIM A(N) AS INTEGER DIM I, J, MIN AS INTEGER FOR I = 1 TO N INPUT A(I) NEXT I ... END	const N = 20; var a: array [1..N] of integer; i, j, min: integer; begin for i := 1 to N do readln(a[i]); ... end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; #define N 20 int main() { int a[N]; int i, j, min; for (i = 0; i<N; i++) cin >> a[i]; ... }	алг нач цел N = 20 целтаб a[1:N] цел i, j, min нц для i от 1 до N ввод a[i] кц ... кон
Eстественный язык
Объявляем массив A из 20 элементов. Объявляем целочисленные переменные I, J, MIN. В цикле от 1 до 20 вводим элементы массива A с 1-го по 20-й. ...
Python
# допускается также использовать # целочисленные переменные j, min a = [] n = 20 for i in range(0, n): a.append(int(input()))

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

Решение. Содержание верного ответа (допускаются иные формулировки ответа, не искажающие его смысла).

Бейсик	Паскаль
MIN = 1001 FOR I = 1 TO N IF A(I)>0 AND A(I) MOD 8=0 AND A(I) < MIN THEN MIN = A(I) END IF NEXT I IF MIN < 1001 THEN PRINT MIN ELSE PRINT "Не найдено" END IF	min := 1001; for i := 1 to N do if (a[i]>0) and (a[i] mod 8=0) and (a[i]< min) then min := a[i]; if min < 1001 then writeln(min) else writeln("Не найдено");
Си	Алгоритмический язык
min = 1001; for (i = 0; i< N; i++) if (a[i]>0 && a[i]%8==0 && a[i]< min) min = a[i]; if (min < 1001) cout << min; else cout << "Не найдено";	min := 1001 нц для i от 1 до N если a[i]>0 и mod(a[i],8)=0 и a[i]< min то min := a[i] все кц если min < 1001 то вывод min иначе вывод "Не найдено" все
Eстественный язык
Записываем в переменную MIN начальное значение, равное 1001. В цикле от первого элемента до двадцатого находим остаток от деления элемента исходного массива на 8. Если значение данного остатка равно 0 и значение текущего элемента массива больше 0, то сравниваем значение текущего элемента массива со значением переменной MIN. Если текущий элемент массива меньше MIN, то записываем в MIN значение этого элемента массива. Переходим к следующему элементу. После завершения цикла проверяем значение переменной MIN. Если оно меньше 1001, то выводим его, иначе выводим сообщение «Не найдено».

Критерии проверки:

Критерии оценивания выполнения задания	Баллы
Предложен правильный алгоритм, выдающий верное значение. Допускается запись алгоритма на другом языке, использующая аналогичные переменные. В случае, если язык программирования использует типизированные переменные, описания переменных должны быть аналогичны описаниям переменных на естественном языке. Использование нетипизированных или необъявленных переменных возможно только в случае, если это допускается языком программирования, при этом количество переменных и их идентификаторы должны соответствовать условию задачи. В алгоритме, записанном на языке программирования, допускается наличие отдельных синтаксических ошибок, не искажающих замысла автора программы.	2
В любом варианте решения может присутствовать не более одной ошибки из числа следующих: 1) не инициализируется или неверно инициализируется переменная MIN (например, присваивается начальное значение, меньшее или равное 1000); 2) при выводе ответа не учитывается, что требуемого числа в массиве может не быть; 3) отсутствует вывод ответа в случае существования минимального числа, удовлетворяющего условию задачи; 4) в сравнении с 0 вместо знака «больше» используется знак «больше или равно»; 5) неверно осуществляется проверка делимости на 8; \ 6) на делимость на 8 проверяется не значение элемента, а его индекс; 7) в сложном условии вместо логической операции «И» используется логическая операция «ИЛИ»; 8) используется переменная, не объявленная в разделе описания переменных; 9) не указано или неверно указано условие завершения цикла; 10) индексная переменная в цикле не меняется (например, в цикле while) или меняется неверно; 11) неверно расставлены операторные скобки	1
Ошибок, перечисленных в п. 1–11, две или больше, или алгоритм сформулирован неверно	0
Максимальный балл	2

31.  

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 47. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 47 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤46.

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

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

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

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

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

3.  Укажите значение S, при котором:

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

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

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

Решение. 1а) Петя может выиграть, если S = 16, …, 46. Во всех этих случаях достаточно утроить количество камней. При меньших значениях S за один ход нельзя получить кучу, в которой больше 46 камней.

1б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 15 камней. Тогда после первого хода Пети в куче будет 16 или 45 камней. В обоих случаях Ваня утраивает количество камней и выигрывает в один ход.

2.  Возможные значения S: 5 и 14. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 15 камней: в первом случае утроением, во втором добавлением одного камня. Эта позиция разобрана в п. 1б. В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (то есть Петя) следующим ходом выиграет.

3.  Возможное значение S: 13. После первого хода Пети в куче будет 14 или 39 камней. Если в куче станет 39 камней, Ваня утроит количество камней и выиграет первым ходом. Ситуация, когда в куче 14 камней, уже разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Ваня), выигрывает своим вторым ходом.

В таблице изображено дерево возможных партий при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) подчёркнуты. На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы).

	Положения после очередных ходов
И. п.	1-й ход Пети (разобраны все ходы)	1-й ход Вани (только ход по стратегии)	2-й ход Пети (разобраны все ходы)	2-й ход Вани (только ход по стратегии)
13	13 + 1 = 14	14 + 1 = 15	15 + 1 = 16	16*3 = 48
	13 + 1 = 14	14 + 1 = 15	15*3 = 45	453 = 135*
	13*3 = 39	393 = 117*

Критерии проверки:

Критерии оценивания выполнения задания	Баллы
Выполнены второе и третье задания. Первое задание выполнено полностью или частично. Здесь и далее допускаются арифметические ошибки, которые не искажают сути решения и не приводят к неправильному ответу	3
Не выполнены условия, позволяющие поставить 3 балла, и выполнено одно из следующих условий. 1. Третье задание выполнено полностью. 2. Первое и второе задания выполнены полностью. 3. Первое задание выполнено полностью или частично, для второго и третьего заданий указаны правильные значения S	2
Не выполнены условия, позволяющие поставить3 или2 балла, и выполнено одно из следующих условий. 1. Первое или второе задание выполнено полностью. 2. Во втором задании правильно указано одно из двух возможных значений S, и для этого значения указана и обоснована выигрышная стратегия Пети. 3. Первое задание выполнено частично, и для одного из остальных заданий правильно указаны значения S. 4. Для второго и третьего заданий правильно указаны значения S	1
Не выполнено ни одно из условий, позволяющих поставить 3, 2 или 1 балл	0
Максимальный балл	3

32.  

Радиотелескоп пытается получать и анализировать сигналы, поступающие из различных участков космоса, при этом различные шумы переводятся в последовательность целых неотрицательных чисел. Чисел может быть очень много, но не может быть меньше трёх. Все числа различны. Хотя бы одно из чисел нечётно.

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

Вам предлагается написать программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет обрабатывать результаты, приходящие из одного участка, находя основное подмножество. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество сигналов N. В каждой из последующих N строк записано одно целое неотрицательное число, не превышающее 10⁹.

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

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

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

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

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

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

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

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

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

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

123

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

Решение. Основное подмножество состоит из всех значений сигналов, кроме 0, если он встречается, и кроме минимального нечётного значения, если таких значений чётное число.

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

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

Пример правильной и эффективной программы на языке Паскаль:	Пример правильной и эффективной программы на языке Бейсик:
var n,i,j,k,c,min,a: longint; begin readln(n); min := 1000000001; k := 0; j := 0; c := 0; for i := 1 to n do begin readln(a); if a = 0 then j := i; if a mod 2 <> 0 then begin c := c + 1; if a < min then begin min := a; k := i; end end end; for i :=1 to n do if (i <> j) and ((c mod 2 <> 0) or (i <> k)) then write(i,' '); end.	INPUT n min = 0 k = 0 j = 0 c = 0 FOR i = 1 TO n INPUT a IF a = 0 THEN j = i IF a MOD 2 <> 0 THEN c = c + 1 IF (min = 0) OR (a < min) THEN min = a k = i END IF END IF NEXT i FOR i = 1 TO n IF (i <> j) AND ((c MOD 2 <>0) OR (i <> k)) THEN PRINT i NEXT i END

Пример решения задачи A на языке Паскаль.

var  a: array[1..10000] of integer; {исходные данные}
  min: integer; {минимальное нечётное число}
  N: integer; {количество чисел}
  sum: integer; {максимальная сумма}
  i: integer;
begin
  readln(N);
  min := 1000000001;
  sum := 0;
  for i := 1 to N do readln(a[i]);
  for i := 1 to N do begin
    sum := sum + a[i];
    if (a[i] mod 2 <> 0) and (a[i]      min := a[i];
    end;
  if sum mod 2 = 0 then
    for i := 1 to N do
      if (a[i] <> min) and (a[i]<>0) then write(i, ' ');
  if sum mod 2 <> 0 then
    for i := 1 to N do
      if (a[i]<>0) then write(i, ' ');
end.

Критерии проверки:

Критерии оценивания выполнения задания	Баллы
Критерии оценивания задания А
Программа решает поставленную задачу для любых соответствующих условию входных данных. Например, допускается переборное решение, аналогичное приведённой выше Программе 1. Допускается до семи синтаксических и приравненных к ним ошибок (см. критерии оценивания задания Б на 4 балла). Допускается до двух содержательных ошибок, описанныхв критериях оценивания задания Б на 3 балла	2
Не выполнены условия, позволяющие поставить 2 балла. Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может быть представлена отдельными фрагментами, без ограничений на количество синтаксических и содержательных ошибок. 1 балл ставится также за решения, верные лишь в частных случаях	1
Не выполнены критерии, позволяющие поставить 1 или 2 балла	0
Максимальный балл для задания А	2

Критерии оценивания выполнения задания Б	Баллы
Программа правильно работает для любых соответствующих условию входных данных и при этом эффективна как по времени, так и по памяти, т.е. не используются массивы и другие структуры данных, размер которых зависит от количества входных элементов, а время работы пропорционально этому количеству. Возможно использование массивов и динамических структур данных (например, контейнеры STL в программе на языке С++) при условии, что в них в каждый момент времени хранится фиксированное количество элементов, требующих для хранения меньше 1кб (минимально необходимое количество — шесть; допускается решение с запасом). Программа может содержать не более трёх синтаксических ошибок следующих видов: — пропущен или неверно указан знак пунктуации (запятая, точка с запятой, скобки и т.д.); — неверно написано или пропущено служебное слово языка программирования; — не описана или неверно описана переменная; — применяется операция, недопустимая для соответствующего типа данных. К синтаксическим ошибкам приравнивается использование неверного типа данных (например, использование целого типа вместо вещественного для представления данных при вводе и обработке). Если одна и та же ошибка встречается несколько раз, она считается за одну ошибку	4
Не выполнены условия, позволяющие поставить 4 балла. Программа правильно работает для любых соответствующих условию входных данных, время работы пропорционально количеству входных элементов. Размер используемой памяти не имеет значения и может зависеть от объёма входных данных. В частности, допускается использование одного или нескольких массивов размера N (как в приведённой выше программе 3). Программа может содержать не более пяти синтаксических и приравненных к ним ошибок, описанных в критериях на 4 балла. Кроме того, допускается наличие не более одной содержательной ошибки из числа следующих: — неверная инициализация при поиске минимального значения; — неверная обработка начальных элементов данных, которая может, например, привести к получению ошибочного ответа при 15 < N < 30; — неточное определение границ массива, выход за границу массива (например, описан массив с границами от 1 до 15, а реально используется от 0 до 14 или наоборот); — вычисленный индекс элемента массива на 1 отличается от верного; — используется операция "<" вместо "<=", "or" вместо "and" и т.п.; — не учитывается, что заданные показания могут начинаться с одного или нескольких чётных чисел; — не учитывается, что для данного набора показаний может не быть ни одного удовлетворяющего условиям произведения	3
Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет. Например, допускается переборное решение, аналогичное приведённой выше программе 4. Допускается до семи синтаксических и приравненных к ним ошибок (см. критерии на 4 балла). Допускается до двух содержательных ошибок, описанных в критериях на 3 балла	2
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может быть представлена отдельными фрагментами, без ограничений на количество синтаксических и содержательных ошибок. 1 балл ставится также за решения, верные лишь в частных случаях	1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла	0
Максимальный балл для задания Б	4
Итоговый максимальный балл	4

№ п/п	№ задания	Ответ
1	6248	4
2	6249	13
3	6250	3
4	6251	1
5	6252	4
6	6253	49
7	6254	2
8	6255	1
9	6256	3
10	6257	1
11	6258	500
12	6259	4
13	6260	21
14	6261	122111
15	6262	1
16	6263	9
17	6264	81
18	6265	110
19	6266	32
20	6267	3
21	6268	67
22	6269	20
23	6270	Б10
24	6271	DCEA
25	6272	540
26	6273	20
27	6274	35
28	6275	192

Область	Условие 1 (y<=1)	Условие 2 (y>=x)	Условие 3 (x>=–1)	Условие 4 (xx+yy<=1)	Программа выведет	Область обрабатывается верно
A	нет	—	—	—	—	нет
B	нет	—	—	—	—	нет
C	нет	—	—	—	—	нет
D	да	да	нет	—	—	нет
E	да	да	да	нет	не принадлежит	нет
F	да	да	да	да	принадлежит	да
G	да	да	да	нет	не принадлежит	да
H	да	нет	—	—	—	нет
I	да	нет	—	—	—	нет
J	да	нет	—	—	—	нет
K	да	да	да	нет	не принадлежит	да

	A	B	C
1	2		2
2	=(B1–5)/2	=(B1–5)/2	=(B1–5)/2+2

ЕГЭ по информатике 08.07.2013. Вторая волна. Вариант 501.

Ключ