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

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

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

1. Аргументы функции:

- a — текущее число на экране.

- c — количество выполненных команд.

- com1 — предпоследняя выполненная команда.

- com2 — последняя выполненная команда.

2. В функции выполняем следующие действия:

- Проверяем, достигли ли мы 11 команд:

- Если c == 11, добавляем текущее число a в множество d для хранения уникальных результатов и выходим из функции.

- Проверяем, не повторяется ли какая-либо команда более двух раз подряд:

- Если com1 == com2 == "1" — команда 1 повторяется дважды, поэтому можно выполнить только команду 2.

- Если com1 == com2 == "2" — команда 2 повторяется дважды, поэтому можно выполнить только команду 1.

- В остальных случаях обе команды доступны, создаем два рекурсивных вызова для команд 1 и 2.

3. Создаем пустое множество d для хранения уникальных значений и запускаем рекурсию с начального числа 1, счетчика команд 0 и пустых последних команд.

4. После завершения рекурсии выводим размер множества d, который соответствует количеству различных значений.

# Создаем пустое множество для хранения уникальных результатов
d = set()

# Рекурсивная функция для перебора всех программ
def f(a, c, com1, com2):
    # Если выполнено 11 команд, добавляем число в множество
    if c == 11:
        d.add(a)
        return
    # Если команда 1 повторяется дважды, выполняем только команду 2
    if com1 == com2 == "1":
        f(a * 2, c + 1, com2, "2")
    # Если команда 2 повторяется дважды, выполняем только команду 1
    elif com1 == com2 == "2":
        f(a + 2, c + 1, com2, "1")
    # Иначе обе команды доступны
    else:
        f(a * 2, c + 1, com2, "2")
        f(a + 2, c + 1, com2, "1")

# Запускаем рекурсию с начального числа 1, 0 команд, пустыми предыдущими командами
f(1, 0, "", "")

# Выводим количество уникальных значений
print(len(d))

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

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

1. Аргументы функции:

- a — текущее число на экране.

- c — количество выполненных команд.

- com — тип предыдущей команды:

- "1"— предыдущая команда была сложением (1 или 2).

- "2"— предыдущая команда была умножением (3 или 4).

- ” — начальное состояние, когда команды еще не выполнялись.

2. В функции выполняем следующие действия:

- Проверяем, не превысили ли количество команд 12:

- Если c > 12, прекращаем выполнение функции.

- Проверяем, достигли ли точно 12 команд:

- Если c == 12, добавляем текущее число a во внешнее множество d и выходим из функции.

- Если c < 12, продолжаем выполнять команды. При этом проверяем ограничение на последовательные одинаковые типы команд:

- Если предыдущая команда была сложением (com == "1"), можно выполнять только команды умножения (*2, *3), чтобы не было двух последовательных сложений.

- Если предыдущая команда была умножением (com == "2"), можно выполнять только команды сложения (+1, +3), чтобы не было двух последовательных умножений.

- Если предыдущей команды не было (com == ), можно выполнить любую команду.

3. Создаем пустое множество d для хранения уникальных значений и запускаем рекурсию с начального числа 6, 0 команд и пустой предыдущей командой.

4. После завершения рекурсии выводим размер множества d, который соответствует количеству различных значений.

# Создаем множество для хранения уникальных результатов
d = set()

# Рекурсивная функция для перебора всех программ
def f(a, c, com):
    # Если число команд больше 12, прекращаем выполнение
    if c > 12:
        return 0
    # Если достигнуто ровно 12 команд, добавляем число в множество
    if c == 12:
        d.add(a)
        return
    # Если команд меньше 12, продолжаем выполнение
    if c < 12:
        # Если предыдущая команда была сложением, выполняем только умножение
        if com == "1":
            f(a * 2, c+1, "2")
            f(a * 3, c+1, "2")
        # Если предыдущая команда была умножением, выполняем только сложение
        elif com == "2":
            f(a + 1, c+1, "1")
            f(a + 3, c+1, "1")
        # Если предыдущей команды не было, выполняем все команды
        else:
            f(a + 1, c+1, "1")
            f(a + 3, c+1, "1")
            f(a * 2, c+1, "2")
            f(a * 3, c+1, "2")

