Решение задач части В демоверсии ЕГЭ-2013, 11 кл

Решение задач части В демоверсии ЕГЭ-2013 по информатике Учитель – Богачёва Г.В. Лицей № 144 Санкт-Петербурга

Задача B1 из демоверсии 2013B1 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 У исполнителя Арифметик две команды, которым присвоены номера: 1. B1 из демоверсии 2013прибавь B1 из демоверсии 20132, 2. B1 из демоверсии 2013умножь B1 из демоверсии 2013на B1 из демоверсии 20133. Первая из них увеличивает число на экране на 2, вторая утраивает его. Например, 21211 – это программа умножь B1 из демоверсии 2013на B1 из демоверсии 20133 прибавь B1 из демоверсии 20132 умножь B1 из демоверсии 2013на B1 из демоверсии 20133 прибавь B1 из демоверсии 20132 прибавь B1 из демоверсии 20132, которая преобразует число 1 в число 19. Запишите порядок команд в программе преобразования числа 3 в число 69, содержащей не более 5 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них.

Задача B1 из демоверсии 2013B1 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Решение: Решаем задачу с конца. 69 на 3 делится, значит, последняя команда 2. B1 из демоверсии 2013 умножь B1 из демоверсии 2013 на B1 из демоверсии 2013 3. B1 из демоверсии 2013 69/3= 23. 23 на 3 не делится, значит, предыдущая команда 1. B1 из демоверсии 2013 прибавь B1 из демоверсии 2013 2. B1 из демоверсии 2013 Вычитаем 23-2= 21, делится на 3, значит, предыдущая команда B1 из демоверсии 20132. B1 из демоверсии 2013 умножь B1 из демоверсии 2013 на B1 из демоверсии 2013 3. B1 из демоверсии 2013 21/3 = 7, на 3 не делится, значит, предыдущая команда B1 из демоверсии 2013 1. B1 из демоверсии 2013 прибавь B1 из демоверсии 2013 2. Вычитаем 7-2 = 5, на 3 не делится, значит, предыдущая команда B1 из демоверсии 2013 1. B1 из демоверсии 2013 прибавь B1 из демоверсии 2013 2. Вычитаем 5-2 = 3, это исходное число. Выписываем номера команд в обратном порядке B1 из демоверсии 201311212

Задача B1 из демоверсии 2013B2 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Определите значение переменной c после выполнения следующего фрагмента программы (записанного ниже на разных языках программирования). Ответ запишите в виде целого числа. Бейсик Паскаль a = 30 b = 14 a=a–2*b IF a > b THEN c=b+2*a ELSE c=b-2*a ENDIF a := 30; b := 14; a := a – 2 * b; if a > b then c := b + 2 * a else c := b - 2 * a; Си Алгоритмический a = 30; b = 14; a = a – 2 * b; if (a > b) c = b + 2 * a; else c = b - 2 * a; a := 30 b := 14 a := a – 2 * b если a > b то c := b + 2 * a иначе c := b - 2 * a все

Задача B1 из демоверсии 2013B2 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Решение: Трассируем программу: Номер команды a 1 30 2 30 14 3 2 14 2 14 4 Ответ: B1 из демоверсии 201310 2

Задача B1 из демоверсии 2013B3 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Дан фрагмент электронной таблицы: A B 1 2 4 2 = (B1 - A1) / 2 = 2 - A1/2 C = (C1-A1)*2 - 4 Какое число должно быть записана в ячейке C1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек A2:C2 соответствовала рисунку:

Задача B1 из демоверсии 2013B3 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Решение: Рассчитываем A2 = 1; B2= 1. Анализируем диаграмму B2= 1 C2 =2 A2 = 1 Отсюда C2 = 2, значит (C1-A1)*2 - 4 =2; подставляем (С1- 2) *2 – 4 = 2, значит С1= 5 Ответ: 5

Задача B4 из демоверсии 2013 Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не B1 из демоверсии 2013 менее B1 из демоверсии 2013четырёх B1 из демоверсии 2013и не B1 из демоверсии 2013более B1 из демоверсии 2013пяти B1 из демоверсии 2013сигналов (точек и тире)? Ответ: 48. Решение: Так как по условию задачи сигналов только 2 (точка и тире), то это – двоичная система счисления. Четыре сигнала – 24 =16, пять сигналов – 25 =32, всего можно закодировать 16+32=48 сигналов Ответ: 48

Задача B1 из демоверсии 2013B5 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Определите, что будет напечатано в результате выполнения программы (записанной ниже на разных языках программирования). Бейсик DIM N, S AS INTEGER N=0 S=0 WHILE S

Решение: Задача B1 из демоверсии 2013B5 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 n s 0 0 s

