23.03 Количество программ из A в B где траектория вычислений содержит число(-а) - Каталог заданий по ЕГЭ

Ошибка.
Попробуйте повторить позже

Задача 21#52532Максимум баллов за задание: 1

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

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

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

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

Программа для исполнителя Калькулятор – это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 13, и при этом траектория вычислений содержит числа 9 и 11?

Показать ответ и решение

Решение рекурсией

Мы будем использовать рекурсивный подход, создавая функцию f(x, y), которая подсчитывает количество способов из числа $x$ получить число $y$ . Основная идея заключается в том, что мы рассматриваем все возможные последовательности команд и суммируем количество корректных программ. Для реализации мы разбиваем задачу на три этапа: из 3 в 9, из 9 в 11, из 11 в 13. Для каждого этапа функция работает одинаково:

- Если текущее число $x$ совпало с целевым $y$ , значит мы нашли один корректный путь, возвращаем 1.

- Если текущее число $x$ стало больше $y$ , значит дальнейшие действия не приводят к результату, возвращаем 0.

- Иначе мы рекурсивно вызываем функцию для всех трех команд:

Прибавить 1: f(x + 1, y)

Прибавить 2: f(x + 2, y)

Умножить на 2: f(x * 2, y)

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

# Определяем функцию f(x, y), которая считает количество программ
def f(x, y):
    # Если текущее число равно целевому, найден один путь
    if x == y:
        return 1
    # Если текущее число превысило целевое, путь невозможен
    if x > y:
        return 0
    # В остальных случаях считаем все возможные варианты:
    # прибавить 1, прибавить 2, умножить на 2
    return f(x + 1, y) + f(x + 2, y) + f(x * 2, y)

# Перемножаем количество программ для каждого этапа,
# чтобы учесть обязательное прохождение чисел 9 и 11
print(f(3, 9) * f(9, 11) * f(11, 13))

—

Решение динамикой

Мы также можем посчитать количество программ с помощью динамического программирования. Для этого создаем массив a длиной достаточной, чтобы включить все числа до 13. Элементы массива будут хранить количество программ, приводящих к каждому числу. Мы идем по массиву от исходного числа 3 к 13, учитывая команды:

- Для каждого числа $i$ , начиная с 4 до 13:

- Добавляем количество программ для $i− 1$ , так как можно прийти командой "прибавить 1"

- Добавляем количество программ для $i− 2$ , так как можно прийти командой "прибавить 2"

- Если $i$ четное, добавляем количество программ для $i∕∕2$ , так как можно прийти командой "умножить на 2"

Чтобы учесть обязательное прохождение чисел 9 и 11, мы после вычисления этих чисел обнуляем все предыдущие значения массива, так как пути, которые их не достигли, не подходят. В конце значение $a[13]$ покажет общее количество корректных программ.

# Создаем массив для хранения количества программ для чисел до 100
a = [0] * 100
# В начальное число 3 записываем 1, только один способ быть в исходном положении
a[3] = 1

