Задание 23 информатика егэ через рекурсию

Здравствуйте! Сегодня речь пойдёт о 23 задании из ЕГЭ по информатике 2023.

Двадцать третье задание является последним заданием из первой части ЕГЭ по информатике 2023.

Давайте познакомимся с примерными задачами 23 задания из ЕГЭ по информатике 2023.

Задача (классическая)

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

1. прибавить 3,
2. умножить на 2.

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

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

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

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y: return 0

    if x < y: return F(x+3, y) + F(x*2, y)

print(F(1, 25))

Число x, это то число, с которым мы работаем. Число y — это куда нужно прийти.

Если число x достигло пункта назначения, то возвращаем 1. Если оно перескочило y, то возвращаем 0. А если ещё не дошло до y, то продолжаем вычисления с помощью рекурсии.

Ответ получается равен 9.

2 Способ (графический, для понимания)

Начинаем рассматривать задачку с конца. Если число нечётное, то оно может быть получено только с помощью первой команды. Если число чётное, то оно может быть получено с помощью двух команд.

Видим, что количество программ получается 9!

3 Способ (С помощью таблицы)

Некоторое число i можно получить только двумя способами: либо c помощью первой команды, либо с помощью второй команды. Тогда количество программ для некоторого числа i будет складываться из двух чисел: количества программ для числа i-3 и количества программ для числа i / 2 (Если i — чётное).

В первой строке пишутся числа от 1 до 25 (до того числа, которое нужно получить).

Во второй строке пишутся числа, которые в сумме с 3 (тройкой) дают числа, написанные в первой строке. (Прим. начиная с 4, числа идут по порядку.)

В третьей строке пишутся числа, которые при умножении на 2 дают числа, написанные в первой строке. (Прим. числа так же идут по порядку через одну пустую ячейку.)

В четвёртой строке для единицы ставим 1. Для остальных ячеек: смотрим, какие числа участвуют во второй и третьей строке для конкретной ячейки. Затем, эти числа ищем в первой строке и пишем сумму количеств программ для этих чисел (Т.е. пишем сумму уже известных значений из четвёртой строки для этих чисел).

Таким образом, основная идея 23 задания из ЕГЭ по информатике заключается в том, что результат каждого шага опирается на результаты предыдущих шагов!

Получаем ответ 9!

Ответ: 9

Задача (с избегаемым узлом)

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

1. прибавь 1

2. сделай нечётное

Первая из этих команд увеличивает число x на экране на 1, вторая переводит число x в число 2x+1. Например, вторая команда переводит число 10 в число 21. Программа для исполнителя НечетМ — это последовательность команд. Сколько существует таких программ, которые число 1 преобразуют в число 25, причём траектория вычислений не содержит число 24? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 17, 18.

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 18 января 2017 года Вариант ИН10304

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y or x==24: return 0

    if x < y: return F(x+1, y) + F(x*2+1, y)

print(F(1, 25))

Здесь на нельзя получать число 24, поэтому, если x будет равен 24, то мы возвращаем ноль.

Ответ получается равен 10.

2 способ (Решение с помощью таблицы).

Мы не может получать число 24! Значит, единственным способом добраться до числа 25 будет вторая команда.

Получается, что сначала нужно получить число 12, тогда 2 * 12 + 1 = 25 (2x+1). Это единственный путь!

Каждое число можем получить только 2 способами (Либо с помощью первой команды, либо с помощью второй команды). Поэтому количество программ для некоторого числа i будет равно сумме количеств команд для числа i-1 и для числа (i — 1) / 2 (Если число нечётное.) Если число i — чётное, то до числа i можно добраться единственным способом (с помощью первой команды).

Если записать с помощью массива:

A[i]=A[i-1] — если i — четное.
A[i]=A[i-1] + A[(i-1)/2] — если i нечетное;

Ответ: 10

Задача (ЕГЭ по информатике, Москва, 2019)

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

1. Прибавить 1
2. Умножить на 3
3. Прибавить 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 3, третья увеличивает его на 2.

Сколько существует программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений содержит число 9 и число 11?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y: return 0

    if x < y: return F(x+1, y) + F(x*3, y) + F(x+2, y)

print(F(2, 9)*F(9, 11)*F(11, 12))

У нас числа 9 и 1 обязательные, поэтому разбиваем функцию следующим образом F(2, 9)*F(9, 11)*F(11, 12), через умножение. Это и будет ответ. Получается 50.