# Запускаем рекурсию с начального числа 6, 0 команд, без предыдущей команды
f(6, 0, "")

# Выводим количество уникальных значений, достигнутых за 12 команд
print(len(d))

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

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

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

d = set() # Создание списка
# Функция для подсчета количества программ преобразования числа a в новые числа, m - число допустимых команд
def f(a, c, m): # c - количество команд
    if c > m: # Если конечное значение больше числа команд, вывести 0
        return 0
    if c == m: # Если конечное значение равно числу команд, вывести список
        d.add(a)
        return
    # Если конечное значение меньше числа команд, выполнить команды
    if c < m:
        f(a + 4, c + 1, m) # Выполним +4 к текущему числу
        f(a * 3, c + 1, m) # Выполним умножение текущего числа
for i in range(11):
    f(5, 0, i) # Найдем все значения не более чем через 10 команд
print(len(d))

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

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

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

d = set() # Создание списка
# Функция для подсчета количества программ преобразования a. с - количество текущих операций. m - допустимое число операций.
def f(a, c, m):
    if c > m: # Если конечное значение больше числа команд, вывести 0
        return 0
    if c == m: # Если конечное значение равно числу команд, вывести список
        d.add(a)
        return
    # Если конечное значение меньше числа команд, выполнить все команды
    if c < m:
        f(a + 1, c + 1, m)
        f(a * 2, c + 1, m)
        f(a * 5, c + 1, m)
for i in range(3, 8): # Сделаем преобразования, используя от 3 до 7 операций
    f(10, 0, i)
print(len(d)) # Ответ

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

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

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

def f(a, b, com = False):
  # Если начальное число равно конечному и одна команда умножения, вывести 1
  if a == b and com == True:
    return 1
  # Если начальное число больше конечного, вывести 0
  if a > b:
    return 0
  # Если команда умножения уже есть, то выполнять только сложение
  if com == True:
    return f(a + 1, b, com) + f(a + 4, b, com) + f(a + 6, b, com)
    # Выполнение основных команд (исключаем умножение, поскольку два раза подряд оно идти не может)
  return f(a + 1, b) + f(a + 4, b) + f(a + 6, b) + f(a * 3, b, True) # Выполнение основных команд
print(f(3, 26)) # Наш ответ

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

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

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

def f(a, b, mult): # а - начальное число, b - конечное, mult - количество умножений
  # Если начальное число равно конечному и число команд умножения меньше или равно 2, вывести 1
  if a == b and mult <= 2:
    return 1
  # Если начальное число больше конечного, вывести 0
  if a > b:
    return 0
    # Если две команды умножения, то выполнять только сложение
  if mult == 2:
    # Выполнение основных команд (исключаем умножение, поскольку три раза подряд оно идти не может)
    return f(a + 1, b, mult) + f(a + 2, b, mult)
  # Выполнение основных команд
  return f(a + 1, b, mult) + f(a + 2, b, mult) + f(a * 2, b, mult + 1)+ f(a * 4, b, mult + 1) # Выполнение основных команд
print(f(1, 13, 0)) # Наш ответ

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

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

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

def f(a, b, two): # two - число цифр 2 в последовательности действий
  # Подсчёт количества цифр 2
  if "2" in str(a):
    two += 1
  # Если начальное число равно конечному и число цифр 2 меньше или равно 1, вывести 1
  if a == b and two <= 1:
    return 1
  # Если начальное число больше конечного и число цифр 2 больше 1, вывести 0
  if a > b or two > 1:
    return 0
  # Выполнение основных команд
  return f(a + 1, b, two) + f(a + 3, b, two) + f(a * 2, b, two)+ f(a * 5, b, two)