Задача B1 из демоверсии 2013B6 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями: F(1) = 1 F(n) = F(n–1) * n, при n >1 Чему равно значение функции F(5)? В ответе запишите только натуральное число. Решение: F(1) = 1; F(2) = F(1) * 2 =1*2=2; F(3) = F(2) * 3 =2*3=6; F(4) = F(3) * 4 =6*4=24; F(5) = F(4) * 5 =24*5=120; Ответ: 120

Задача B1 из демоверсии 2013B7 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Запись десятичного числа в системах счисления с основаниями 3 и 5 в обоих случаях имеет последней цифрой 0. Какое минимальное натуральное десятичное число удовлетворяет этому требованию? Решение: Так как последняя цифра 0, то при переводе этого числа из 10 с.с. в 3 с.с. и 5 с.с. первый остаток от деления равен 0, т.е. число кратно 3 и 5. (Напоминаю правило перевода - при переводе из 10 с.с. в любую другую делим число (частное) последовательно на основание с.с. (в которую переводим) до тех пор, пока частное не окажется меньше основания с.с. Цифры получившегося числа – остатки от деления, записанные в обратном порядке.) Наименьшее натуральное десятичное число, которое без остатка делится на 3 и на 5, это 15. Ответ: 15

Задача B1 из демоверсии 2013B8 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Ниже на четырёх языках записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: a и b. Укажите наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 2, а потом 21. Бейсик DIM X, A, B AS INTEGER INPUT X A=0: B=1 WHILE X > 0 A = A+1 B = B*(X MOD 10) X = X \ 10 WEND PRINT A PRINT B Паскаль var x, a, b: integer; begin readln(x); a:=0; b:=1; while x>0 do begin a:=a+1; b:=b*(x mod 10); x:= x div 10 end; writeln(a); write(b); end.

Задача B1 из демоверсии 2013B8 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Си Алгоритмический #include void main() { int x, a, b; scanf("%d", &x); a=0; b=1; while (x>0){ a=a+1; b=b*(x%10); x= x/10; } printf("%d\n%d", a, b); } алг нач цел x, a, b ввод x a:=0; b:=1 нц пока x>0 a:=a+1 b:=b*mod(x,10) x:=div(x,10) кц вывод a, нс, b кон

Задача B1 из демоверсии 2013B8 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Решение: Анализируем алгоритм – на экран сначала выведется a = 2 (значит, команды в цикле будут повторены 2 раза), затем b = 21. Команда b := b*(x mod 10) находит произведение b и последней цифры числа x (mod – остаток от деления на 10). Команда x := x div 10 отбрасывает последнюю цифру от числа x (div – деление нацело). Так как цикл повторяется до тех пор, пока x > 0 (то есть выходим из цикла, как только х = 0) и мы знаем, что он будет повторён 2 раза (a = 2), то отсюда x – двузначное число. Множители числа 21 3, 7. Наименьшее двузначное число, которое из них можно составить, 37. Ответ: B1 из демоверсии 201337 B1 из демоверсии 2013

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

Задача B1 из демоверсии 2013B9 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Решение: 3+1=4 1 4 3 4 + 1 + 8 = 13 4 + 1+ 3 =8 1 1 1 Цифры у каждой вершины показывают количество дорог, которые ведут к этой вершине. Подробнее: из А в Б ведёт одна дорога, пишем 1. Аналогично - из А-Г 1дорога, из А в В ведут 3 дороги, пишем 3. В пункт Д ведут одна дорога из Б + одна дорога из В, но, так как в В можно попасть тремя дорогами, значит, из А в Д можно проехать 1 + 3 = 4 дорогами.

Задача B1 из демоверсии 2013B9 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Если между пунктами одна дорога, то цифра повторяет предыдущую, если дорог несколько, складываем количество дорог, ведущих в каждый предыдущий пункт. Например, из Д в И ведёт одна дорога, но, так как в Д можно попасть 4 путями, то и в И можно приехать 4 дорогами. В Ж можно попасть из Е (1 дорога), и из В (3 дороги), и из Д (4 дороги), значит, в Ж всего ведут 8 дорог. Продолжаем до пункта Л ( К 1дорога, Ж – 8 дорог, И - 4 дороги), всего 1 + 4 + 8 = 13 дорог. Ответ : 13

Задача B1 из демоверсии 2013B10 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Документ объёмом 20 Мбайт можно передать с одного компьютера на другой двумя способами. А. Сжать архиватором, передать архив по каналу связи, распаковать. Б. Передать по каналу связи без использования архиватора. Какой способ быстрее и насколько, если: средняя скорость передачи данных по каналу связи составляет 220 бит в секунду; объём сжатого архиватором документа равен 20% исходного; время, требуемое на сжатие документа, – 5 секунд, на распаковку – 1 секунда?

