23.01 Количество программ из A в B

Решение (Рекурсия)

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

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

# Функция для подсчета количества программ преобразования a -> b
def f(a,b):
if a>b: # Если начальное число больше конечного, то возвращаем 0
return 0
if a==b: # Начальное число равно конечному числу - Возвращаем 1
return 1
# Иначе делаем все возможные варианты
return f(a + 1, b) + f(a + 2, b)
# Выводим результат
print(f(1,10))

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

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

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

Чтобы получить итоговый ответ, выведем количество траекторий до числа 10.

# Создаем массив для хранения количества путей до чисел от 0 до 1000
# a[i] - количество программ, которые преобразуют число 1 в число i
a = [0] * 1000
a[1] = 1  # Исходное положение - только один способ быть в числе 1
# Перебираем все числа от 3 до 10 невключительно
for i in range(10):
    a[i+1] += a[i] # Из a[i] можно попасть в a[i+1]
    a[i+2] += a[i] # Из a[i] можно попасть в a[i+2]
print(a[10]) # Общее количество программ до 10

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

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

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

# Создаем массив для хранения количества путей до чисел от 3 до 38
# a[i] - количество программ, которые преобразуют число 2 в число i
a = [0]*39
a[2] = 1 # Начальное число
# Перебираем все числа от 3 до 38 включительно
for i in range(3, 39):
    # Добавим проверки, что для деления число должно быть чётным и корень из числа будет целым
    a[i] = a[i-1] + a[i//2]*(i % 2 == 0) + a[int(i**0.5)] * (i**0.5 == int(i**0.5))
print(a[38]) # Выводим ответ

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

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

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

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

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

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

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

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

# Создаем массив для хранения количества путей до чисел от 3 до 128
# a[i] - количество программ, которые преобразуют число 2 в число i
a = [0] * 129
a[2] = 1 # Начальное число
# Перебираем все числа от 3 до 128 включительно
for i in range(3, 129):
    a[i] += a[i - 5] + a[i - 8]
print(a[128]) # Выведем ответ

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

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

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

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

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

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

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

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

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

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

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

# Создаем массив для хранения количества путей до чисел от 3 до 25
# a[i] - количество программ, которые преобразуют число 2 в число i
a = [0] * 26
a[2] = 1 # Начальное число
for i in range(3, 26):
    a[i] = a[i - 2] + a[i // 4] * (i % 4 == 0) + a[i - 1] # Дополнительно проверим, что число нацело делится на 4
print(a[25]) # Выводим ответ

Решение 3 (Динамика)

a = [0] * 150
a[2] = 1 # Начальное число
# Аналогично прошлому решению произведём операции. Будем добавлять текущее значение к ячейкам +1, +2, умножить на 4.
for i in range(2, 25):
    a[i + 1] += a[i]
    a[i + 2] += a[i]
    a[i * 4] += a[i]
print(a[25]) # Выводим ответ

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

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

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

def f(st, fn):
    if st == fn: # Если дошли до нужного числа
        return 1
    if st > fn: # Если число стало больше нужного
        return 0
    a = [0] * (st * st) # Массив с количеством путей до нашего числа
    for i in range(2, st + 1):
        a[i] = f(st * i, fn) # Заполняем массив по условию задачи
    return sum(a) # Количество путей до нашего числа
print(f(2, 60)) # Найдем ответ по условию задачи

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

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

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

# Создаем массив для хранения количества путей до чисел от 2 до 59
# a[i] - количество программ, которые преобразуют число 2 в число i
a = [0] * 60 * 60
a[2] = 1 # Начальное число
# Перебираем числа в нужном диапазоне
for i in range(2, 60):
    for j in range(2, i + 1): # Найдем количество путей до каждого числа по условию задачи
        a[i * j] += a[i]
print(a[60]) # Найдем ответ по условию задачи

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

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

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

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

print(f(12, 2215)) # Найдем ответ по условию задачи

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

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

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

# Создаем массив для хранения количества путей до нужного числа
# a[i] - количество программ, которые преобразуют число 12 в число i
a = [0] * 2216
a[12] = 1 # Начальное число
for i in range(13, 2216):
    a[i] = a[i - 11]
    if i % 2 == 0: # Добавим проверку, что для деления число должно делиться нацело
        a[i] += a[i // 2]
print(a[2215]) # Выводим ответ

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

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

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

# Модуль для того,
# чтобы функция не считала одни и те же значения по нескольку раз.
# Значительно ускоряет программу
from functools import lru_cache
@lru_cache(None)
# Функция для подсчета количества программ преобразования a -> b
def f(n, m):
    if n == m: # Если дошли до нужного числа
        return 1
    if n > m: # Если число стало больше нужного
        return 0
    return f(n + 1, m) + f(n + 2, m) + f(n * 2, m) # Количество путей до текущего числа

print(f(5, 40)) # Найдем ответ по условию задачи

 

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

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

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

# Создаем массив для хранения количества путей до чисел
# a[i] - количество программ, которые преобразуют число 5 в число i
a = [0] * 100
a[5] = 1 # Начальное число
for i in range(6, 41):
    a[i] = a[i - 1] + a[i - 2] + a[i // 2] * (i % 2== 0) # Проверим четность числа для правильного результата при делении на 2
print(a[40])

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

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

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

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

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

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

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

# Создаем массив для хранения количества путей до чисел
# a[i] - количество программ, которые преобразуют число 12 в число i
a = [0] * 100
a[12] = 1 # Начальное число
# Перебираем все числа от 13 до 96 включительно
for i in range(13, 97):
    a[i] = a[i - 3] + a[i // 2] * (i % 2== 0) # Делить на 2 будем только если число чётное
print(a[96]) # Выводим ответ

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

Определим функцию 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
    return f(a + 2, b) + f(a * 3, b) # Количество путей до текущего числа
print(f(8, 50)) # Найдем ответ по условию задачи

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

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

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

# Создаем массив для хранения количества путей до чисел от 9 до 50
# a[i] - количество программ, которые преобразуют число 8 в число i
a = [0] * 100
a[8] = 1 # Начальное число
# Перебираем все нужные числа
for i in range(9, 51):
    a[i] = a[i - 2] + a[i // 3] * (i % 3 == 0) # Будем делить на 3 только если число кратно 3
print(a[50]) # Выводим ответ

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

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

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

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

print(f(5, 20)) # Найдем ответ по условию задачи

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

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

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

# Создаем массив для хранения количества путей до чисел от 6 до 20
# a[i] - количество программ, которые преобразуют число 5 в число i
a = [0] * 100
a[5] = 1 # Начальное число
for i in range(6, 21):
    a[i] = a[i - 1] + a[i - 3] + a[i // 2] * (i % 2 == 0) # Будем делить на 2 только если число кратно 2
print(a[20]) # Выводим ответ

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

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

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

d = set() # Создание списка
# Функция для подсчета количества программ преобразования a -> b
def f(a, c):
    if c > 9: # Если число команд больше 9, то вернуть 0
        return 0
    if c == 9:  # Если число команд равно 9, то вернуть список
        d.add(a)
        return
    if c < 9:  # Если число команд меньше 9, то продолжать выполнение команд
        f(a + 3, c + 1)
        f(a * 2, c + 1)
f(4,0)
print(len(d))

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

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

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

d = set() # Создание списка
# Функция для подсчета количества программ преобразования a -> b
def f(a,c):
    if c > 6: # Если число команд больше 6, то вернуть 0
        return 0
    if c == 6: # Если число команд равно 6, то вернуть список
        d.add(a)
        return
    if c < 6: # Если число команд меньше 6, то продолжать выполнение команд
        f(a + 1,c + 1)
        f(a + 4,c + 1)
        f(a * 3,c + 1)
f(7,0) # Запустим функцию для получения значений
print(len(d))

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

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

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

d = set() # Cоздание списка
# Функция для подсчета количества программ преобразования a -> b
def f(a, c):
    if c > 8: # Если число команд больше 8, то вернуть 0
        return 0
    if c == 8: # Если число команд равно 8, то вернуть список
        d.add(a)
        return
    if c < 8: # Если число команд меньше 8, то продолжать выполнение команд
        f(a + 5,c + 1)
        f(a - 3,c + 1)
        f(a * 4,c + 1)
f(12,0) # Запустим функцию для заполнения списка
print(len(d))

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

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

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

d = set() # Создание списка
# Функция для подсчета количества программ преобразования a -> b
def f(a,c):
    if c > 11: # Если число команд больше 11, то вернуть 0
        return 0
    if c == 11: # Если число команд равно 11, то вернуть список
        d.add(a)
        return
    if c < 11: # Если число команд меньше 11, то продолжать выполнение команд
        f(a - 1, c + 1)
        f(a - 5, c + 1)
        f(a * 2, c + 1)
f(2, 0) # Запустим функцию для получения значений
print(len(d))

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

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

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

d = set() # Создание списка
# Функция для подсчета количества программ преобразования a -> b
def f(a, c):
    if c > 7: # Если число команд больше 7, то вернуть 0
        return 0
    if c == 7: # Если число команд равно 7, то вернуть список
        d.add(a)
        return
    if c < 7: # Если число команд меньше 7, то продолжать выполнение команд
        f(a - 2, c + 1)
        f(a - 3, c + 1)
        f(a // 2, c + 1)
f(220, 0) # Запустим функцию для получения значений
print(len(d))

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

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

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

d = set() # Cоздание списка
def f(a,c):
    if c > 6: # Если число команд больше 6, то вернуть 0
        return 0
    if c == 6: # Если число команд равно 6, то вернуть список
        d.add(a)
        return
    if c < 6: # Если число команд меньше 6, то продолжать выполнение команд
        f(a + 5, c + 1)
        f(a * 3, c + 1)
        f(a * 4, c + 1)
        f(a * (-1), c + 1)
        f(a // 2, c + 1)
        f(a + (a % 4), c + 1)
f(12, 0) # Запустим программу для получения значений
print(len(d))

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

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

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

d = set() # Создание списка
def f(a, c):
    if c > 14: # Если число команд больше 14, то вернуть 0
        return 0
    if c == 14: # Если число команд равно 14, то вернуть список
        d.add(a)
        return
    if c < 14: # Если число команд меньше 14, то продолжать выполнение команд
        f(a + 4, c + 1)
        f(a * 2, c + 1)
        f(a * 2 + 1, c + 1)
f(1, 0) # Запустим программу для получения значений
print(len(d))

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

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

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

d = set() # Cоздание списка
def f(a, c):
    if c > 11 == 8: # Если число команд больше 8, то вернуть 0
        return 0
    if c == 8: # Если число команд равно 8, то вернуть список
        d.add(a)
        return
    f(a + 2, c + 1)
    f(a + 3, c + 1)
    f(a + a - 1, c + 1)
f(8, 0) # Запустим программу для получения значений
print(len(d))

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

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

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

d = set() # Создание списка
def f(a,c):
    if c > 6: # Если число команд больше 6, то вернуть 0
        return 0
    if c == 6: # Если число команд равно 6, то вернуть список
        d.add(a)
        return
    str1 = str(a)
    if int(str1[0]) < 9: # Увеличение старшего числа
      str2 = str(int(str1[0]) + 1) + str1[1:]
      str2 = int(str2)
    else:
        str2 = a
    if c < 6:  # Если число команд меньше 6, то продолжать выполнение команд
        f(a + 1, c + 1)
        f(str2, c + 1)
    elif c < 6:
        f(a + 1, c + 1)
f(67,0)
print(len(d))

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

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

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

d = set() # Создание списка
def f(a,c):
    if c > 9: # Если число команд больше 9, то вернуть 0
        return 0
    if c == 9: # Если число команд равно 9, то вернуть список
        d.add(a)
        return d
    str1 = str(a)
    str2 = ""
    for i in str1: # Увеличение разрядов числа
        if int(i) < 9: # Если разряд числа не равен 9, то увеличим его на 1
            str2 += str(int(i) + 1)
        else:
            str2 += i
    str2 = int(str2)
    if c < 9: # Если число команд меньше 9, то продолжать выполнение команд
        f(a + 3, c + 1)
        f(str2, c + 1)
f(81, 0) # Запуск программы для поиска значений
print(len(d))