В этой статье разберёмся, как написать рекурсивную программу для решения задания №23 из ЕГЭ по информатике.
Термины, которые будем использовать: рекурсия, базовый случай.
Вспомним, что рекурсия — это функция, которая вызывает саму себя. Значит в нашем алгоритме будут присутствовать рекурсивное нахождение ответа и базовые случаи.
Практикум: решение задач
Задание 1
У исполнителя Flash25 две команды, которым присвоены номера:
- прибавь 2;
- умножь на 2.
Сколько есть программ, которые число 1 преобразуют в число 10?
Пусть x — это число, из которого мы идём посредством доступных ходов, а y — конечная точка маршрута.
Тогда, так как все ходы увеличивают текущее число, справедливым будет ввести базовый случай, при котором x > y, то есть достигнуть y в таком случае будет невозможно.
Если число x окажется больше, чем y, то тогда мы точно не сможем вернуться в это число y, поэтому возвращаем 0 (на схеме это отображается красными стрелочками).
Введём второй базовый случай, при котором x == y.
Если x == y, то существует только 1 способ, как дойти в эту точку (она вернётся сама в себя).
В остальных случаях мы рекурсией будем запоминать количество вариантов того, в какие точки мы сможем попасть, выполняя наши действия с числом x.
def f(x, y):
if x > y:
return 0
if x == y:
return 1
return f(x + 2, y) + f(x · 2, y)
print(f(1, 10))
такие программы стандартные и есть на многих сайтах
Ответ: 6.
Рассмотрим рекурсивные вызовы подробно:
f(1, 10) = f(3, 10) + f(2, 10)
f(3, 10) = f(5, 10) + f(6, 10)
f(5, 10) = f(7, 10) + f(10, 10)
f(7, 10) = f(9, 10) + f(14, 10)
f(9, 10) = f(11, 10) + f(18, 10)
f(11, 10): 11 > 10 return 0
f(18, 10): 18 > 10 return 0
f(9, 10) = 0 + 0 = 0
f(14, 10): 14 > 10 return 0
f(7, 10) = 0 + 0 = 0
f(10, 10): x == y return 1
f(5, 10) = 0 + 1 = 1
f(6, 10) = f(8, 10) + f(12, 10)
f(8, 10) = f(10, 10) + f(16, 10)
f(10, 10) = 1
f(16, 10) = 0
f(8, 10) = 1 + 0 = 1
f(12, 10): 12 > 10 return 0
f(6, 10) = 1 + 0 = 1
f(3, 10) = f(5, 10) + f(6, 10) = 1 + 1 = 2
f(2, 10) = f(4, 10) + f(4, 10) # потому что 2·2 = 4, 2+2 = 4
f(4, 10) = f(6, 10) + f(8, 10) = 1 + 1 = 2
f(2, 10) = f(4, 10) + f(4, 10) = 2 + 2 = 4
f(1, 10) = f(3, 10) + f(2, 10) = 2 + 4 = 6
Задание 2
Исполнитель Flash25 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
- Прибавить 1.
- Прибавить 3.
Программа для исполнителя Flash25 — это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 20 и при этом траектория вычислений содержит число 15?
Раз программа содержит число 15, то оно обязательно должно быть в ней. Более того, любой путь должен проходить через это число.
Рассмотрим на примере: допустим, из числа 3 в число 15 у нас есть четыре разных пути, а из числа 15 в число 18 будет три разных пути. Тогда, чтобы из числа 3 попасть в 18, обязательно проходя через число 15, у нас есть 4 · 3 = 12 вариантов. Отобразим это замечание в программе:
def f(x, y):
if x > y:
return 0
if x == y:
return 1
return f(x + 1, y) + f(x + 3, y)
print(f(3, 15) · f(15, 20))
такие программы стандартные и есть на многих сайтах
Ответ: 240.
Мы посчитали, сколько путей идёт в число 15 и сколько путей идёт из 15 в 20, сами значения перемножили, так как на каждый путь до 15 приходится любой путь после 15.
Задание 3
Исполнитель Flash25 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
- Вычти 1.
- Найди целую часть от деления на 2.
Первая из них уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2. Программа для исполнителя Flash25 — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 20 в число 2?
Здесь нам впервые встречается вычитание, рассмотрим условия:
- В этот раз программа вернёт 0, если число x изначально меньше числа y, так как из-за этого мы никогда не сможем прийти в число y.
- Если x == y, мы продолжаем возвращать единичку.
def f(x, y):
if x < y:
return 0
if x == y:
return 1
return f(x – 1, y) + f(x // 2, y)
print(f(20, 2))
такие программы стандартные и есть на многих сайтах
Ответ: 77.
Заключение
Мы разобрали три типовых задания на рекурсию: от простого сложения и умножения до вычитания с делением. Теперь ты сможешь решать 23-й номер на ЕГЭ — просто аккуратно прописывай рекурсию и проверяй границы переходов. Удачи!
Автор статьи
