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