2 способ (с помощью таблицы).

От числа 11 до числа 12 можно добраться единственным путём (11 + 1 = 12).

От числа 9 до числа 11 можно добраться двумя способами (9 + 1 + 1 = 11, 9 + 2 = 11).

Найдём сколькими способами можно попасть от числа 2 до числа 9.

Учитывая, что от 9 до 11 двумя способами можно добраться, то 25 * 2 = 50 — это и будет ответ.

Ответ: 50

Задача ( ЕГЭ по информатике, Москва, 2020)

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

1. Прибавить 1
2. Умножить на 3
3. Прибавить 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 3, третья увеличивает на 2.

Сколько существует программ, которые преобразуют исходное число 3 в число 14 и при этом траектория вычислений содержит число 9?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y: return 0

    if x < y: return F(x+1, y) + F(x*3, y) + F(x+2, y)

print(F(3, 9)*F(9, 14))

Ответ получается 112.

2 способ (с помощью таблицы).

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

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

Получается, что мы будем использовать основной принцип 23 задания из ЕГЭ по информатике: результат для некоторого числа опирается на результаты предыдущих чисел. Т.к. траектория вычислений программ обязательно должна проходить через число 9, то при вычислении результата для чисел больших 9, мы не можем опираться на результаты для чисел меньших 9 (Иначе мы пропустим число 9).

Ответ: 112

Посмотрим следующую задачу из 23 задания ЕГЭ по информатике 2023

Задача (с обязательным узлом, закрепление)

Исполнитель Май17 преобразует число на экране.

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

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

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3. Программа для исполнителя Май17 — это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 17 и при этом траектория вычислений содержит число 9?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 12 при исходном числе 7 траектория будет состоять из чисел 8, 11, 12.

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y: return 0

    if x < y: return F(x+1, y) + F(x+3, y)

print(F(1, 9)*F(9, 17))

Ответ получается 169.

2 способ (с помощью таблицы).

Любое число может получится в результате двух команд! Тогда количество программ для числа i будет складываться из количеств команд для числа i — 1 и для числа i — 3.

Если написать на языке массива

A[i] := A[i-1] + A[i-3], при i > 3.

При составлении значения для числа 10, мы не имеем право «заглядывать» за число 9, иначе число 9 будет пропущено! Поэтому для следующих трёх чисел (9, 9 + 1, 9 + 1 + 1), начиная с 9, будет 13 программ.

Для числа 17 получается ответ 169.

Ответ: 169

Пройти тестирование по этим заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word

Пройти тестирование по этим заданиям

Задание 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 (по числу обведённых в кружочек конечных результатов).

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

Итого 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 в ЕГЭ по информатике и овладеть такими понятиями, как рекурсия, динамическое программирование, дерево вариантов.

Хотите готовиться со мной к ЕГЭ?
Пишите:  ydkras@mail.ru
Немного обо мне.

В задаче 23 ЕГЭ по информатике описывается исполнитель, который может выполнять несколько команд (чаще всего две), например, прибавить 1 или прибавить 3. Требуется найти количество программ, которые преобразуют одно число (исходное) в другое (цель). Например, из числа 2 нужно получить число 15, используя две описанные выше команды.

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

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

Заметим, что каждая команда увеличивает число. Поэтому если команда дает результат, превышающий целевое число, то в дальнейшем мы никогда не получим целевого числа. Если текущее число равно целевому, то мы, очевидно, достигли цели.

Наша рекурсивная функция на языке Питон может выглядеть, например, так:

def ways(n, goal):
    if n>goal: return 0
    if n==goal: return 1
    return ways(n+1,goal)+ways(n+3,goal)

Таким образом, задача решена с помошью всего лишь пяти строк кода на Питоне.

Если команды исполнителя не увеличивают число, а уменьшают его, то нужно изменить операцию сравнения: вместо «больше» написать «меньше». Так, для задачи получения числа 2 из числа 22 с помощью операций «вычти 2» и «вычти 5» можно написать такую программу:

Программы с обязательным этапом

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

Программа для решений этой задачи может выглядеть так:

Программы с избегаемым этапом

Если нам запрещают получать в ходе вычислений какое-то число, то нашу функцию придется немного изменить: она должна возвращать 0 для «запрещенных» чисел.