print(f(6, 38, 0)) # Наш ответ

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

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

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

def f(a, b, c):
  # Если начальное число равно конечному и число команд меньше или равно 10, вывести 1
  if a == b and c <= 10:
    return 1
  # Если начальное число больше конечного и число команд больше 10, вывести 0
  if a > b or (c > 10):
    return 0
  # Выполнение основных команд
  return f(a + 1, b, c+1) + f(a * 3, b, c + 1) + f(a + (a - 1), b, c + 1)
print(f(7, 75, 0)) # Наш ответ

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

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

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

def f(a, b, c): # a - начальное число, b - конечное, c - текущее число команд
    if a == b: # Если начальное число равно конечному, то вывести 1
        return 1
    if a > b: # Если начальное число больше конечного, то вывести 0
        return 0
    # Проверка того, что первая команда не 3 и не 5
    if c == 2 or c == 4:
        return f(a * 2, b, c + 1) + f(a * 2 + 1, b, c + 1)
    else:
        return f(a + 1, b, c + 1) + f(a * 2, b, c + 1) + f(a * 2 + 1, b, c + 1)
print(f(10, 68, 0))

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

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

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

#определяем функцию
def f(a, b, com): # с - текущая команда
    # Если начальное число равно конечному, то возвращаем 1
    if a == b:
        return 1
    # Если начальное число больше конечного, то возвращаем 0
    if a > b:
        return 0
    # Если номер команды 2 или 3, то можно использовать только 1 команду
    if com == 2 or com == 3:
        return f(a + 3, b, 1)
    # Ссновные команды программы
    return f(a + 3, b, 1) + f(a + a % 10, b, 2) + f(a * 2, b, 3)
# Вывод количества программ, преобразующих число 13 в 52.
print(f(13, 52, 0))

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

Идея решения с помощью рекурсии заключается в том, что мы определяем функцию, которая подсчитывает количество способов преобразовать число в число . Внутри функции задаём три условия: если текущее число превысило , то возвращаем , так как дальнейшие преобразования не имеют смысла; если совпало с , то возвращаем , так как найден корректный путь; если ни одно из этих условий не выполнено, то функция вызывает саму себя дважды — первый раз с аргументом (что соответствует команде "прибавить 2"), второй раз с аргументом (что соответствует команде "умножить на 3"). Таким образом, итоговое количество способов будет равно сумме результатов этих двух рекурсивных вызовов. Запуск функции с начальными значениями даст количество всех программ, которые из числа 7 приводят к числу 77.

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

# Запускаем функцию от 7 до 77 и выводим результат
print(f(7, 77))

—

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

Идея динамического подхода состоит в том, чтобы построить массив, где индекс соответствует числу, а значение по этому индексу показывает количество способов добраться до этого числа. Сначала заполняем массив нулями, а в ячейку с индексом 7 записываем 1, так как изначально мы находимся в числе 7, и существует ровно один способ быть в этом положении. Далее для каждого числа от 8 до 77 вычисляем количество способов добраться до него:

- если в можно попасть из командой "прибавить 2 то добавляем ; - если делится на 3, то в него можно попасть из командой "умножить на 3 и тогда добавляем ; - иначе такой переход невозможен.

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

