Задание 13 ЕГЭ по информатике: число программ

Идея

Число программ, которые приводят в число n, равно сумме программ, которые приводят во все числа, из которых в n можно попасть одной командой. Для команд +1 и ×2: f(n) = f(n − 1) + f(n / 2), второе слагаемое только для чётных n. Начальное значение f(1) = 1.

Таблица для 1 → 20

Для нечётных n значение равно предыдущему: f(3) = 2, f(5) = 4 и так далее. Получаем f(20) = 60.

Разбор задач

Рекурсия на Python

def f(a, b): if a > b: return 0 if a == b: return 1 return f(a + 1, b) + f(a * 2, b) print(f(1, 20)) print(f(1, 10) * f(10, 20))

Запрещённую точку проверяют условием «if a == запрещённое: return 0». Для больших чисел добавьте from functools import lru_cache и декоратор @lru_cache над функцией.

Проверь себя

• Сколько программ переводят 1 в 8? Ответ: 10.
• Сколько программ переводят 1 в 12, не проходя через 6? Ответ: 8 (из 20 вычитаем 6·2 программ через 6).

Где теряют балл

• Обязательная точка сложением. Пути через точку перемножаются, а не складываются.
• Нечётные числа. У нечётного n нет слагаемого f(n/2).

Как тренироваться

Та же идея сложения путей используется в новом задании 23 на графы: задание 23 на графы. Все номера экзамена в статье ЕГЭ по информатике по номерам.

Частые вопросы