Пример задачи — получить из числа 3 число 13, причем разрешается использовать две операции: «прибавь 1» и «прибавь 2», а в процессе вычислений не должно получаться числа 8.

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

Вот программа, решающая данную задачу:

Так как в нашем случае «запрещенное» число всего одно, то в функцию передается массив, состоящий из одного элемента.

Крест-накрест: обязательный этап вместо избегаемого и наоборот

Вначале — очень простая мысль: общее число программ — это сумма числа программ, треактория вычислений которых проходит через некое число, и числа программ, траектория которых через это число не проходит.

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

Так, рассмотренную в разделе «Программы с обязательным этапом» задачу можно решить так:

(Когда у нас нет «запрещенных» чисел, тогда в функцию передается пустой массив.)

Мы решили задачу двумя способами: рассмотренным ранее перемножением числа вариантов первого этапа (3-10) и числа вариантов второго  этапа (10-12), а также вычитанием из общего числа программ числа тех программ, траектория которых не содержит числа 10. В обоих случаях получается одинаковый результат (как и следовало ожидать).

Аналогичным образом можно решить задачу на запрещенный этап, используя метод обязательного этапа:

Эта идея позволяет легко решать задачи вроде следующей: получить из числа 11 число 29, пользуясь операциями «прибавь 1» и «прибавь 2», причем траектория вычислений должна содержать либо число 17, либо число 23, либо оба этих числа одновременно.  

Решение можно найти, если из общего числа программ вычесть число таких программ, траектория которых не содержит ни числа 17, ни числа 23:

Программы с обязательным и избегаемым этапами

Часто встречаются задачи,  в которых сочетаются обязательный и избегаемый этап. Например, требуется получить из числа 2 число 29, при этом разрешены операции «прибавить 1» и «умножить на 2», а траектория вычислений должна содержать число 14 и не должна содержать числа 25.

 Эту задачу можно решить двумя способами. Можно подсчитать число способов получить из числа 2 число 14, а из числа 14 — число 29 и перемножить эти числа (разумеется, нужно учитывать запрет на число 25). Можно также подсчитать число способов получить из числа 2 число 29 с запретом на число  25, а затем вычесть из него количество программ, которые не проходят ни через число 14, ни через число 25 — так мы получим количество программ, которые не проходят число 25, но обязательно пройдут через число 14.

Оба эти способа иллюстрирует такая программа:

В некоторых задачах число обязательных и/или избегаемых этапов более одного. Рассмотрим задачу, в которой траектория вычислений должна содержать число 8 и не должна содержать чисел 10 и 11, в ней требуется из числа 1 получить число 28, а используемые операции — «прибавь 1», «прибавь 2» и «умножь на три».

Задача решается следующей программой (в ней опять-таки показаны два возможных способа решения):

Если количество «обязательных» чисел более одного, то нам надо разбить путь не на два этапа, а более. Например, в одной из задач нужно получить из числа 2 число 15, пользуясь операциями «прибавь 1», «прибавь 2» и «умножь на три», а траектория вычислений должна содержать числа 4 и 11.

Разбиваем путь на три этапа: 2-4, 4-11, 11-15. Программа для решения жтой задачи следующая:

Ограничение на число команд программы или требования к командам

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

Имеются две операции:

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

Сколько существует программ, для которых при исходном числе 4 результатом является число 14, а предпоследней командой которых является команда «1»?

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

Добавим в нашу рекурсивную функцию ways дополнительный параметр prog: строку, содержащую цепочку команд, выполненных прелылущими операциями. При выполнении операции 1 будем приписывать к  этой строке цифру 1, а при выполнении операции 2 — цифру 2. Когда цель будет достигнута, проверим, что предпоследний символ нашей строки равен 1. (Напомним, что в Питоне s[-1] — это последний символ строки, s[-2] — предпоследний и т.д.) Если это не так, то не учитываем такое решение.

При вызове этой функции из основной программы в качестве параметра prog задаем пустую строку.

Вот программа целиком:

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

Допустимые операции исполнителя следующие:

1. Прибавить 1
2. Прибавить 4
3. Умножить на 2

Требуется получить из числа 3 число 27, причем программа должна содержать ровно 7 команд.

