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

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

Мы создаём список a, где индекс соответствует числу, а значение a[i] показывает количество способов попасть в это число, начиная с .

1. В начале a[1] = 1, так как в исходном числе можно находиться единственным способом — стартовав в нём.

2. Для каждого числа от до определяем количество способов:

- в число всегда можно попасть из , если применить команду «+1»;

- если чётное, то в него можно попасть ещё и из , если применить команду «умножить на 2».

3. Таким образом, формула:

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

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

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

Теперь определим функцию f(a), которая считает количество способов преобразовать число a в число .

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

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

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

- f(a+1) — это переход по команде «+1»;

- f(a*2) — это переход по команде «*2».

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

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

# Запускаем функцию от исходного числа 1
print(f(1))

Решение руками

В четные числа мы можем попасть из числа деленного на 2 или предыдущего, а в нечетные только из предыдущих.
Получается, что в число 2 мы можем попасть из 1 двумя разными способами.
В число 3 мы можем попасть только из 2.
В число 4 мы можем попасть из 2 или 3.
В число 5 мы можем попасть только из 4.
И т.д.