# Создаем массив из 80 элементов, все значения изначально равны 0
a = [0] * 80
# В ячейку с индексом 7 записываем 1, так как стартуем с числа 7
a[7] = 1
# Перебираем все числа от 8 до 77
for i in range(8, 78):
    # В число i можно попасть двумя способами:
    # 1) из i-2 командой "прибавить 2"
    # 2) из i//3 командой "умножить на 3", только если i делится на 3
    a[i] = a[i - 2] + a[i // 3] * (i % 3 == 0)

# Выводим количество программ, которые ведут от 7 к 77
print(a[77])

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

Идея рекурсивного решения заключается в том, чтобы построить функцию, которая считает количество различных программ, преобразующих число в число . На каждом шаге проверяются условия: если текущее число стало меньше числа , то дальнейшие преобразования невозможны и возвращается ; если совпало с , то найден один корректный путь, и функция возвращает ; если ни одно из условий не выполнено, то функция вызывает саму себя дважды — первый раз с аргументом , что соответствует команде «уменьшить на 2», второй раз с аргументом , что соответствует команде «поделить нацело на 3». Результаты этих двух вызовов складываются, чтобы получить общее количество программ. Таким образом, при вызове функции f(123, 2) она будет рекурсивно перебирать все возможные последовательности команд и возвращать итоговое число способов преобразования.

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

# Запускаем функцию от 123 до 2 и выводим результат
print(f(123,2))

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

Рекурсивный способ решения заключается в определении функции, которая считает количество программ, преобразующих число в число . Логика работы функции следующая: если текущее число превысило , то возвращаем , так как большее число уже нельзя уменьшить до нужного, следовательно, пути не существует. Если совпало с , то возвращаем , так как найден один корректный путь. В остальных случаях функция вызывает саму себя трижды: с аргументом (команда «прибавить 2»), с аргументом (команда «прибавить 3») и с аргументом (команда «умножить на 4»). Полученные значения суммируются, так как каждая из ветвей даёт количество различных программ. По условию траектория должна содержать число , поэтому итоговое количество программ вычисляется как произведение значений и : первая часть считает количество способов дойти от 2 до 16, вторая — от 16 до 26, а произведение этих чисел даёт ответ, потому что для каждого пути из первой части можно выбрать любой путь из второй.

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

# Условие требует прохождения через число 16,
# поэтому результат равен произведению двух этапов:
# от 2 до 16 и от 16 до 26
print(f(2,16)*f(16,26))

—

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

Динамический способ решения основывается на том, что мы последовательно заполняем массив, где индекс соответствует числу, а значение по индексу обозначает количество программ, ведущих в это число. Сначала создаём массив из нулей, в ячейку с индексом 2 записываем 1, так как изначально исполнитель находится в числе 2 и существует ровно один способ быть в этой позиции. Далее последовательно рассматриваем все числа от 3 до 26 и для каждого вычисляем количество способов попасть в него. Для этого проверяем:

- если в число можно попасть из , то прибавляем ; - если в число можно попасть из , то прибавляем ; - если число делится на 4, то в него можно попасть умножением предыдущего числа на 4, и тогда прибавляем .

Особенность задачи заключается в обязательном включении числа 16 в траекторию. Для этого, как только индекс достигает 16, мы обнуляем все значения массива для индексов меньше 16, так как они относятся к путям, не содержащим число 16. В результате сохраняются только те траектории, которые проходят через 16, и дальнейший счёт будет идти только от числа 16 к 26. Окончательный ответ находится в .

# Создаем массив для хранения количества путей, изначально все нули
a = [0] * 35
# В ячейку с индексом 2 записываем 1,
# так как начальное число равно 2
a[2] = 1
# Перебираем числа от 3 до 26 включительно
for i in range(3, 27):
    # В число i можно попасть из i-2 и i-3,
    # а также из i//4, если i делится на 4
    a[i] = a[i - 2] + a[i - 3] + a[i // 4] * (i % 4 == 0)
    # Когда достигли числа 16,
    # нужно оставить только пути, которые его содержат,
    # поэтому все значения для индексов меньше 16 обнуляем
    if i == 16:
        for j in range(i):
            a[j] = 0

# В ячейке с индексом 26 теперь хранится количество программ
# от 2 до 26 с обязательным прохождением через 16
print(a[26])

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

Рекурсивное решение строится на определении функции, которая подсчитывает количество способов преобразовать число в число с помощью доступных команд. Внутри функции выполняются проверки: если число стало больше числа , то дальнейшие действия не имеют смысла, поэтому возвращаем ; если оказалось равным запрещённому числу , то также возвращаем , так как такая траектория не подходит; если совпало с , то найден один правильный путь и функция возвращает ; если ни одно из условий не выполнено, то выполняем три рекурсивных вызова: соответствует команде «прибавить 2», соответствует команде «прибавить 3», соответствует команде «возвести в квадрат». Результат работы функции складывает все найденные пути. Запуск функции f(2, 33) подсчитает количество программ, которые преобразуют 2 в 33, не заходя в число 16.

# Импортируем декоратор lru_cache, чтобы запоминать
# результаты предыдущих вызовов функции и не пересчитывать их заново
from functools import lru_cache

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

# Запускаем функцию от 2 до 33 и выводим результат
print(f(2,33))

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

Рекурсивный способ решения заключается в построении функции f(a, b), которая считает количество различных программ преобразования числа в число . На каждом шаге функция проверяет условия: если текущее число превысило целевое или оказалось чётным, то такая траектория невозможна и возвращается ; если совпадает с , значит найден правильный путь, возвращается ; если ни одно из условий не выполнено, то функция вызывает саму себя для четырёх возможных переходов. Первый вызов соответствует команде «прибавить 1» (f(a+1, b)), второй — «прибавить 2» (f(a+2, b)), третий — «умножить на 3» (f(a*3, b)), четвёртый — «прибавить до кратного 3», то есть f(a + (3 - a%3), b). Результат вычислений складывается, так как каждый вариант задаёт отдельную программу. Таким образом, при вызове f(3, 77) происходит полный перебор всех допустимых траекторий с учётом ограничения, что на пути не встречаются чётные числа.

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

# Запускаем функцию от 3 до 77 и выводим количество программ
print(f(3,77))

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

Идея рекурсивного решения заключается в том, чтобы определить функцию f(a, b), которая будет подсчитывать количество программ, преобразующих число в число . Для этого на каждом шаге функции проверяются условия: - Если текущее число стало меньше числа , то дальнейшие команды не приведут к цели, и функция возвращает . - Если равно , значит найден один корректный путь, и функция возвращает . - Если ни одно из условий не выполнено, функция рекурсивно вызывает себя трижды: 1) с аргументом , что соответствует команде «уменьши на 1»; 2) с аргументом , что соответствует команде «уменьши на 4»; 3) с аргументом , что соответствует команде «подели нацело на 2».