Задача B1 из демоверсии 2013B10 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 В ответе напишите букву А, если быстрее способ А, или Б, если быстрее способ Б. Сразу после буквы напишите число, обозначающее, на сколько секунд один способ быстрее другого. Так, например, если способ Б быстрее способа А на 23 секунды, в ответе нужно написать Б23. Единиц измерения «секунд», «сек.», «с.» к ответу добавлять не нужно. Решение: Рассчитываем объем сжатого архиватором документа, решаем пропорцию: 20 Мб – 100% x Мб – 20% Отсюда x= (20*20)/100 = 400/100= 4 Мб = 4* 210 Кбайт = 4*220 байт = 4*223 бит

Задача B1 из демоверсии 2013B10 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Рассчитываем время на передачу архива по каналу связи: Решаем пропорцию 1 с – 220 бит x с – 4*223 бит x= 4*223 / 220 = 25= 32 с Добавляем время на сжатие документа и на распаковку, получаем, что при способе А требуется 32с + 5с +1с = 38 с. Рассчитываем время передачи файла по каналу связи без сжатия (способ Б): 1 с – 220 бит x с – 20*223 бит Отсюда x= 20*223 / 220 = 20 * 23=160 с Разница 160 с – 38 с = 122 с Ответ: А122

Задача B1 из демоверсии 2013B11 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. По заданным IP-адресу узла и маске определите адрес сети. IP –адрес узла: 217.19.128.131 Маска: 255.255.192.0 При записи ответа выберите из приведенных в таблице чисел четыре элемента IP-адреса и запишите в нужном порядке соответствующие им буквы, без использования точек. A 0 B 16 C 19 D 64 E 128 F 131 G 192 H 217

Задача B1 из демоверсии 2013B11 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Пример. Пусть искомый IP-адрес 192.168.128.0, и дана таблицаадрес 192.168.128.0, и дана таблица A B C D E F G H 128 168 255 8 127 0 17 192 В этом случае правильный ответ будет записан в виде: HBAF Решение: В маске 1 и 2 байт – максимальное число (28=256, возможные значения от 0 до 255), то есть в двоичном коде - все единицы. Так как A & 1 = A, то первые два байта маски сети совпадают с IPадресом узла. Последний байт адреса сети будет равен 0, так как A & 0 = 0, а последний байт маски равен 0. Осталось найти 3 байт адреса сети. Переводим в 2 с.с. 3 байт из IP-адреса узла 12810=2008=100000002. Переводим в 2 с.с. 19210=3008=110000002 . Поразрядная конъюнкция даёт 10 000 0002= 2008=12810. Ответ: HCEA

Задача B1 из демоверсии 2013B12 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. Запрос Фрегат | Эсминец Фрегат & Эсминец Фрегат Найдено B1 из демоверсии 2013страниц B1 из демоверсии 2013(в B1 из демоверсии 2013тысячах) 3400 900 2100 Какое количество страниц (в тысячах) будет найдено по запросу Эсминец? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Задача B1 из демоверсии 2013B12 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Решение x a y Вводим обозначения a = 900 (и фрегат, и эсминец одновременно – по определению конъюнкции) x + a = 2100 (фрегат) По условию задачи x + a + y = 3400 (по запросу «или фрегат, или эсминец, или то и другое одновременно» - по определению дизъюнкции) Подставляем 2100 + y = 3400, y = 1300 Тогда эсминец y + a = 1300 +900= 2200 Ответ: 2200

Задача B1 из демоверсии 2013B13 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 У исполнителя Удвоитель две команды, которым присвоены номера: 1. B1 из демоверсии 2013прибавь B1 из демоверсии 20131, 2. B1 из демоверсии 2013умножь B1 из демоверсии 2013на B1 из демоверсии 20132. Первая из них увеличивает на 1 число на экране, вторая удваивает его. Программа для Удвоителя – это последовательность команд. Сколько есть программ, которые число 3 преобразуют в число 23? Решение:

Задача B1 из демоверсии 2013B13 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Нарисуем частичный граф для решения этой задачи от 3 до 11 (ясно, что начиная с 12, команду 2 применять нельзя – 12*2=24 >23). Используя граф, попробуем проверить следующие программы (* - обозначено любое кол-во команд 1). Каждую программу начинаем проверять с числа 3 (программы 7 и 8 могут быть выполнены только для 3), затем для 4 (* перед программой в этом случае равна одной команде 1), затем для 5 (* перед программой в этом случае равна двум командам 1), и так далее. По графу доводим до числа, удвоение которого приводит к превышению 23, считаем, что далее число 23 достигается повторением команды 1. Считаем количество таких программ, для удобства сводим в таблицу – это поможет не пропустить варианты программ (увеличивается кол-во команд 1 между двумя командами 2).