Можно было бы передавать при вызовах строку команд, как в предыдущем примере, и при достижении цели проверять её длину. Но так как нам требуется лишь число команд, то можно использовать целую переменную, которую будем увеличивать на единицу при последующий вызовах. При достижении цели проверим, равно ли число команд требуемому. Если это условие выполнено, функция вернет 1, в противном случае — 0.

Приведем программу, решающую эту задачу:

Количество результатов программы, состоящей из определенного числа команд

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

Задачу можно решить методом «грубой силы» — выполнив все возможные программы, состоящие из требуемого числа команд, и подсчитав количество полученных результатов. 

Количество всех программ сравнительно велико. Так, если допустимо n команд, а длина программы — k команд, то число всех возможных программ — это n**k (операция ** — это возведение в степень).

Рассмотрим конкретную задачу. Пусть у исполнителя есть две допустимые команды: «прибавить 1» и «умножить на 2 и вычесть 3».  Требуется начать с числа 3 и подсчитать количество различных результатов, которые дадут все программы, состоящие ровно из 12 команд.

Вначале решим задачу без применения рекурсии. Первый этап — генерация всех возможных программ для исполнителя.  Программа — это строка символов, в которых символ «0» обозначает первую команду, а «1» — вторую. Такую строку можно получить, перебрав все числа от  0 до 2**12-1 и преобразовав эти числа в двоичную запись. Это делается следующим фрагментом программы:

k=12
for i in range(2**k):
    prog=bin(i)[2:]
    if len(prog)<k: prog=’0’*(k-len(prog)) + prog 

Выражение  bin(i)[2:] работает так: функция bin(i) преобразует целое число в его двоичное представление, которое начинается с символов «0b». Чтобы отрезать эти символы, используем операцию выделения подстроки [2:], которая удалаяет первые два символа. Если длина нашей строки prog менее k, мы приписываем к ней слева такое количество нулей, чтобы её длина было ровно k символов. 

Теперь выполним полученную программу. Выбираем из строки символы по очереди. Если символ — «0», то выполняем операцию «прибавить 1», в противном случае — операцию «умножить на 2 и вычесть 3». Соответствующий фрагмент программы вышлядит так:

    n=start
    for j in range(k):
        if prog[j]==’0′: n += 1
        else: n=2*n-3 

После завешения этого цивла переменная n будет содержать результат выполнения текущей программы из k команд.

Чтобы полсчитать число различных резудьтатов, будем использовать массив a (изначально пустой). Если данное число не содержится в нём — добавим это число в массив:

    if not n in a: a.append(n) 

Когда закончится внешний цикл, то в массиве a будут содержаться все возможные результаты выполнения — под одному разу каждый. Всё, что осталось сделать — вывести количество элементов массива a:

print(len(a))

Приведем программу полностью:

k=12
start=3
a=[]
for i in range(2**k):
    prog=bin(i)[2:]
    if len(prog)<k: prog=’0’*(k-len(prog)) + prog
    n=start
    for j in range(k):
        if prog[j]==’0′: n += 1
        else: n=2*n-3
    if not n in a: a.append(n)
print(len(a))

Теперь решим ту же самую задачу с использованием рекурсии. Для этого напишем рекурсивную функцию f:

def f(n,l,k):
    if l==k:
        if not n in a: a.append(n)
        return
    f(n+1,l+1,k)
    f(2*n-3,l+1,k)
    return

Параметры функции следующие: n — текущее число, с которым работает исполнитель, l — текущее число команд, k — длина программ, которые требуется выполнять.

Если l равно k, это означает, что мы выполнили программу из k команд. Проверяем, содержится ли данный результат в массиве a, если нет — добавляем его в массив. После этого выходим из программы.

Если же требуемое количество команд ещё не выполнено, вызываем функцию два раза, первый — увеличив значение n на 1, второй — со значением 2*n-3. В обоих случаях увеличиваем l на 1, т.к. мы выполнили ещё одну команду.

Основная программа очень короткая: в ней переменной a присваивается пустой массив, вызывается функция f с параметром l, равным 0 (мы её не выполнили ни одноё команды), а после её завершения печатается количество элементов в массиве a.

Вот программа полностью:

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

Некоторые «хитрые» операции

В ряде задач встречаются «хитрые» операции получения следующего числа. Рассмотрим некоторые из них.

«Сделай нечётное». Если число чётное, к нему прибавляется 1, а если чётное,  то 2. Результат достигается с помощью выражения n+n%2+1. 

