Задание 23 ЕГЭ по информатике


Задание 23 в ЕГЭ  – это одно из заданий, проверяющих умение анализировать результат исполнения алгоритма, содержащего ветвление и цикл. Как правило, это задание не очень сложное и поэтому на него рекомендуется, на наш взгляд, обращать внимание всем учащимся, сдающим ЕГЭ по предмету «Информатика».

Основные способы решения задания 23 ЕГЭ по информатике.

1. Аналитический (с помощью дерева вариантов или таблицы)

2. Программный (рекурсия или динамическое программирование)

Рассмотрим пример задания.

Исполнитель преобразует число на экране.
У него две команды, которым присвоены номера:

1. Прибавить 1

2. Умножить на 2

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

Программа исполнителя – это последовательность команд.

Траектория вычислений – это последовательность результатов выполнения всех команд программы. Например, для программы 1221 при исходном числе 5 траектория будет состоять из чисел 6, 12, 24, 25.

Сколько существует программ, которые число 2 преобразуют в число 32, причём траектория вычислений содержит число 10?

По сути, необходимо ответить на два вопроса.

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

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

Для ответа на вопрос исходной задачи необходимо перемножить ответы на эти два вопроса, так как каждому способу получить из числа 2 число 10 может соответствовать любой из способов получения числа 32 из числа 10.

Приведём примеры решения задания выше.

1. Аналитический.

А) С помощью дерева вариантов посчитаем количество способов получения из числа 2 числа 10. Таких способов 7 (по числу обведённых в кружочек конечных результатов).

111.png


Б) С помощью дерева вариантов посчитаем количество способов получения из числа 10 числа 32. Таких способов 8 (по числу обведённых в кружочек конечных результатов).

222222.png

Итого 7 * 8 = 56 различных программ.

2. Программный способ (рекурсия). Пример решения дадим на языке Pascal (легко можно перенести решение на нужный вам язык). Число a – начальное, b – число после работы программы из условия задачи. На каждом шаге анализируем, какие числа можем получить за 1 ход из числа a.

function func(a, b : integer) : integer;

begin

if (b < a) then

result := 0

else if (b = a) then result := 1

else result := func(a+1, b) + func(2*a, b)

end;

begin

writeln ( func(2,10) * func(10,32) );

end.

Замечание. Рассмотрим другой возможный вопрос в задаче.

Сколько существует программ, которые число 2 преобразует в число 32, причём траектория не содержит число 10?

Необходимо найти общее число программ, преобразующих число 2 в число 32, и вычесть количество программ, содержащих число 10, то есть вычислить результат по формуле func(2,32) - func(2,10)*func(10,32).

3*. Программный способ решения (с помощью динамического программирования). Последовательно вычисляем элементы в массиве элементы с индексами от a до b. В i-м элементе массива будет храниться число способов получить из начального числа a число i. Для каждого числа (индекса массива) смотрим, какие числа можно из него получить описанными операциями. Пример на языке Pascal (легко можно перенести решение на нужный вам язык).

var dp : array[ 1..32 ] of integer;

function func2 ( const a, b : integer) : integer;

var i: integer;

begin

dp [ a ] := 1;

for i := (a+1) to b do

dp[ i ] := 0;

for i:= a to b do

begin

if ( 2 * i <= b) then

dp [2 * i ] := dp [2 * i] + dp [ i ];

if (i + 1 <= b) then

dp [i + 1] := dp [i + 1] + dp [ i ];

end;

func2 := dp [b];

end;

begin

writeln ( func2(2,10) * func2(10,32) );

end.

Надеемся, что приведенные примеры помогут вам решить задание 23 в ЕГЭ по информатике и овладеть такими понятиями, как рекурсия, динамическое программирование, дерево вариантов.