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

Идея решения программой через динамику

Мы начинаем с пошагового перевода условия задачи на язык Python. Для этого создаём массив (список), в котором каждая ячейка хранит количество способов достичь соответствующего числа. В Python список создаётся оператором умножения: [0] * (n + 1), где n+1 означает количество элементов. Индексация в Python начинается с нуля, поэтому ячейка с индексом соответствует числу .

Начальное условие — число : это единственная точка старта, поэтому в массиве ставим a[2] = 1, а все остальные ячейки остаются равными нулю. Далее используем цикл for i in range(3, 30+1), чтобы поочередно заполнить ячейки от до . Конструкция range(x, y) порождает последовательность от до , поэтому верхнюю границу всегда нужно задавать с «+1».

Внутри цикла для каждого проверяем условия: 1. Если , пропускаем шаг (continue), так как это число не должно встречаться в траектории. 2. Если чётное, то для подсчёта количества способов сложим три значения: a[i-1], a[i-2] и a[i // 2]. Запись i // 2 означает целую часть от деления на . 3. Если нечётное, то складываем только два предыдущих значения: a[i-1] и a[i-2].

Таким образом мы получаем количество способов попасть в число . Аналогично строим второй массив для перехода из в , где базовое условие теперь b[30] = 1. Логика переходов сохраняется, только диапазон меняется на range(31, 41+1). Итоговый ответ вычисляется как произведение a[30] * b[41], так как для каждого пути первой части можно использовать любой путь второй части.

Решение через динамику:

# Первый этап: от 2 до 30
# Создаём список из 31 элемента, заполненный нулями
a = [0] * (30 + 1)
# Начальная позиция: только один способ быть в числе 2
a[2] = 1
# Перебираем все числа от 3 до 30 включительно
for i in range(3, 30 + 1):
    # Если текущее число равно 7, то его пропускаем
    if i == 7:
        continue
    # Если число чётное, то складываем три возможных пути
    elif i % 2 == 0:
        a[i] = a[i - 1] + a[i - 2] + a[i // 2]
    # Если число нечётное, складываем только два предыдущих
    else:
        a[i] = a[i - 1] + a[i - 2]

# Второй этап: от 30 до 41
# Создаём список из 42 элементов для хранения количества способов
b = [0] * (41 + 1)
# Начальная позиция: в числе 30 один способ
b[30] = 1
# Перебираем все числа от 31 до 41 включительно
for i in range(31, 41 + 1):
    # Если число чётное, учитываем три варианта переходов
    if i % 2 == 0:
        b[i] = b[i - 1] + b[i - 2] + b[i // 2]
    # Если число нечётное, учитываем только два варианта переходов
    else:
        b[i] = b[i - 1] + b[i - 2]

# Перемножаем количество способов первого и второго этапа
print(a[30] * b[41])

Идея решения через рекурсию:

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

1. Если a > b или a == 7, то возвращаем 0, так как переход невозможен. 2. Если a == b, то возвращаем 1, так как найден ровно один способ достижения цели.

Если базовые случаи не выполняются, то возвращаем сумму значений трёх возможных переходов: f(a+1, b), f(a+2, b), f(a*2, b). Каждый вызов — это новая задача с другим стартовым числом.

Так как по условию траектория должна содержать число , итоговое значение вычисляем как произведение f(2, 30) * f(30, 41). Первая часть считает количество способов пройти из в , вторая — из в .

Решение через рекурсию:

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

# Считаем количество способов пройти от 2 до 30 и от 30 до 41
# Умножаем результаты, так как обе части независимы
print(f(2, 30) * f(30, 41))

Решение аналитикой:

Количество программ, которые преобразуют число 2 в число обозначим Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на три, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа:
Если число на три делится, то вариантов последней команды два: прибавь 2 и умножь на 3, тогда Заполним таблицу по данной формуле:

Отсюда видим, что всего программ 15.