Разбор заданий повышенного уровня сложности, вызвавших наибольшие затруднения у выпускников 2014 г.
Чернышова Е.И.,
учитель информатики МБОУ СОШ№10 г.Хабаровска
2015 год
ЕГЭ по информатике 2014 года
Всего 32 задания, из них:
- 15 заданий базового уровня,
- 13 заданий повышенного уровня,
- 4 задания высокого уровня
Выполняемость заданий повышенного уровня
Предполагаемый процент выполнения заданий повышенного уровня – 40–60%.
Выполняемость заданий повышенного уровня
Предполагаемый процент выполнения заданий повышенного уровня – 40–60%.
Наиболее трудные задания
В13 (умение построить дерево путей вычислений, а также, умение анализировать такое дерево, например, вычислять количество путей, удовлетворяющих заданным свойствам) В22 в 2015 году
В14 (анализ алгоритма, содержащего вызов пользовательской функции) В21
Пример задания В13
У исполнителя Увеличитель две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 2.
Первая из них увеличивает число на экране на 1, вторая – умножает его на 2. Программа для Увеличителя – это последовательность команд.
Сколько есть программ, которые число 3 преобразуют в число 23?
Решение (1 способ)
Будем строить дерево решений. Ребра в нем будут помечены допустимыми командами, в каждом узле будет записано текущее число, т.е. число, полученное из числа 3 с помощью последовательности команд, которые соответствуют пути из корня в этот узел. В корне будет записано число 3. Нас интересует количество путей из корня в вершины, помеченные числом 23. Так как обе команды увеличивают исходное число, то вершины, соответствующие числам, большим, чем 23, рассматривать не нужно.
Дерево решений
Осталось пересчитать количество вершин с пометкой 23
Ответ: 22
Решение (2 способ)
Будем решать поставленную задачу последовательно для чисел 3, 4, …, 23. То есть для каждого из чисел определим, сколько программ исполнителя существует для получения этого числа из числа 3. Количество программ, которые преобразуют число 3 в число n , будем обозначать через R(n) .
Если число не делится на два, то оно может быть получено только из предыдущего с помощью команды прибавь 1.
Значит, количество искомых программ для такого числа равно количеству программ для предыдущего числа: R(n) = R(n-1).
Если число на 2 делится, то вариантов последней команды два: прибавь 1 и умножь на 2,
тогда R(n) = R(n-1) + R(n/2). В общем виде это можно записать так:
R(n) = R(p1)+R(p2), где p1, p2 – числа, из которых число n можно получить за одно действие. Понятно, что если у числа n, не 2, а, один «предшественник», то формула будет выглядеть R(n) = R(p).
Пример задания В13
У исполнителя Удвоитель-Утроитель три команды, которым присвоены номера:
1. прибавь 1
2. умножь на 2
3. умножь на 3.
Первая из них увеличивает на 1 число на экране, вторая увеличивает это число в 2 раза, третья - в 3 раза.
Программа для Удвоителя-Утроителя — это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 13?
38
Правильный ответ
Пример задания В13
У исполнителя Прибавитель две команды, которым присвоены номера:
1. прибавь 1,
2. увеличь старшую цифру числа на 1.
Первая из них увеличивает число на экране на 1, вторая увеличивает на 1 старшую (левую) цифру числа, например число 23 с помощью такой команды превратится в число 33. Если старшая цифра числа равна 9, то вторая команда оставляет это число неизменным. Программа для Прибавителя — это последовательность команд. Сколько есть программ, которые число 15 преобразуют в число 37?
Правильный ответ
20
Пример задания В13
У исполнителя четыре команды, которым присвоены номера:
1. прибавь 1,
2. сделай чётное,
3. сделай нечётное,
4. умножь на 10.
Первая из них увеличивает на 1 исходное число x, вторая умножает это число на 2, третья переводит число x в число 2x + 1, четвёртая умножает его на 10. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. Программа для исполнителя — это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 15?
Правильный ответ
84
Еще пример задания В13
У исполнителя Калькулятор две команды:
1. прибавь 2
2. умножь на 3.
Первая из них увеличивает число на экране на 2, вторая — утраивает его. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 3 команды?
Решение
4
8
6
2
18
12
14
6
36
8
10
18
24
20
54
Ответ: 8 чисел
Задание В14
Напишите в ответе число различных значений входной переменной k, при которых программа выдаёт тот же ответ, что и при входном значении k = 64. Значение k = 64 также включается в подсчёт различных значений k. Для Вашего удобства программа приведена на четырёх языках программирования.
0 цикл завершается в ситуации, когда f(i) (при k 0 это наступает раньше, чем i i 3 истинно. Очевидно, что это все i . " width="640"
Решение задания В13
При решении данной задачи следует выполнить два действия:
Во-первых, определить, что за функция вызывается в основном алгоритме. Для данной задачи это, как хорошо видно из описания, куб числа ( f=n 3 ).
Во-вторых, определить, при каком условии завершается выполнение цикла. Для любого целого k 0 цикл завершается в ситуации, когда f(i) (при k 0 это наступает раньше, чем i i 3 истинно. Очевидно, что это все i .
Итак, при k=64 программа выведет число 4 (значение переменной i, такое, что i 3 = 64 ). При 9 программа выведет число 3 , при k = 125 программа выведет число 5 . Таким образом, число 4 будет выводиться программой для всех 64 . Таких целых чисел в этом диапазоне ровно 61 .
Задание В14
Напишите в ответе число различных значений входной переменной k, при которых программа выдаёт тот же ответ, что и при входном значении k = 120. Значение k = 120 также включается в подсчёт различных значений k. Для Вашего удобства программа приведена на четырёх языках программирования.
Решение
- Проанализировав описание функции, видим, что это факториал (f=n!), записанный как рекурсивная функция. Дальше мы понимаем, что 5! = 120 , 6!=720 и число 5 программа выведет при всех 120 . Таких целых значений k всего 600 .
0) and (F(i) K) do i:=i-1; writeln(i); end. Правильный ответ 96 " width="640"
Еще задание В14
Определите, количество чисел K, для которых следующая программа выведет такой же результат, что и для K = 24:
var i, k: integer;
function F(x:integer):integer;
begin
if x = 1 then
F:=1
else F:=x*F(x-1);
end;
begin
i := 15;
readln(K);
while (i0) and (F(i) K) do
i:=i-1;
writeln(i);
end.
Правильный ответ
96
Использованные ресурсы
http://kpolyakov.spb.ru/school/ege.htm
http://inf.reshuege.ru/?redir=1
http://fipi.ru/ege-i-gve-11/analiticheskie-i-metodicheskie-materialy