Question

Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 3 Сколько существует программ, для которых при исходном числе 3 результатом является число 20 и при этом траектория вычислений содержит число 15 и не содержит число 10?

Answer 1

Заполняем таблицу:

Число -> Источники (из каких чисел можно получить текущее) -> Количество способов получения числа.

Число 3 можно получить только одним способом из числа 3 с помощью "пустой" программы.

Число 4 - из числа 3 (1 способ)

Число 5- из числа 4 (1 способ)

Число 6 - из числа 3 (1 способ) и из числа 5 (1 способ). Всего 1+1=2 способа

Число 7 - из числа 4 (1 способ) и из числа 6 (2 способа). Всего 1+2=3 способа

Некоторые варианты выбрасываем:

Число 11 - только из числа 8 (4 способов)

Число 13 - только из числа 12 (10 способов)

Выбрасываем также варианты, которые проходят "мимо" числа 15, например 12-13-16 или 13-14-17

Итого получаем 96 способов для числа 20 (см.таблицу)

Answer 2

Для решения этой задачи можно использовать рекурсивный подход, перебирая все возможные комбинации команд до достижения числа 20, с учетом условий, что траектория вычислений содержит число 15 и не содержит число 10. Давайте начнем:

Пусть функция F(n, target) будет возвращать количество программ, которые приводят к числу target, начиная с числа n.

F(n, target) = F(n+1, target) + F(n+3, target)

Для чисел, меньших 15, программа не должна содержать число 10, иначе мы просто исключим эти варианты.

Теперь давайте рассмотрим базовые случаи:

1. Если n > target, то программа не сможет достичь числа target, поэтому F(n, target) = 0.
2. Если n == target, то программа состоит из одной команды "Прибавить 1", поэтому F(n, target) = 1.
3. Если n == 15, то нам нужно обработать вариант, где мы не будем использовать команду "Прибавить 3" (иначе мы достигнем числа 18, а потом 21 и так далее, что приведет к 20, но не позволит избежать числа 15). Таким образом, F(15, target) = F(16, target) + F(18, target) + ... + F(20, target).

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

pythonCopy code
def count_programs(n, target):
    if n > target:
        return 0
    if n == target:
        return 1
    if n == 15:
        # Если текущее число равно 15, рассмотрим все возможные пути
        # без использования команды "Прибавить 3".
        return (
            count_programs(n + 1, target)
            + count_programs(n + 3, target)
            + count_programs(n + 4, target)
            + count_programs(n + 5, target)
            + count_programs(n + 6, target)
        )
    # Все остальные случаи, где текущее число не является 15,
    # будут использовать обе команды.
    return count_programs(n + 1, target) + count_programs(n + 3, target)

# Проверим результат для исходного числа 3 и целевого числа 20.
start_number = 3
target_number = 20
result = count_programs(start_number, target_number)
print(result)

Запустив код, вы получите количество программ, которые приводят к числу 20 при исходном числе 3 и удовлетворяют условиям с траекторией через 15 и без числа 10.