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.

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

Обозначим число программ, преобразующих число 2 в число n как Тогда число может быть получено либо прибавлением к либо к либо из некоторого числа увеличением на так что откуда так могут быть получены только нечетные числа.
Тогда для четных чисел а для нечетных — ). Заполним таблицу по данным формулам:

Отсюда получаем искомое количество программ — 122.

Идея решения программой (рекурсией)

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

Функция начинается с базовых случаев: 1. Если текущее число a стало больше b, возвращаем 0, так как такой путь уже не может привести к цели. 2. Если a == b, возвращаем 1, так как найден ровно один способ достичь нужного числа.

Если базовые случаи не выполнены, мы рассматриваем возможные шаги: - всегда можем прибавить , это вызов f(a+1, b); - можем прибавить , это вызов f(a+2, b); - можем прибавить «предыдущее» число, то есть a-1. Тогда текущее число увеличивается на a-1, получаем выражение f(a + a - 1, b). Но этот шаг недопустим для числа , так как «предыдущее» будет равно . Поэтому добавляем этот вызов только если a != 1.

Каждый рекурсивный вызов возвращает количество способов для своей ветви, и мы суммируем их, так как все пути независимы. В конце программа печатает f(1, 10), что соответствует количеству способов пройти из в .

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

# Выводим количество программ, преобразующих 1 в 10
print(f(1,10))

Аналитическое решение

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

Отсюда видим, что имеем 34 возможных программ для получения числа 9.

Идея решения программой (рекурсией)

Мы определяем функцию f(a, b), которая возвращает количество способов преобразовать число a в число b, применяя только команды «прибавь 1» и «прибавь 2».

Функция работает по принципу разветвления:

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

2. Если a == b, возвращаем 1, так как найден ровно один путь достижения результата.

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

- переход от a к a+1, вызов f(a+1, b);

- переход от a к a+2, вызов f(a+2, b).

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

Чтобы решить задачу, вызываем функцию f(1, 9), то есть считаем количество всех возможных программ, преобразующих число в число .

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

# Выводим количество программ, преобразующих 1 в 9
print(f(1,9))

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

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

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

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

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

- f(x+1, y) — переход командой «прибавь 1»;

- f(x+2, y) — переход командой «прибавь 2»;

- f(x+3, y) — переход командой «прибавь 3».

Таким образом, функция находит общее количество программ, складывая все возможные пути. Чтобы получить ответ задачи, мы вызываем f(1, 14).

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

# Выводим количество программ, которые преобразуют 1 в 14
print(f(1, 14))

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

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

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

Далее последовательно заполним массив:

- чтобы попасть в число , можно прийти из числа (командой +1),

- или из числа (командой +2),

- или из числа (командой +3).

Поэтому общее число способов a[i] равно сумме a[i-1] + a[i-2] + a[i-3]. Вычисления нужно вести для всех чисел от до . Ответом задачи будет значение a[14].

# Создаем массив для хранения количества способов
a = [0] * 100
# В числе 1 есть один способ находиться — старт
a[1] = 1
# Заполняем массив для чисел от 2 до 14
for i in range(2, 15):
    # В i можно попасть из i-1, i-2 или i-3
    a[i] = a[i - 1] + a[i - 2] + a[i - 3]
# Выводим количество программ, которые преобразуют 1 в 14
print(a[14])

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

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

Отсюда получаем искомое количество программ — 1705.

Получается ответ:

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

Обе команды увеличивают исходное число. Старшая цифра — 3, следовательно, использовать команду 2 более двух раз бессмысленно.
Выпишем программы, в которых команда 2 используется два раза: 1122, 2211, 1212, 2121, 2112, 1221. Итого 6 программ.
Выпишем программы, в которых команда 2 используется один раз. Использовав эту команду в первой позиции, мы получим из числа 31 число 41, следовательно, после этого необходимо будет дописать ещё 12 команд 1 чтобы получить число 53. Таким образом, получаем программы: и. т. д. Итого имеем 13 программ (двойка побывала в каждой позиции).
Существует лишь одна программа, в которой команда 2 не используется:
Таким образом получаем

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

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

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

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

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

- f(a+1, b) — соответствует команде «прибавь 1»;

- f(a+10, b) — соответствует команде «увеличь старшую цифру числа на 1».