Сумма этих трёх вызовов даёт общее количество программ для данного промежутка. Так как траектория должна проходить через числа 56, 30 и 18, мы разбиваем общий путь на этапы: от 60 до 56, от 56 до 30, от 30 до 18 и от 18 до 10, и перемножаем результаты всех этапов.

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

# Перемножаем результаты всех этапов, чтобы учесть прохождение
# через числа 56, 30 и 18, и выводим общее количество программ
print(f(60,56)*f(56,30)*f(30,18)*f(18,10))

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

Идея рекурсивного решения заключается в построении функции, которая считает количество программ, переводящих число в число . Функция проверяет три условия: - если текущее число больше или равно запрещённому числу 33, то путь невозможен и возвращаем ; - если совпало с , то найден подходящий путь, возвращаем ; - если ни одно из условий не выполнено, вызываем функцию рекурсивно трижды: для команды "прибавить 2 для команды "прибавить 3 для команды "умножь на 4".

Затем суммируем все результаты для всех от 50 до 60, чтобы получить общее количество программ.

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

# Переменная для накопления общего числа программ
c = 0
# Перебираем все целевые числа от 50 до 60 включительно
for i in range(50,61):
    # Добавляем количество программ, которые переводят 12 в i
    c += f(12,i)

# Выводим итоговое количество программ
print(c)

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

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

- если текущее число больше или равно запрещённым числам 42 или 56, путь невозможен и функция возвращает 0; - если текущее число совпало с целевым , значит найден корректный путь и функция возвращает 1; - в остальных случаях функция вызывает саму себя четыре раза, соответствуя четырём командам: прибавляем 2, прибавляем 5, умножаем на 3 и прибавляем до ближайшего кратного 2 (вычисляется как ), затем суммируем результаты этих вызовов, чтобы получить общее количество программ.