Задача B1 из демоверсии 2013B13 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Номер Программа Число B1 из демоверсии 2013программ 1 *1 1 1 1* (все команды 1) 1 2 * 2* (с одной командой 2) 9 3 *2211* 3 4 *2121* 3 5 *2112* 2 6 *21112* 2 7 *211112* 1 8 *2111112* 1 Считаем общее кол-во 1+9+3+3+2+2+1+1=22 программы Ответ: 22

Задача B1 из демоверсии 2013B14 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Определите, какое число будет напечатано в результате выполнения следующего алгоритма (для Вашего удобства алгоритм представлен на четырех языках): Бейсик Паскаль DIM A, B, T, M, R AS INTEGER A = -20: B = 20 M = A: R = F(A) FOR T = A TO B IF F(T) < R THEN M=T R = F(T) ENDIF NEXT T PRINT M FUNCTION F(x) F = 3*(x-8)*(x-8) END FUNCTION Function F(x:integer):integer; begin F := 3*(x-8)*(x-8) end; begin a := -20; b := 20; M := a; R := F(a); for t := a to b do begin if (F(t)

Задача B1 из демоверсии 2013B14 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Си Алгоритмический #include int F(int x) { return 3*(x-8)*(x-8); } void main() { int a, b, t, M, R; a = -20; b = 20; M = a; R = F(a); for (t=a; t

Задача B1 из демоверсии 2013B14 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Решение: Анализируем алгоритм – аргумент функции меняется от – 20 до 20, в каждой точке с помощью функции определяется значение квадратичной функции (F:= 3*(x-8)*(x-8)), сравнивается с предыдущим значением функции и, если оно оказывается меньше предыдущего значения функции, то в R записывается текущее значение, а в M – значение аргумента. Значит, необходимо определить точку, в которой условие перестаёт выполняться, то есть следующее значение оказывается больше предыдущего. Функция – парабола (F:= 3*(x-8)*(x-8)), анализируем уравнение, минимальное значение при t=8. Ответ: 8

Задача B1 из демоверсии 2013B15 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2 y3, y4, которые удовлетворяют всем перечисленным ниже условиям? (x1 → x2) /\ (x2 → x3) /\ (x3 → x4) = 1 (¬y1 \/ y2) /\ (¬y2 \/ y3) /\ (¬y3 \/ y4) = 1 (y1 → x1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 → x4) = 1 В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, y1, y2 y3, y4, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Задача B1 из демоверсии 2013B15 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Решение: Решаем первое уравнение – так как дана конъюнкция импликаций, то, по определению конъюнкции, каждая из этих импликаций должна быть равна 1. Но, если х1 = 1, тогда х2 тоже 1 (если из 1 следует 0, то импликация равна 0), х3 = 1 и х4 = 1. Первый набор – 1111. Если х1 = 0, то х2 может быть или 0, или 1. Второй набор – 0111. Третий – 0011, четвертый – 0001, пятый – 0000. Переводим второе уравнение (¬y1 \/ y2) /\ (¬y2 \/ y3) /\ (¬y3 \/ y4) = (y1 → y2) /\ (y2 → y3) /\ (y3 → y4). Рассуждая аналогично, получаем 5 наборов решений 2-го уравнения. y1 y2 y3 y4 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0

Задача B1 из демоверсии 2013B15 B1 из демоверсии 2013из B1 из демоверсии 2013демоверсии B1 из демоверсии 20132013 Анализируем 3-ие уравнение. Так как если из 1 следует 0, то импликация равна 0, то для каждого набора у-ков отмечаем соответствующее количество наборов х. y1 y2 y3 y4 Наборы B1 из демоверсии 2013 решений B1 из демоверсии 2013 1-го B1 из демоверсии 2013 уравнения, B1 из демоверсии 2013 не B1 из демоверсии 2013 превращающие B1 из демоверсии 2013 3 B1 из демоверсии 2013 B1 из демоверсии 2013 уравнение B1 из демоверсии 2013в B1 из демоверсии 20130 1 1 1 1 1111 – 1 набор 0 1 1 1 1111, 0111 – 2 набора 0 0 1 1 1111, 0111, 0011 – 3 набора 0 0 0 1 1111, 0111, 0011, 0001 – 4 набора 0 0 0 0 1111, 0111, 0011, 0001, 0000 - 5 наборов Складываем 1+2+3+4+5 = 15 наборов Ответ: 15 наборов