# Проходим числа от 4 до 13
for i in range(4, 14):
    # Суммируем количество программ из предыдущих чисел,
    # учитывая команды прибавить 1, прибавить 2 и умножить на 2
    a[i] = a[i - 1] + a[i - 2] + a[i // 2] * (i % 2 == 0)
    # Если число равно 9 или 11, обнуляем все предыдущие значения,
    # чтобы пути обязательно проходили через это число
    if i == 9 or i == 11:
        for j in range(i):
            a[j] = 0

# Выводим количество программ, приводящих от 3 к 13 с обязательным прохождением 9 и 11
print(a[13])

Ответ: 68

Ошибка.
Попробуйте повторить позже

Задача 22#53444Максимум баллов за задание: 1

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

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

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

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

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

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

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

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 6 траектория будет состоять из чисел 9, 10, 20.

Показать ответ и решение

Решение рекурсией

Идея рекурсивного решения заключается в том, что мы создаём функцию, которая подсчитывает количество всех программ, преобразующих число $a$ в число $b$ . На каждом шаге функции проверяем три условия:

1. Если текущее число $a$ превысило $b$ , то дальнейшие действия невозможны, возвращаем 0.

2. Если текущее число $a$ совпало с целевым $b$ , то найден один корректный путь, возвращаем 1.

3. Если ни одно из условий не выполнено, мы вызываем функцию трижды: первый раз с $a + 1$ (команда "прибавить 1"), второй раз с $a∗ 2$ (команда "умножить на 2"), третий раз с $a+ 3$ (команда "прибавить 3"). Сумма этих вызовов даёт общее количество программ.

Чтобы учесть требование, что траектория должна содержать число 14, мы разбиваем задачу на два этапа: подсчёт программ от 2 до 14 и от 14 до 24. Результаты этих этапов перемножаются, так как любая программа из первой части может быть объединена с любой программой второй части.

# Определяем функцию f(a, b), которая считает количество программ
def f(a,b):
    # 1. Если текущее число больше целевого, путь невозможен
    if a > b:
        return 0
    # 2. Если текущее число совпало с целевым, найден путь
    if a == b:
        return 1
    # 3. В остальных случаях суммируем количество программ для всех трёх команд
    return f(a + 1, b) + f(a * 2, b) + f(a + 3, b)

# Вычисляем количество программ с учётом прохождения числа 14
print(f(2, 14) * f(14, 24))

—

Решение динамикой

Динамический способ решения заключается в том, что мы создаём массив, где индекс $i$ соответствует числу $i$ , а значение $a[i]$ хранит количество программ, которые преобразуют начальное число в $i$ .

1. Создаём массив длиной 25, заполняем нулями, так как числа от 0 до 24.

2. В ячейку $a[2]$ записываем 1, так как стартуем с числа 2.

3. Перебираем все числа $i$ от 3 до 24:

- Добавляем количество программ, ведущих в $i− 1$ (команда "прибавить 1").

- Добавляем количество программ, ведущих в $i− 3$ (команда "прибавить 3").

- Если $i$ делится на 2, добавляем количество программ, ведущих в $i∕∕2$ (команда "умножить на 2").

- Если $i$ равно 14, обнуляем все предыдущие элементы массива, чтобы учесть, что траектория должна содержать число 14.

После завершения цикла в $a[24]$ будет храниться количество программ, которые из числа 2 ведут к 24 и проходят через число 14.

# Создаем массив для подсчета программ
a = [0] * 25
# Начальное число 2, один способ быть в нём
a[2] = 1
# Перебираем числа от 3 до 24
for i in range(3, 25):
    # Считаем количество программ, ведущих в i
    a[i] = a[i - 1] + a[i - 3] + a[i // 2] * (i % 2 == 0)
    # Если достигли числа 14, обнуляем предыдущие элементы массива
    if i == 14:
        for j in range(i):
            a[j] = 0

# Выводим количество программ, ведущих от 2 до 24 с проходом через 14
print(a[24])

Ответ: 3752

Ошибка.
Попробуйте повторить позже

Задача 23#54936Максимум баллов за задание: 1

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

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

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

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

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

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

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

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

Показать ответ и решение

Решение рекурсией

Мы определяем функцию f(x, y), которая считает количество программ, преобразующих число $x$ в число $y$ . Внутри функции мы делаем три проверки:

1. Если текущее число $x$ совпадает с целевым числом $y$ , то значит мы достигли конца траектории, возвращаем $1$ , так как найден один корректный путь.

2. Если текущее число $x$ больше $y$ , то дальнейшие команды приведут только к превышению $y$ , поэтому возвращаем $0$ , так как такие пути не подходят.

3. Если ни одно из условий не выполнено, мы рекурсивно считаем все возможные пути из текущего числа: прибавляем 1, прибавляем 4, умножаем на 3, и суммируем количество полученных программ.

Так как траектория должна содержать число 18, мы делим вычисление на два этапа: сначала считаем все пути от 2 до 18, затем все пути от 18 до 35. Произведение этих двух значений даёт общее количество программ.

# Определяем рекурсивную функцию f(x, y), которая считает количество программ
def f(x, y):
    # Если текущее число совпало с целевым, возвращаем 1
    if x == y:
        return 1
    # Если текущее число больше целевого, возвращаем 0
    if x > y:
        return 0
    # Считаем все возможные варианты перехода:
    # прибавляем 1, прибавляем 4, умножаем на 3
    return f(x + 1, y) + f(x + 4, y) + f(x * 3, y)

# Вычисляем количество программ, сначала от 2 до 18, затем от 18 до 35,
# и перемножаем результаты, так как траектория должна проходить через 18
print(f(2, 18) * f(18, 35))

—

Решение динамикой

Мы создаём массив a размером 36 (чтобы индекс соответствовал числу от 0 до 35). Каждая ячейка массива будет хранить количество способов попасть в это число из числа 2, учитывая только допустимые команды.

1. Инициализируем массив нулями.

2. Устанавливаем a[2] = 1, так как начинаем с числа 2, существует один способ быть в этом положении.

3. Для каждого числа $i$ от 3 до 35 включительно:

- Считаем количество способов добраться до $i$ из $i− 1$ командой "прибавить 1".

- Добавляем количество способов из $i− 4$ командой "прибавить 4 если $i− 4 ≥ 0$ .

- Если $i$ делится на 3, добавляем количество способов из $i∕∕3$ командой "умножить на 3".

- Если $i$ равно 18, обнуляем все предыдущие ячейки массива, так как траектория должна содержать число 18, а пути до него больше не учитываем напрямую.

После заполнения массива, значение a[35] будет равно количеству программ, которые из числа 2 приводят к числу 35 и содержат число 18 в траектории.

# Создаем массив из 36 элементов, все значения изначально равны 0
a = [0] * 36
# Начинаем с числа 2, единственный способ быть в начале
a[2] = 1
# Проходим по всем числам от 3 до 35 включительно
for i in range(3, 36):
    # Добавляем количество способов, приходящих из i-1 (команда +1)
    # и из i-4 (команда +4)
    # и из i//3 (команда *3), только если i делится на 3
    a[i] = a[i - 1] + a[i - 4] + a[i // 3] * (i % 3 == 0)
    # Если достигли числа 18, обнуляем все предыдущие значения,
    # чтобы гарантировать, что траектория проходит через 18
    if i == 18:
        for j in range(i):
            a[j] = 0

# Выводим количество программ, которые из числа 2 приводят к числу 35 через 18
print(a[35])

Ответ: 18209

Ошибка.
Попробуйте повторить позже

Задача 24#56324Максимум баллов за задание: 1

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

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

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

2. Прибавить $4$ ,

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

Первая команда увеличивает число на экране на $1$ , вторая — на $4$ , третья — увеличивает число в $2$ раза. Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе $4$ результатом является число $27$ и при этом траектория содержит число $22$ ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $123$ при исходном числе $1$ траектория будет состоять из чисел $2$ , $6$ , $12$ .

Показать ответ и решение

Решение рекурсией

Мы решаем задачу рекурсивным методом. Сначала определяем функцию f(x, y), которая подсчитывает количество программ, преобразующих число $x$ в число $y$ .

1. Проверяем, достигли ли мы цели: если $x == y$ , значит путь завершён успешно, возвращаем $1$ .

2. Проверяем условие выхода за пределы: если $x > y$ , дальнейшие операции приведут к числу больше цели, возвращаем $0$ .

3. Если ни одно из условий не выполнено, рекурсивно вызываем функцию для всех трёх возможных команд:

- прибавление 1 (x + 1),

- прибавление 4 (x + 4),

- умножение на 2 (x * 2),

и суммируем результаты этих вызовов.

Так как траектория должна содержать число 22, мы разбиваем задачу на два этапа: подсчёт программ от 4 до 22 и от 22 до 27. Итоговое количество программ равно произведению результатов этих двух этапов, так как каждый путь до 22 может сочетаться с любым путём от 22 до 27.

# Определяем рекурсивную функцию для подсчета программ от x до y
def f(x, y):
    # Если дошли до цели, возвращаем 1
    if x == y:
        return 1
    # Если число превысило цель, путь невозможен, возвращаем 0
    if x > y:
        return 0
    # В остальных случаях считаем все возможные переходы
    return f(x + 1, y) + f(x + 4, y) + f(x * 2, y)

# Считаем количество программ от 4 до 22 и от 22 до 27, перемножаем результаты
print(f(4, 22) * f(22, 27))

—

Решение динамикой

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

1. Инициализируем массив нулями и ставим a[4] = 1, так как начинаем с числа 4, и существует один способ находиться на нём.

2. Перебираем числа от 5 до 27 включительно. Для каждого числа $i$ :

- добавляем количество программ, ведущих из $i− 1$ , для команды "прибавить 1

- добавляем количество программ, ведущих из $i− 4$ , для команды "прибавить 4

- если $i$ чётное, добавляем количество программ из $i∕∕2$ , для команды "умножить на 2".

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

После завершения цикла, значение a[27] содержит количество программ, удовлетворяющих условию.

# Создаем массив длиной 28, заполняем нулями
a = [0] * 28
# Начальное положение: только один способ быть в числе 4
a[4] = 1
# Перебираем числа от 5 до 27 включительно
for i in range(5, 28):
    # Суммируем количество программ, ведущих из i-1 и i-4
    # Для i четного добавляем путь из i//2
    a[i] = a[i - 1] + a[i - 4] + a[i // 2] * (i % 2 == 0)
    # Если достигли числа 22, обнуляем все предыдущие значения
    # чтобы учесть обязательное прохождение через 22
    if i == 22:
        for j in range(i):
            a[j] = 0

# Выводим количество программ, приводящих к числу 27 через 22
print(a[27])

Ответ: 933

Ошибка.
Попробуйте повторить позже

Задача 25#58499Максимум баллов за задание: 1

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

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

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

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

Программа для исполнителя РазДваТри – это последовательность команд. Сколько существует программ, для которых при исходном числе 4 результатом является число 31, и при этом траектория вычислений содержит число 18?

Показать ответ и решение

Решение рекурсией

Идея рекурсивного решения заключается в том, что мы определяем функцию f(x, y), которая считает количество способов преобразовать число $x$ в число $y$ . На каждом шаге мы проверяем следующие условия:

1. Если текущее число $x$ совпало с целевым числом $y$ , то мы нашли одну корректную программу, и функция возвращает 1.

2. Если текущее число $x$ стало больше $y$ , то дальнейшее применение команд приведет к числам, превышающим $y$ , и поэтому функция возвращает 0.

3. Если ни одно из этих условий не выполнено, мы пробуем все три команды рекурсивно:

- вызываем f(x+1, y), что соответствует команде "прибавить 1";

- вызываем f(x+2, y), что соответствует команде "прибавить 2";

- вызываем f(x*3, y), что соответствует команде "умножить на 3".

Чтобы учесть условие, что траектория должна содержать число 18, мы разбиваем задачу на два этапа: сначала считаем количество программ от 4 до 18, затем от 18 до 31. Итоговое количество программ равно произведению этих двух результатов, так как для каждой программы из первой части можно использовать любую программу из второй части.

# Определяем рекурсивную функцию f(x, y), которая считает количество программ
def f(x, y):
    # Если текущее число совпало с целевым, возвращаем 1
    if x == y:
        return 1
    # Если текущее число стало больше целевого, возвращаем 0
    if x > y:
        return 0
    # В остальных случаях считаем все возможные варианты:
    # прибавляем 1, прибавляем 2, умножаем на 3 и суммируем результаты
    return f(x + 1, y) + f(x + 2, y) + f(x * 3, y)

# Вычисляем количество программ для двух этапов и перемножаем
# Первый этап: от 4 до 18
# Второй этап: от 18 до 31
print(f(4, 18) * f(18, 31))

—

Решение динамикой

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

1. Инициализируем массив нулями, длина массива равна 32, так как максимальное число, до которого нужно дойти, — 31.

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

3. Проходим циклом по всем числам от 5 до 31 включительно:

- Для числа $i$ добавляем количество программ из $i − 1$ (команда "+1").

- Добавляем количество программ из $i− 2$ (команда "+2").

- Если $i$ делится на 3, добавляем количество программ из $i∕∕3$ (команда "*3").

4. Чтобы учесть, что траектория должна содержать число 18, после заполнения ячейки с индексом 18 мы обнуляем все предыдущие значения массива (индексы меньше 18). Это гарантирует, что все найденные программы обязательно проходят через число 18.

5. После завершения цикла ячейка с индексом 31 хранит количество программ, которые преобразуют 4 в 31 с обязательным прохождением числа 18.

# Создаем массив для чисел от 0 до 31, все элементы равны 0
a = [0] * 32
# Начальное число 4: существует один способ быть в этом состоянии
a[4] = 1
# Перебираем все числа от 5 до 31 включительно
for i in range(5, 32):
    # Считаем количество программ, которые могут привести к числу i:
    # 1) из i-1 через команду "+1"
    # 2) из i-2 через команду "+2"
    # 3) из i//3 через команду "*3", если i делится на 3
    a[i] = a[i - 1] + a[i - 2] + a[i // 3] * (i % 3 == 0)
    # Если достигли числа 18, обнуляем все предыдущие индексы
    # чтобы обеспечить прохождение через число 18
    if i == 18:
        for j in range(i):
            a[j] = 0
# Выводим количество программ, которые ведут от 4 к 31 через 18
print(a[31])

Ответ: 236756

Ошибка.
Попробуйте повторить позже

Задача 26#58500Максимум баллов за задание: 1

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

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

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

3. Умножить на 5

Программа для исполнителя ТриЧетыреПять – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 100, и при этом траектория вычислений содержит число 50?

Показать ответ и решение

Рекурсия:

Решение рекурсией

Мы будем использовать рекурсию для подсчёта всех программ, которые преобразуют число $x$ в число $y$ . Основная идея состоит в том, чтобы на каждом шаге проверять, достигли ли мы целевого числа, превысили ли его, и если ни одно из этих условий не выполнено, рекурсивно пробовать все три команды.

1. Если текущее число $x$ совпадает с целевым числом $y$ , мы возвращаем 1, так как найден один корректный путь.

2. Если текущее число $x$ больше $y$ , дальнейшие команды не помогут, и мы возвращаем 0.

3. Иначе мы рекурсивно вызываем функцию трижды:

- $f (x + 3,y)$ — пробуем команду "прибавить 3"

- $f (x + 4,y)$ — пробуем команду "прибавить 4"

- $f (x ∗5,y)$ — пробуем команду "умножить на 5"

Сумма этих трёх значений даст общее количество программ, ведущих от $x$ к $y$ .

Так как траектория должна содержать число 50, мы считаем количество способов сначала дойти от 2 до 50, а затем отдельно от 50 до 100. Общее количество программ — это произведение этих двух значений, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Определяем функцию f(x, y), которая считает количество программ от x до y
def f(x, y):
    # Если текущее число совпадает с целевым, найден один путь
    if x == y:
        return 1
    # Если текущее число больше целевого, пути невозможны
    if x > y:
        return 0
    # Иначе считаем все возможные команды и суммируем результаты
    return f(x + 3, y) + f(x + 4, y) + f(x * 5, y)

# Вычисляем количество программ, учитывая обязательное прохождение через 50
print(f(2, 50) * f(50, 100))

—

Решение динамикой

Мы можем использовать динамическое программирование, чтобы подсчитать количество программ для каждого числа до 100. Основная идея: создать массив a, где a[i] — количество программ, которые приводят к числу $i$ .

1. Инициализируем массив нулями и устанавливаем a[2] = 1, так как стартуем с числа 2.

2. Перебираем все числа от 3 до 100:

- Для каждого числа $i$ добавляем количество программ из $i− 3$ , используя команду "прибавить 3".

- Добавляем количество программ из $i− 4$ , используя команду "прибавить 4".

- Если $i$ делится на 5, добавляем количество программ из $i∕∕5$ , используя команду "умножить на 5".

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

4. После завершения цикла, a[100] содержит общее количество программ, которые проходят через 50 и приводят к 100.

# Создаем массив для чисел от 0 до 100
a = [0] * 101
# Начальное положение - число 2, один способ
a[2] = 1
# Перебираем числа от 3 до 100
for i in range(3, 101):
    # Считаем количество программ из i-3 и i-4
    # Добавляем i//5 только если i кратно 5
    a[i] = a[i - 3] + a[i - 4] + a[i // 5] * (i % 5 == 0)
    # Если достигли числа 50, обнуляем все предыдущие значения,
    # чтобы гарантировать прохождение через 50
    if i == 50:
        for j in range(i):
            a[j] = 0

# Выводим количество программ, ведущих от 2 до 100 через 50
print(a[100])

Ответ: 31503912

Ошибка.
Попробуйте повторить позже

Задача 27#60488Максимум баллов за задание: 1

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

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

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

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

Программа для исполнителя Банан – это последовательность команд. Сколько существует программ, для которых при исходном числе 7 результатом является число 77, и при этом траектория вычислений содержит число 31?

Показать ответ и решение

Решение рекурсией

Мы используем рекурсивный способ, в котором строим функцию f(n, m), подсчитывающую количество программ, преобразующих число n в число m.

1. Сначала мы проверяем условие окончания пути:

- Если n == m, значит мы достигли цели, и существует один корректный путь. Возвращаем 1.

- Если n > m, путь невозможен (число превысило цель), возвращаем 0.

2. Если ни одно из условий не выполнено, мы выполняем рекурсивные вызовы для каждой команды:

- f(n + 2, m) — соответствует команде "прибавить 2".

- f(n + 5, m) — соответствует команде "прибавить 5".

- f(n * 3, m) — соответствует команде "умножить на 3".

3. Чтобы учитывать условие, что траектория содержит число 31, мы делим вычисление на два этапа:

- Сначала считаем все пути от 7 до 31: f(7, 31).

- Затем считаем пути от 31 до 77: f(31, 77).

- Произведение этих двух значений даёт общее количество программ, так как для каждого пути до 31 можно использовать любой путь из 31 до 77.

# Определяем рекурсивную функцию f(n, m)
def f(n, m):
    # Если текущее число равно цели, найден один путь
    if n == m:
        return 1
    # Если текущее число больше цели, путь невозможен
    if n > m:
        return 0
    # В остальных случаях суммируем количество программ для всех трех команд
    return f(n + 2, m) + f(n + 5, m) + f(n * 3, m)

# Считаем пути до числа 31, затем от 31 до 77, перемножаем результаты
print(f(7, 31) * f(31, 77))

—

Решение динамикой

Мы используем динамический массив a длиной 78, где каждый элемент a[i] хранит количество программ, приводящих к числу i.

1. Инициализируем массив нулями: a = [0] * 78.

2. Устанавливаем начальное число 7: a[7] = 1, так как существует ровно один способ находиться в числе 7 без выполнения команд.

3. Проходим по всем числам от 8 до 77:

- Для каждого i прибавляем количество способов добраться из i-2, i-5.

- Если i делится на 3, добавляем количество способов из i//3.

- После достижения числа 31 обнуляем все предыдущие значения массива (a[j] = 0 для всех j < 31), чтобы обеспечить прохождение траектории через 31.

4. В конце количество программ, которые приводят к числу 77 через 31, хранится в a[77].

# Создаем массив для хранения количества программ
a = [0] * 78
# Начальное число 7 имеет один путь
a[7] = 1
# Перебираем все числа от 8 до 77
for i in range(8, 78):
    # Суммируем количество способов из предыдущих чисел
    a[i] = a[i - 2] + a[i - 5] + a[i // 3] * (i % 3 == 0)
    # Если достигли числа 31, обнуляем все предыдущие значения
    if i == 31:
        for j in range(i):
            a[j] = 0
# Выводим количество программ, которые ведут от 7 к 77 через 31
print(a[77])

Ответ: 315645

Ошибка.
Попробуйте повторить позже

Задача 28#60737Максимум баллов за задание: 1

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

1. Прибавь 1

2. Прибавь 2

3. Умножь на 3

Первая из них увеличивает число на экране на 1, вторая увеличивает число на 2, третья увеличивает число в 3 раза. Программа для исполнителя РазДваТри - это последовательность команд.

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

Показать ответ и решение

Решение рекурсией

Решение рекурсией основано на создании функции f(a, b), которая подсчитывает количество программ, преобразующих число $a$ в число $b$ . Алгоритм работы функции:

1. Если текущее число $a$ больше целевого числа $b$ , значит путь невозможен, возвращаем 0.

2. Если текущее число $a$ совпало с целевым $b$ , значит найден подходящий путь, возвращаем 1.

3. Если ни одно из условий не выполнено, то считаем все возможные переходы из текущего числа:

- прибавляем 1, вызываем f(a + 1, b);

- прибавляем 2, вызываем f(a + 2, b);

- умножаем на 3, вызываем f(a * 3, b);

и складываем результаты этих вызовов.

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

- Первый этап: от 3 до 9, считаем количество способов дойти до 9.

- Второй этап: от 9 до 14, считаем количество способов дойти до 14, начиная с 9.

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

# Определяем рекурсивную функцию f(a, b)
def f(a,b):
    # Если текущее число превысило целевое, путь невозможен
    if a > b:
        return 0
    # Если текущее число совпало с целевым, найден корректный путь
    if a == b:
        return 1
    # В остальных случаях считаем все возможные переходы:
    # прибавляем 1, прибавляем 2, умножаем на 3
    return f(a + 1, b) + f(a + 2, b) + f(a * 3, b)

# Вычисляем количество программ от 3 до 14 через число 9
print(f(3, 9) * f(9, 14))

—

Решение динамикой

Динамический способ решения заключается в поэтапном заполнении массива a, где индекс соответствует числу, а значение по этому индексу показывает количество программ, которые приводят к этому числу. Алгоритм:

1. Создаем массив a длиной 15 (так как максимальное число 14) и заполняем нулями.

2. Инициализируем начальное число: a[3] = 1, так как стартуем с числа 3, существует ровно один способ быть в этом положении.

3. Перебираем числа от 4 до 14 включительно:

- Для числа i считаем количество программ из предыдущих чисел:

* из i-1, прибавив 1;

* из i-2, прибавив 2;

* из i//3, если i делится на 3, умножив на 3.

- Если число i равно 9, обнуляем все предыдущие ячейки массива, так как траектория должна содержать число 9.

Итоговое количество программ, которые ведут от 3 к 14 через число 9, хранится в a[14].

# Создаем массив для хранения количества программ до каждого числа
a = [0] * 15
# Инициализируем исходное число 3
a[3] = 1
# Перебираем все числа от 4 до 14
for i in range(4, 15):
    # Считаем количество программ через предыдущие числа
    a[i] = a[i - 1] + a[i - 2] + a[i // 3] * (i % 3 == 0)
    # Обнуляем предыдущие значения до числа 9, чтобы траектория обязательно содержала 9
    if i == 9:
        for j in range(i):
            a[j] = 0

# Выводим количество программ, которые ведут от 3 к 14 через число 9
print(a[14])

Ответ: 112

Ошибка.
Попробуйте повторить позже

Задача 29#63344Максимум баллов за задание: 1

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

1. Вычти 5

2. Вычти 7

Первая из них уменьшает число на экране на 5, вторая уменьшает число на экране на 7.

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

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

Показать ответ и решение

Решение рекурсией

Мы решаем задачу рекурсивно, создавая функцию f(x, y), которая считает количество программ, преобразующих число x в число y. Идея решения состоит в том, что каждая программа — это последовательность команд, а каждая команда уменьшает текущее число на 5 или на 7. Поэтому количество программ, ведущих от x к y, можно выразить через количество программ, ведущих от x-5 к y и от x-7 к y.

1. Сначала проверяем условие: если текущее число x стало меньше целевого y, значит путь невозможен, и мы возвращаем 0.

- Это означает, что мы не можем дальше уменьшать число и достигнуть y.

2. Если текущее число x совпало с целевым y, значит найден один корректный путь, и мы возвращаем 1.

- Это учитывает случай, когда мы достигли нужного числа без лишних шагов.

3. Если ни одно из условий не выполнено (то есть x > y), мы делаем два рекурсивных вызова:

- Первый вызов: f(x-5, y), который соответствует применению команды "вычти 5".

- Второй вызов: f(x-7, y), который соответствует применению команды "вычти 7".

- Сумма результатов этих двух вызовов даёт общее количество программ для текущего x.

Так как в условии задачи требуется, чтобы траектория проходила через число 37, мы делим процесс на два этапа:

1) от 101 до 37,

2) от 37 до 20.

Количество всех программ равно произведению f(101, 37) * f(37, 20), потому что каждая программа из первой части может сочетаться с любой программой из второй части.

# Определяем функцию f(x, y), которая подсчитывает количество программ
def f(x,y):
    # Если текущее число стало меньше целевого,
    # то путь невозможен, возвращаем 0
    if x < y:
        return 0
    # Если текущее число совпало с целевым,
    # значит найден один корректный путь, возвращаем 1
    if x == y:
        return 1
    # Если текущее число больше целевого,
    # пробуем два варианта команд: вычесть 5 или вычесть 7
    return f(x - 5, y) + f(x - 7, y)

# Вычисляем количество программ, проходящих через 37
# Сначала считаем пути от 101 до 37
# Затем пути от 37 до 20
# Результат — произведение двух значений
print(f(101, 37) * f(37, 20))

Ответ: 558

Ошибка.
Попробуйте повторить позже

Задача 30#63345Максимум баллов за задание: 1

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

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

B. Прибавить 4

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

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

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

Показать ответ и решение

Решение рекурсией

Решение кодом через рекурсию заключается в том, что мы определяем функцию f(x, y), которая подсчитывает количество программ, преобразующих число $x$ в число $y$ . Внутри функции мы делаем следующие проверки:

1. Если текущее число $x$ стало больше целевого числа $y$ , значит, дальнейшие действия не приведут к успеху, и возвращаем 0.

2. Если текущее число $x$ равно $y$ , значит мы нашли одну корректную программу, и возвращаем 1.

3. Если ни одно из условий не выполнено, значит ещё можно применять команды, поэтому делаем три рекурсивных вызова функции:

- первый вызов с аргументом $x + 1$ , что соответствует команде A "прибавить 1";

- второй вызов с аргументом $x∗ 2$ , что соответствует команде C "умножить на 2";

- третий вызов с аргументом $x+ 4$ , что соответствует команде B "прибавить 4".

Так как траектория должна содержать число 18, мы разделяем вычисления на два этапа: от 10 до 18 и от 18 до 36. Результаты двух этапов перемножаются, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Определяем функцию f(x, y), которая считает количество программ
def f(x, y):
    # Если текущее число стало больше целевого,
    # дальнейшие действия невозможны, возвращаем 0
    if x > y :
        return 0
    # Если текущее число равно целевому,
    # найден один корректный путь, возвращаем 1
    if x == y:
        return 1
    # Если текущее число меньше целевого,
    # суммируем количество программ для всех трёх команд
    return f(x + 1, y) + f(x * 2, y) + f(x + 4, y)

# Вычисляем количество программ от 10 до 18 и от 18 до 36, умножаем результаты
print(f(10, 18) * f(18, 36))

—

Решение динамикой

Решение кодом через динамику заключается в том, что мы создаём массив a длиной 37 элементов (так как целевое число 36) и заполняем его нулями. Каждый индекс массива соответствует числу, а значение в ячейке показывает количество программ, которые приводят от исходного числа 10 к этому числу.

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

2. Для каждого числа $i$ от 11 до 36:

- Считаем количество программ, которые приходят из $i − 1$ (команда A), из $i− 4$ (команда B) и из $i∕∕2$ , только если $i$ чётное (команда C).

- Если $i$ равно 18, то обнуляем все предыдущие значения массива (от 0 до 17), так как траектория должна содержать число 18, и все пути, не достигшие этого числа, больше не считаются.

После прохода по массиву значение в a[36] даёт итоговое количество программ.

# Создаем массив из 37 элементов, все значения изначально равны 0
a = [0] * 37
# В ячейку с индексом 10 записываем 1, так как стартуем с числа 10
a[10] = 1
# Перебираем все числа от 11 до 36
for i in range(11, 37):
    # В число i можно попасть из i-1, i-4 или i//2 (если i чётное)
    a[i] = a[i - 1] + a[i - 4] + a[i // 2] * (i % 2 == 0)
    # Если достигли числа 18, обнуляем все предыдущие числа,
    # так как траектория должна содержать число 18
    if i == 18:
        for j in range(i):
            a[j] = 0

# Выводим количество программ, которые ведут от 10 к 36, через 18
print(a[36])

Ответ: 1274

Ошибка.
Попробуйте повторить позже

Задача 31#63348Максимум баллов за задание: 1

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

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

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

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

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

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

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

Показать ответ и решение

Решение рекурсией

Решение кодом через рекурсию заключается в том, что мы создаём функцию f(x, y, is_8=0, is_13=0), которая считает количество программ, преобразующих число $x$ в число $y$ , с учётом того, встречались ли уже числа 8 или 13 в траектории.

1. В начале функции мы проверяем, достигло ли текущее число $x$ числа 8 или 13:

- Если $x == 8$ , то устанавливаем is_8 = 1, что означает, что число 8 встречено на траектории.

- Если $x == 13$ , то устанавливаем is_13 = 1, что означает, что число 13 встречено на траектории.

2. Далее проверяем базовые условия завершения рекурсии:

- Если текущее число $x$ превысило целевое число $y$ , значит этот путь не приведёт к цели, и возвращаем 0.

- Если текущее число $x$ равно целевому числу $y$ , проверяем условие задачи о траектории: число 8 и 13 должны встречаться не одновременно и не отсутствовать полностью. Для этого проверяем is_8 != is_13. Если условие выполнено, возвращаем 1 — найден корректный путь.

3. Если текущее число $x$ меньше $y$ , продолжаем рекурсию:

- Вызываем функцию с аргументом $x + 1$ , что соответствует команде 1 «прибавить 1».

- Вызываем функцию с аргументом $x ∗2$ , что соответствует команде 2 «умножить на 2».

- Вызываем функцию с аргументом $x + 2$ , что соответствует команде 3 «прибавить 2».

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

4. Запускаем функцию для исходного числа 3 и целевого числа 23 и выводим результат.

# Определяем рекурсивную функцию подсчета программ
def f(x, y, is_8 = 0, is_13 = 0):
    # Проверяем, достигли ли числа 8
    if x == 8:
        is_8 = 1
    # Проверяем, достигли ли числа 13
    if x == 13:
        is_13 = 1

    # Если текущее число больше целевого, путь невозможен
    if x > y:
        return 0
    # Если достигли целевого числа, проверяем условие по траектории
    if x == y and is_8 != is_13:
        return 1
    # Если число меньше целевого, суммируем количество программ для всех команд
    if x < y:
        return f(x + 1, y, is_8, is_13) + f(x * 2, y, is_8, is_13) + f(x + 2, y, is_8, is_13)
    return 0

# Вычисляем количество программ от 3 до 23, учитывая условие про числа 8 и 13
print(f(3, 23))

Ответ: 7003

Ошибка.
Попробуйте повторить позже

Задача 32#63350Максимум баллов за задание: 1

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

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

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

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

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

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

Показать ответ и решение

Решение рекурсией

Определим функцию f(a, b), которая будет вызывать саму себя. Она подсчитает количество программ, преобразующих число a в b. Функция возвращает:

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+1, умножить на 2, +2), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def F(x, y):
    if x == y: # Если дошли до нужного числа
        return 1
    if x > y : # Если число стало больше нужного
        return 0
    else:
        return F(x + 1, y) + F(x + 2, y) + F(x * 2,y) # Количество путей до текущего числа

print(F(3, 9) * F(9, 11) * F(11, 13))  # Найдем ответ по условию задачи, умножение позволит нам включить число 9 и 11 в цепочку действий

Решение динамикой

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i - 1, i - 2 и i // 2.

# Создаем массив для хранения количества путей до чисел от 4 до 13
# a[i] - количество программ, которые преобразуют число 3 в число i
a = [0] * 100
a[3] = 1 # Начальное число
for i in range(4, 14):
    a[i] = a[i - 1] + a[i - 2] + a[i // 2] * (i % 2 == 0) # Будем делить на 2 только если число кратно 2
    # Если встретили 9 или 11 обнулим все значения до них. Таким образом мы не включим в последующие подсчёты лишние пути.
    if i == 9 or i == 11:
        for j in range(i):
            a[j] = 0

print(a[13]) # Выводим ответ

Ответ: 68

Ошибка.
Попробуйте повторить позже

Задача 33#63932Максимум баллов за задание: 1

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

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

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

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

Программа для исполнителя ААА - это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 14, и при этом траектория вычислений содержит числа 6 и 10?

Показать ответ и решение

Решение рекурсией

Определим функцию f(a, b), которая будет вызывать саму себя. Она подсчитает количество программ, преобразующих число a в b. Функция возвращает:

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+1, умножить на 2, +3), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(n, m):
    if n == m: # Если дошли до нужного числа
        return 1
    if n > m: # Если число стало больше нужного
        return 0
    if n < m:
        return f(n + 1, m) + f(n + 3, m) + f(n * 2, m) # Количество путей до текущего числа

print(f(2, 6) * f(6, 10) * f(10, 14)) # Найдем ответ по условию задачи

Решение динамикой

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i - 1, i - 3 и i // 2.

# Создаем массив для хранения количества путей до чисел от 3 до 14
# a[i] - количество программ, которые преобразуют число 2 в число i
a = [0] * 15
a[2] = 1 # Начальное число
for i in range(3, 15):
    a[i] = a[i - 1] + a[i - 3] + a[i // 2] * (i % 2 == 0) # Будем делить на 2 только если число кратно 2
    # Если встретили нужное число - обнулим все до него. Так, проходя дальше, мы будем учитывать только подходящий путь, чтоб не перескочить нужный.
    if i == 6 or i == 10:
        for j in range(i):
            a[j] = 0

print(a[14]) # Выводим ответ

Ответ: 45

Ошибка.
Попробуйте повторить позже

Задача 34#72492Максимум баллов за задание: 1

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

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

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

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

Показать ответ и решение

Решение рекурсией

Определим функцию f(a, b), которая будет вызывать саму себя. Она подсчитает количество программ, преобразующих число a в b. Функция возвращает:

0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
сумму значений для трёх возможных переходов (+2, +3), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(a, b):
    if a > b: # Если число стало больше нужного
        return 0
    if a == b: # Если дошли до нужного числа
        return 1
    else:
        return f(a + 2, b) + f(a + 3, b) # Количество путей до текущего числа
print(f(4, 7) * f(7, 14)) # Найдем ответ по условию задачи

Решение динамикой

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 8 необходимо знать количество траекторий до числа 5, 6 и 7.

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i - 2, i - 3.

# Создаем массив для хранения количества путей до чисел от 5 до 14
# a[i] - количество программ, которые преобразуют число 4 в число i
a = [0] * 15
a[4] = 1 # Начальное число
for i in range(5, 15):
    a[i] = a[i - 2] + a[i - 3]
    # Если встретили нужное число - обнулим всё до него. Таким образом мы точно его не перепрыгнем и будем учитывать подходящие пути.
    if i == 7:
        for j in range(i):
            a[j] = 0
print(a[14]) # Выводим ответ

Ответ: 3

Ошибка.
Попробуйте повторить позже

Задача 35#136848Максимум баллов за задание: 1

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

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

A. Вычти 2

B. Найди целую часть от деления на 2

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

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

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.

Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2.

Показать ответ и решение

Идея решения

Решение строится с помощью рекурсивной функции f(a,b), которая считает количество способов преобразовать число a в число b. Функция работает так: - если a < b, то решений нет (возвращается 0); - если a == b, то найден один путь (возвращается 1); - иначе выполняем рекурсивный вызов от двух возможных шагов: a - 2 (команда A) и a // 2 (команда B).

Чтобы учесть требование, что траектория должна содержать число 16, используем произведение:

f(38,16)× f(16,2)

Таким образом, считаем количество программ, которые ведут от 38 до 16, и затем от 16 до 2.

Решение:

def f(a, b):
    # Нет решений, если текущее число меньше целевого
    if a < b:
        return 0
    # Если дошли ровно до b, найден один путь
    if a == b:
        return 1
    # Рекурсивно пробуем обе команды: A (a-2) и B (a//2)
    return f(a - 2, b) + f(a // 2, b)

# Считаем количество программ через промежуточное число 16
print(f(38, 16) * f(16, 2))

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 36#137638Максимум баллов за задание: 1

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

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

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

Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 20, и при этом траектория вычислений содержит число 10? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Показать ответ и решение

Решение программой:

Чтобы найти количество программ, мы воспользуемся функцией, которая вызывает сама себя (рекурсией). Определим функцию f(a, b), где параметр a обозначает текущее число на экране, а параметр b – целевое число, к которому мы хотим прийти.

Функция f(a, b) работает по правилам:

1. Если a > b, возвращаем 0, так как выйти за предел целевого числа нельзя, программа в этом случае не подходит.

2. Если a == b, возвращаем 1. Это значит, что найден один способ дойти от числа a до числа b.

3. В противном случае мы продолжаем движение по траектории, пробуя обе возможные команды:

- команда «прибавить 1» (a + 1),

- команда «умножить на 2» (a * 2).

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

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

* сначала считаем количество способов добраться от 1 до 10,

* затем – количество способов добраться от 10 до 20.

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

# Определяем функцию f, которая считает количество программ от числа a до числа b
def f(a, b):
    # Если текущее число стало больше целевого, возвращаем 0
    if a > b:
        return 0
    # Если текущее число совпало с целевым, возвращаем 1
    if a == b:
        return 1
    # Иначе пробуем оба варианта перехода:
    # 1) добавляем 1
    # 2) умножаем на 2
    # и суммируем количество найденных путей
    return f(a + 1, b) + f(a * 2, b)

# Считаем количество программ как произведение двух этапов:
# из 1 в 10 и из 10 в 20
print(f(1, 10) * f(10, 20))

Ответ: 28