Так как в условии задачи траектория должна содержать числа 15 и 23, а запрещены числа 42 и 56, для подсчёта общего количества программ решение разделяется на три этапа: от 4 до 15, от 15 до 23 и от 23 до 66. Результаты этапов перемножаются, так как для каждого пути первой части можно выбрать любой путь из второй и третьей частей. Для ускорения рекурсии используется декоратор lru_cache, который запоминает уже вычисленные значения функции.

# Импортируем lru_cache для запоминания результатов рекурсивных вызовов
from functools import lru_cache

# Определяем рекурсивную функцию f(a, b) с декоратором lru_cache
@lru_cache(None)
def f(a,b):
    # Если текущее число больше целевого или равно запрещённым числам 42 или 56,
    # путь невозможен, возвращаем 0
    if a > b or a == 42 or a == 56:
        return 0
    # Если текущее число совпало с целевым числом b,
    # значит найден подходящий путь, возвращаем 1
    if a == b:
        return 1
    # В остальных случаях считаем все возможные переходы:
    # 1) прибавить 2
    # 2) прибавить 5
    # 3) умножить на 3
    # 4) прибавить до ближайшего кратного 2 (не ноль)
    # Складываем количество способов из всех этих переходов
    return f(a+2,b) + f(a+5,b) + f(a*3,b) + f(a+(2-a%2),b)

# Вычисляем общее количество программ с учётом обязательных чисел в траектории
# Считаем отдельно путь от 4 до 15, от 15 до 23 и от 23 до 66, затем перемножаем результаты
print(f(4,15) * f(15,23) * f(23,66))

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

Идея рекурсивного решения заключается в построении функции, которая подсчитывает количество программ, преобразующих число в число , проверяя при этом условия задачи. На каждом шаге функции проверяется:

- если текущее число стало больше целевого , дальнейшие преобразования невозможны, возвращаем ;

- если текущее число кратно 5, то траектория нарушает условие задачи, возвращаем ;

- если текущее число равно , значит найден корректный путь, возвращаем ;

- если ни одно из условий не выполнено, функция рекурсивно вызывает саму себя дважды: первый раз с (команда "прибавить 4"), второй раз с (команда "прибавить 5"), и складывает результаты этих вызовов, чтобы получить общее количество программ.

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

    # Если текущее число равно целевому, найден путь
    if a == b:
        return 1  # Возвращаем 1, увеличивая счетчик корректных траекторий

    # В остальных случаях рекурсивно суммируем количество траекторий
    # для двух возможных команд: прибавить 4 и прибавить 5
    return f(a + 4, b) + f(a + 5, b)

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

—

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

Идея динамического решения состоит в построении массива, где индекс соответствует числу, а значение по этому индексу показывает количество траекторий, ведущих к этому числу, начиная с числа 31. Сначала создаём массив длиной , заполненный нулями, и устанавливаем , так как существует ровно один способ находиться в начальном числе. Далее проходим циклом по всем числам от 32 до 113 и вычисляем количество траекторий для каждого числа:

- если число не кратно 5, значит в него можно попасть;

- количество программ для числа равно сумме программ для и , так как это соответствующие команды прибавления.

Итоговое количество программ хранится в .

# Создаем массив для хранения количества программ для всех чисел до 113
a = [0] * (113 + 1)  # Индексы от 0 до 113
# Начальное число 31 имеет одну траекторию
a[31] = 1

# Перебираем числа от 32 до 113 включительно
for i in range(32, 113 + 1):
    # Проверяем условие: число не должно быть кратно 5
    if i % 5 != 0:
        # Количество программ для числа i равно сумме
        # программ для i-4 и i-5
        a[i] = a[i - 4] + a[i - 5]

# Выводим количество программ, ведущих от 31 к 113
print(a[113])