«Дописать справа 0» и «дописать справа 1». К десятичной записи числа справа приписывается ноль или единица. Такой результат дают выражения 10*n и 10*n+1 соответственно.

«Прибавить предыдущее» и «прибавить следующее». В первом случае к числу прибавляется число, меньшее на 1 (так, из числа 5 получается число 5+4, т.е. 9), во втором — на единицу большее. Соответствующие выражения — 2*n-1 и 2*n+1.

«Обнулить младший разряд». Операция обнуляет младший разряд в троичной записи числа. Соответствующее выражение — (n//3)*3. Внимание, тут есть подвох! Если последняя цифра числа в троичной записи — ноль (например, число 6 в троичной записи выглядит как 20), то число не изменяется и рекурсия зациклится. Поэтому надо проверять эту ситуацию и в случае, когда последняя цифра — ноль, не вызывать функцию. Для операций «отнять 2» и «обнулить младший разряд» функция ways может выглядеть так:

def ways(n, goal, zapret):
    if n<goal: return 0
    if n in zapret: return 0
    if n==goal: return 1
    if n%3==0: return ways(n-2,goal,zapret)
    else: return ways(n-2,goal,zapret)+ways((n//3)*3,goal,zapret)

(Обратите внимание: так как операции уменьшают число, то во второй строке функции используется операция сравнения «меньше», а не «больше».)

«Добавить слева 1». Операция приписывает к двоичной записи числа единицу слева. Это можно сделать, например, с помощью выражения int(‘1’+bin(n)[2:],2).

«Убрать последнюю цифру справа». Удаляется последняя цифра справа в десятичной записи числа. Это можно сделать целочисленным делением на 10: n//10. 

«Обнулить». Первая слева цифра числа в двоичной записи не изменяется, а остальные заменяются нулями.  Возможное выражение — n-int(bin(n)[3:],2). Тут тоже возможны неприятности, аналогичные упомянутым в операции «обнулить младший разряд» (см. выше).

«Прибавить следующее четное». К числу прибавляется минимальное четное число, превосходящее данное. Так, к числу 2 прибавляется 4, а к числу 5 — 6. Это можно сделать при помощи выражения 2*n+1+(n+1)%2.

«Сделать простое». Требуется получить простое число, большее, чем данное, и ближайшее в нему. Так, для числа 8 результатом должно быть число 11. Тут придется написать функцию, которая будет последовательно перебирать числа n+1, n+2 и т.д., пока не найдет простое число. Функция может выглядеть, например, так:

def makeprime(n):
    n += 1
    while True:
        k=2
        prime=True
        while k*k<=n:
            if n%k==0:
                prime=False
                break
            k += 1
        if prime: return n
        n += 1 

(О простых числах и способах проверки «на простоту» я писал ранее.)

Задачи ЕГЭ 23 и 13 — по сути одна задача

Данная задача является подсчетом числа путей в ориентированном графе. Вершинами графа являются числа, а правила перехода от одного числа к другому задаются разрешенными в задаче операциями. Поэтому данная задача аналогична задаче  ЕГЭ № 13, в которой рисуется схема дорог между городами и задается вопрос вроде: «Сколько существует различных путей из города А в город Н?» 

Возникает вопрос: а можно ли решать программным путем и задачу 13? Разумеется, можно! Самая большая сложность — представить граф из задачи 13 в форме, удобной для компьютерной обработки. Впрочем, сложность эта вполне преодолима. Но более подробный рассказ об этом — тема для отдельной заметки.

Использованные выше задачи взяты с сайта «Решу ЕГЭ» (информатика) и с сайта К.Ю.Полякова.

(c) Ю.Д.Красильников, 2022 г.

За это задание ты можешь получить 1 балл. На решение дается около 10 минут. Уровень сложности: высокий.
Средний процент выполнения: 25.4%
Ответом к заданию 23 по информатике может быть цифра (число) или слово.

Задачи для практики

#include <iostream>
using namespace std;
int main(){
    const int n0 = 1, nk = 33;
    int arr[nk + 1];
    for (int i = 0; i < nk + 1; ++i) arr[i] = 0;
    arr[n0] = 1;
    for (int n = n0 + 1; n <= nk; ++n) {
        arr[n] = arr[n - 1]; // Kn-1
        if (n % 2 != 0 && (n - 1) / 2 >= n0) //K(n - 1)/2
            arr[n] += arr[(n - 1) / 2];
        if (n % 2 != 0 && (n + 1) / 2 >= n0) //K(n + 1)/2
            arr[n] += arr[(n + 1) / 2];
        if (n == 7 || n == 14)
            arr[n] = 0;
        if (n == 12)
            for (int i = n - 1; i >=0 ; --i)
                arr[i] = 0;
    }
    cout << arr[nk];
    return 0;
}

#include <iostream>
using namespace std;
int main(){
    const int n0 = 2, nk = 30;
    int arr[nk + 1];
    for (int i = 0; i < nk + 1; ++i) arr[i] = 0;
    arr[n0] = 1;
    for (int n = n0 + 1; n <= nk; ++n) {
        arr[n] = arr[n - 1]; // Kn-1
        if (n % 2 != 0 && (n - 1) / 2 >= n0) //K(n - 1)/2 - сделай нечётное
            arr[n] += arr[(n - 1) / 2];
        if (n % 2 == 0 && n / 2 >= n0) //Kn/2 - сделай чётное
            arr[n] += arr[n / 2];
        if (n == 16)
            arr[n] = 0;
        if (n == 9)
            for (int i = n - 1; i >=0 ; --i)
                arr[i] = 0;
    }
    cout << arr[nk];
    return 0;
}

Еще один способ решения данного задания – написание программы.

На примере первой задачи посмотрим несколько способов решения.

Задание 1

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

1. прибавь 1

2. умножь на 3

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

В решении электронными таблицами мы получили формулы для расчетов:

Если число n НЕ делится на 3, количество программ для него

kn = kn-1

Если же число делится на 3, то

kn = kn-1 + kn / 3

их мы и будем использовать в данном задании.

1 способ решения. Заполнение списка.

Необходимые навыки:

• работа со списками
• условный оператор
• цикл for

# +1 *3 1->20

a = [0] * 21 # создаем список из такого количества

# элементов, чтобы нам хватило индексов от 0 до 20

a[1] = 1 # заполняем элемент с индексом стартового числа

for i in range(2, 20 + 1): # перебираем остальные числа от 2 до 20

if i % 3 == 0: # если кратно 3, добавляем предыдущее и / 3

a[i] = a[i – 1] + a[ i // 3]

else: # если не кратно 3, добавляем только предыдущее

a[i] = a[i – 1]

print(a[20]) # выводим на экран значение конечного числа

Данное решение является самым частным и не всегда получится им хорошо решить. Потребуются дополнительные условия когда могут получаться отрицательные индексы.

2 вариант решения без инверсии команд

# +1 *3 1->20
a = [0] * 100 # создаем список из такого количества 
# элементов, чтобы нам хватило индексов от 0 до 20 * 3 (я взял сильно с запасом)
a[20] = 1 # заполняем элемент с индексом стартового числа
for i in range(19, 0, -1): # перебираем остальные числа от 2 до 20
	a[i] = a[i + 1] + a[i * 3]
print(a[1]) # выводим на экран значение конечного числа

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

3 вариант решения. Рекурсивная функция

# +1 *3 1->20
def f(n):
	if n > 20: # перепрыгнули 20
		return 0
	if n == 20: # попали в 20
		return 1
	return f(n + 1) + f(n * 3) # число до 20
	


print(f(1))

Задача 2. Все варианты решения

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

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

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

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 40 и при этом траектория вычислений содержит число 20 и не содержит число 8?

Разобьем решение со списком на два этапа

# +1 *2 2->40 v20 x8
a = [0] * 100 

a[20] = 1 # заполняем элемент с индексом стартового числа
a[40] = 1
for i in range(19, 2 - 1, -1): 
	if i != 8:
		a[i] = a[i + 1] + a[i * 2]
for i in range(39, 20 - 1, -1):
	a[i] = a[i + 1] + a[i * 2]
print(a[2] * a[20]) # выводим на экран значение конечного числа

Усовершенствуем рекурсивный алгоритм: добавим в функцию еще один параметр. Теперь их два: из какого числа считаем и в какое.

# +1 *2 2->40 v20 x8
def f(n, finish):
	if n == finish:
		return 1
	if n > finish or n == 8:
		return 0
	return f(n + 1, finish) + f(n * 2, finish)
	
	
print(f(2, 20) * f(20, 40))

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

Следует рассматривать такой вариант решения как средство для проверки ручного решения.