Почему перемножают, а не складывают?

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

Что если команда уменьшает число?

Тогда условие a > b уже не останавливает перебор. Ограничьте траекторию по смыслу задачи или считайте динамикой.

Входит ли исходное число в траекторию?

Обычно нет: траектория — это результаты команд. Проверьте определение в условии.

Задание 23 ЕГЭ по информатике: решайте с автопроверкой

В задании 23 у исполнителя две или три команды, например «прибавить 1» и «умножить на 2». Нужно посчитать программы, которые переводят одно число в другое, иногда с условием: траектория проходит через одни числа и обходит другие.

Решать задачи номера

Как решать программой

Количество программ из a в b считает рекурсивная функция: если a больше b, программ нет; если a равно b, программа одна (пустая); иначе сложите количества программ после каждой команды.

Обязательное число c делит путь на два отрезка: число программ равно произведению количеств из a в c и из c в b. Запрещённое число просто даёт ноль, если траектория в него попала.

Для больших чисел добавьте @lru_cache или посчитайте количества циклом от a к b в списке. Для команд из примера (+1, +2, ×2) cnt[x] прибавляется к cnt[x + 1], cnt[x + 2] и cnt[2x].

Проверьте функцию на маленьком отрезке, где программы легко выписать руками. Например, с командами из примера из 3 в 5 ведут две программы: «1, 1» и «2».

Разбор примера

Команды: прибавить 1, прибавить 2, умножить на 2. Сколько программ переводят 3 в 25 через 10 и не проходят через 17?

def count(a, b, avoid):
    if a > b or a in avoid:
        return 0
    if a == b:
        return 1
    return (count(a + 1, b, avoid) + count(a + 2, b, avoid)
            + count(a * 2, b, avoid))

print(count(3, 10, {17}) * count(10, 25, {17}))

Программа печатает

Из 3 в 10 ведут 30 программ, из 10 в 25 в обход 17 ведут 286 программ. Каждую первую часть можно продолжить любой второй, поэтому всего 30 · 286 = 8580 программ.

Решить эту задачу

Задачи к заданию 23

Три команды и обязательные числаСредняяРешать
Хотя бы одна отметка на траекторииСредняяРешать
Обратный отсчёт с делением пополамСредняяРешать
Прибавить или возвести в квадратСредняяРешать
Прибавить последнюю цифруСредняяРешать
Сколько разных результатов у программСредняяРешать
Без двух одинаковых команд подрядСредняяРешать
Не больше m умножений в программеСредняяРешать
Траектория без кратных dСредняяРешать
Ровно одно отмеченное числоСредняяРешать

Бесплатно и без регистрации: пишете код в браузере и проверяете его тестами (без аккаунта — несколько задач в день).

Вопросы и ответы

Почему перемножают, а не складывают?: Каждую программу до обязательного числа можно продолжить любой программой после него. Пары считаются произведением.
Что если команда уменьшает число?: Тогда условие a > b уже не останавливает перебор. Ограничьте траекторию по смыслу задачи или считайте динамикой.
Входит ли исходное число в траекторию?: Обычно нет: траектория — это результаты команд. Проверьте определение в условии.