Суммируя эти два значения, получаем количество всех возможных программ, которые преобразуют a в b. Для решения задачи вычисляем f(31, 53).

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

# Выводим количество программ, которые преобразуют 31 в 53
print(f(31,53))

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

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

1. Если x > y, то возвращаем 0, так как число превысило цель и больше не может её достичь.

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

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

- f(x+1, y) — соответствует команде «прибавить 1»;

- f(x+2, y) — соответствует команде «прибавить 2»;

- f(x*4, y) — соответствует команде «умножить на 4».

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

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

# Выводим количество программ для преобразования 2 в 17
print(f(2, 17))

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

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

1. Изначально a[2] = 1, так как число — стартовое, и есть ровно один способ «быть в точке старта».

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

- складываем количество способов попасть в i-1 и i-2, так как из этих чисел можно перейти в i командами «+1» и «+2»;

- если число i делится на , то к результату добавляем a[i//4], так как в этом случае существует путь, ведущий через умножение на 4.

После окончания цикла в a[17] будет находиться итоговый ответ.

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

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

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

Если число делится на 4, то вариантов последней команды три: прибавить 1, прибавить 2 и умножить на 4, тогда . Заполним таблицу по данной формуле:

Отсюда получаем искомое количество программ — 1052.

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

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

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

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

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

- f(x+2, y) — шаг, соответствующий команде «прибавь 2»;

- f(x*10, y) — шаг, соответствующий команде «умножь на 10».

Таким образом, функция перебирает все возможные траектории и складывает количество успешных.

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

# Выводим количество программ для преобразования 2 в 40
print(f(2, 40))

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

Второй способ решения — динамическое программирование.

Создаём список a, где индекс i обозначает число, а a[i] — количество способов дойти до этого числа.

1. В начальной точке a[2] = 1, так как существует ровно один способ «быть» в числе 2.

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

- если мы пришли в число i командой «прибавь 2», то добавляем a[i-2];

- если число i делится на , то оно могло образоваться через команду «умножь на 10» из числа i//10, поэтому добавляем a[i//10].

После выполнения цикла в a[40] будет итоговое количество программ.

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

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

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

Отсюда получаем искомое количество программ - 3.

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

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

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

2. Далее последовательно для всех чисел от до вычисляем количество способов:

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

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

3. Поэтому a[i] = a[i-1] + a[i-2].

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

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

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

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

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

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

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

- f(a+1) — соответствует применению команды «+1»;

- f(a+2) — соответствует применению команды «+2».

Таким образом, функция перебирает все возможные траектории и суммирует количество успешных.

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

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

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

Мы создаём список 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.
И т.д.

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

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

1. Если x > y, возвращаем 0, так как число превысило цель и больше её достичь нельзя.

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

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

- f(x + 1, y) — соответствует применению команды «прибавь 1»;

- f(x + 3, y) — соответствует применению команды «прибавь 3».

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

# Выводим количество программ для преобразования числа 5 в 42
print(f(5, 42))

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

Второй способ — динамическое программирование.

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

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

2. Для чисел от до :

- количество способов попасть в число равно a[i-1] + a[i-3], так как в него можно попасть командой «+1» из и командой «+3» из .

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

# Создаём массив для хранения количества способов
a = [0] * 100
# Начальная точка (число 5) имеет один способ
a[5] = 1
# Заполняем массив для чисел от 6 до 42
for i in range(6, 43):
    # Количество способов попасть в число i
    a[i] = a[i - 1] + a[i - 3]
# Выводим количество программ для числа 42
print(a[42])

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

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

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

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

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

- f(x+1, y) — применение команды «прибавь 1»;

- f(x+2, y) — применение команды «прибавь 2»;

- f(x*3, y) — применение команды «умножь на 3».

Использование декоратора @lru_cache позволяет кэшировать уже вычисленные значения, что ускоряет рекурсию за счёт избежания повторных вычислений.

from functools import lru_cache

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

# Выводим количество программ для преобразования числа 4 в 63
print(f(4, 63))

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

Создаём массив a, где a[i] — количество способов получить число i от числа .

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

2. Для чисел от до :

- прибавляем количество способов попасть в i-1 через команду «прибавь 1»;

- прибавляем количество способов попасть в i-2 через команду «прибавь 2»;

- если число делится на 3, прибавляем количество способов попасть в i//3 через команду «умножь на 3».

После завершения цикла значение a[63] покажет количество всех программ.

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

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

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

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

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

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

- f(x + 1, y) — применение команды «прибавь 1»;

- f(x + 4, y) — применение команды «прибавь 4».

Использование декоратора @lru_cache позволяет кэшировать уже вычисленные значения, ускоряя рекурсию.

from functools import lru_cache

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

# Выводим количество программ для преобразования числа 1 в 128
print(f(1, 128))

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

Создаём массив num, где num[i] — количество способов получить число i от числа .

1. Инициализируем num[1] = 1, так как стартовое число имеет один способ «быть» в нём.

2. Для чисел от до :

- прибавляем num[i-1] для команды «прибавь 1»;

- если , прибавляем num[i-4] для команды «прибавь 4».

После заполнения массива значение num[128] покажет количество всех программ.

# Создаем массив для динамического программирования
num = [0] * 129
# Начальная точка (число 1) имеет один способ
num[1] = 1
# Заполняем массив для чисел от 2 до 128
for i in range(2, 129):
    # Количество способов через команду +1
    num[i] = num[i - 1]
    # Если число >= 5, добавляем путь через команду +4
    if i >= 5:
        num[i] += num[i - 4]
# Выводим количество программ для числа 128
print(num[128])

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

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

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

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

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

- f(x + 1, y) — применение команды «прибавь 1»;

- f(x + 10, y) — применение команды «прибавь 10».

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

# Выводим количество программ для преобразования числа 7 в 49
print(f(7, 49))

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

Создаём массив num, где num[i] — количество способов получить число i от числа .

1. Инициализируем num[7] = 1, так как стартовое число имеет один способ «быть» в нём.

2. Для чисел от до :

- прибавляем num[i-1] для команды «прибавь 1»;

- если , прибавляем num[i-10] для команды «прибавь 10».

После заполнения массива значение num[49] покажет количество всех программ.

# Создаем массив для динамического программирования
num = [0] * 60
# Начальная точка (число 7) имеет один способ
num[7] = 1
# Заполняем массив для чисел от 8 до 49
for i in range(8, 60):
    # Количество способов через команду +1
    num[i] = num[i - 1]
    # Добавляем путь через команду +10
    if i - 10 >= 7:
        num[i] += num[i - 10]
# Выводим количество программ для числа 49
print(num[49])

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

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

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

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

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

- f(x + 1, y) — применение команды «прибавь 1»;

- f(x + 3, y) — применение команды «прибавь 3».

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

# Выводим количество программ для преобразования числа 4 в 30
print(f(4, 30))

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

Создаём массив num, где num[i] — количество способов получить число i от числа .

1. Инициализируем num[4] = 1, так как стартовое число имеет один способ «быть» в нём.

2. Для чисел от до :

- прибавляем num[i-1] для команды «прибавь 1»;

- прибавляем num[i-3] для команды «прибавь 3».

После заполнения массива значение num[30] покажет количество всех программ.

# Создаем массив для динамического программирования
num = [0] * 31
# Начальная точка (число 4) имеет один способ
num[4] = 1
# Заполняем массив для чисел от 5 до 30
for i in range(5, 31):
    # Количество способов через команду +1
    num[i] = num[i - 1]
    # Добавляем путь через команду +3
    num[i] += num[i - 3]
# Выводим количество программ для числа 30
print(num[30])

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

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

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

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

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

- f(x + 2, y) — применение команды «прибавь 2»;

- f(x + 5, y) — применение команды «прибавь 5».

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

# Выводим количество программ для преобразования числа 1 в 19
print(f(1, 19))

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

Создаём массив num, где num[i] — количество способов получить число i от числа .

1. Инициализируем num[1] = 1, так как стартовое число имеет один способ «быть» в нём.

2. Для чисел от до :

- прибавляем num[i-2] для команды «прибавь 2»;

- прибавляем num[i-5] для команды «прибавь 5», если .

После заполнения массива значение num[19] покажет количество всех программ.

# Создаем массив для динамического программирования
num = [0] * 20
# Начальная точка (число 1) имеет один способ
num[1] = 1
# Заполняем массив для чисел от 2 до 19
for i in range(2, 20):
    # Количество способов через команду +2
    num[i] = num[i - 2]
    # Добавляем путь через команду +5, если возможно
    if i > 5:
        num[i] += num[i - 5]
# Выводим количество программ для числа 19
print(num[19])

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

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

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

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

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

- f(x + 1, y) — применение команды «прибавь 1»;

- f(x * 4, y) — применение команды «умножь на 4».

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

# Выводим количество программ для преобразования числа 1 в 55
print(f(1, 55))

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

Создаём массив a, где a[i] — количество способов получить число i от числа .

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

2. Для чисел от до :

- прибавляем a[i-1] для команды «прибавь 1»;

- прибавляем a[i//4] для команды «умножь на 4», только если делится на .

После заполнения массива значение a[55] покажет количество всех программ.

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

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

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

1. Если s > fi, возвращаем 0, так как количество задач превысило цель.

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

3. Если s нечетное, можем выполнить только команду «прибавь 1» и вызываем рекурсию: f(s + 1, fi).

4. Если s четное, суммируем два возможных действия:

- f(s + 1, fi) — прибавление 1 задачи;

- f(s * 1.5, fi) — увеличение количества задач в 1.5 раза.

# Рекурсивная функция для подсчета количества последовательностей действий
def f(s, fi):
    # Если текущее количество задач больше целевого, путь невозможен
    if s > fi:
        return 0
    # Если текущее количество задач равно целевому, найден один путь
    if s == fi:
        return 1
    # Если текущее количество задач нечетное, можно только прибавить 1
    if s % 2 != 0:
        return f(s + 1, fi)
    else:
        # Если четное, можно прибавить 1 или увеличить в 1.5 раза
        return f(s + 1, fi) + f(s * 1.5, fi)

# Выводим количество способов, чтобы дойти от 1 до 20
print(f(1, 20))

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

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

1. Инициализируем a[1] = 1.

2. Для чисел от до :

- прибавляем a[i - 1] для команды «прибавь 1»;

- прибавляем a[i - i // 3] для команды «умножь на 1.5», только если делится на (так как , значит делится на 3).

После заполнения массива значение a[20] покажет количество всех последовательностей действий.

# Создаем массив для динамического программирования
a = [0] * 21
# Начальная точка (1 решенная задача) имеет один способ
a[1] = 1
# Заполняем массив для чисел от 2 до 20
for i in range(2, 21):
    # Количество способов через команду +1
    a[i] = a[i - 1]
    # Добавляем путь через команду *1.5, если текущее число делится на 3
    if i % 3 == 0:
        a[i] += a[i - i // 3]
# Выводим количество способов для числа 20
print(a[20])

Решение

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

Мы создаём массив a, где a[i] — количество программ, которые позволяют дойти от исходного числа до числа .

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

2. Проходим по всем числам от 2 до 11 включительно и для каждого числа выполняем три действия:

- a[i + 2] += a[i] — прибавляем все пути, которые достигают , к числу через команду «прибавь 2»;

- a[i + 3] += a[i] — прибавляем пути через команду «прибавь 3»;

- a[i + i - 1] += a[i] — прибавляем пути через команду «прибавь предыдущее», так как третья команда прибавляет число .

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

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

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

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

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

Общее количество программ равно f(2, 11).

# Функция для подсчета количества программ преобразования 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) + f(a + a - 1, b)
# Вычисляем и выводим ответ
print(f(2,11))

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

Определим функцию 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 + 10, b)
# Выводим результат
print(f(12,36))

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

a = [0] * 37 # Создаем список длины 37 с нулями
a[12] = 1
# 12 это наше начало, значит в него прийти можно только одним способом (ставим 1)
# Перебираем все числа от 13 до 36 включительно
for i in range(13, 37):
    # Добавляем к нашему a[i] значения а[i-1] и a[i-10]
    # Если a[i] можно получить шагами +1 и +10, то a[i] увеличивается
    a[i] += a[i - 1]
    a[i] += a[i - 10]
print(a[36]) # Выводим результат

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

Определим функцию 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 + 10, b)
# Выводим результат
print(f(11,27))

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

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

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

Чтобы получить итоговый ответ, выведем количество траекторий дойти до числа 27, начиная заполнять список из позиции 11.

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