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

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

Мы используем рекурсивный метод, разделяя вычисления на два этапа: от исходного числа 3 до числа 11 и от числа 11 до числа 23. Сначала определяем функцию f(x, y), которая считает количество программ, преобразующих число в число с учётом всех ограничений.

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

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

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

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

Так как траектория должна содержать число 11, мы умножаем количество программ от 3 до 11 на количество программ от 11 до 23.

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

# Общее количество программ равно произведению числа программ от 3 до 11 и от 11 до 23
print(f(3, 11) * f(11, 23))

—

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

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

1. Инициализируем массив нулями и записываем в a[3] = 1, так как начинаем с числа 3.

2. Перебираем числа от 4 до 23 и для каждого числа выполняем:

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

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

- Если равно 13 или 18, обнуляем a[i], так как эти числа запрещены в траектории.

3. После прохода по всем индексам, количество программ, приводящих от 3 к 23 с учётом условий, хранится в a[23].

# Создаем массив из 24 элементов, все значения равны 0
a = [0] * 24
# Начальное число 3, один путь к нему
a[3] = 1
# Перебираем числа от 4 до 23
for i in range(4, 24):
    # Считаем количество программ из i-4, i-5 и i//2
    a[i] = a[i - 4] + a[i - 5] + a[i // 2] * (i % 2 == 0)
    # Если достигли числа 11, обнуляем все предыдущие элементы массива
    if i == 11:
        for j in range(i):
            a[j] = 0
    # Если число запрещено (13 или 18), обнуляем его
    if i == 13 or i == 18:
        a[i] = 0

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

Решение аналитически

Составим формулы для решения этой задачи:

— если число не делится на 2.

— если число делится на 2.

Заметим, что число 3 мы получаем одним способом — пустой программой. Числа 4, 5 мы получить не можем данными командами. Заполним таблицу:

Пусть — количество программ, которые число 1 преобразуют в число n. Тогда верно следующее утверждение:

Заполним таблицу по данной формуле до 7:

По условию сказано, что траектория должна содержать число 8, значит , так как число 9 можем получить только первой командой.

Продолжим заполнять таблицу:

В условии сказано, что траектория не содержит число 14. Значит .

Заполним таблицу до конца:

Отсюда получаем ответ — 840.

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

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

1. Сначала мы проверяем, нарушает ли текущее число условия задачи: - если текущее число превысило целевое число , дальнейшие шаги невозможны, возвращаем 0; - если текущее число равно запрещённым значениям (например, 14, которое не должно встречаться в траектории), путь недопустим, возвращаем 0.

2. Если текущее число совпало с целевым числом , значит, мы нашли корректную программу, возвращаем 1.

3. В остальных случаях считаем все возможные варианты продолжения программы: - прибавляем 1 к числу и вызываем рекурсию; - прибавляем 2 к числу и вызываем рекурсию; - суммируем результаты этих вызовов, чтобы получить общее количество программ, ведущих от к .

4. Так как траектория должна содержать число 8, но не содержать число 14, мы делим задачу на два этапа: - первый этап: от 1 до 8 с проверкой запрета числа 14; - второй этап: от 8 до 19 с проверкой запрета числа 14; - общее количество программ равно произведению результатов двух этапов, так как для каждого пути первой части можно использовать любой путь второй части.

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

# Вычисляем количество программ с учётом условия траектории:
# первый этап: от 1 до 8
# второй этап: от 8 до 19
# Общее количество программ равно произведению двух этапов
print(f(1, 8) * f(8, 19))

Составим формулы для решения этой задачи:

— если число не делится на 2.

— если число делится на 2.

Заполним таблицу:

Так как траектория должна прохоить через число 13, то все последующие числа мы можем получить только через него. Продолжим заполнять таблицу:

Аналогично траектория должна проходить через число 25. Заполним таблицу до конца, учитывая, что траектория не должна проходить через числа 28 и 31. Значит и .

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

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

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

# Функция для подсчета количества программ преобразования a -> b
def f(x, y):
    if x > y or x == 28 or x == 31:  # Если число стало больше нужного или 28 или 31
        return 0
    if x == y: # Если дошли до нужного числа
        return 1
    return f(x + 1, y) + f(x + 3, y) + f(x + 5, y) + f(x * 2, y) # Количество путей до текущего числа

print(f(1, 13) * f(13, 25) * f(25, 32)) # Найдем ответ по условию задачи

Составим формулы для решения этой задачи:

— если число не делится ни на 2, ни на 3.

— если число не делится на 3.

— если число не делится на 2.

— если число делится на 2 и на 3.

Заполним таблицу по данным формулам и со всеми условиями траектории.

Так как траектория должна проходить через число 17, то последующие числа мы можем получить только командой 1. Количество программ изменится только на . Отсюда следует, что ответ 20.

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

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

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

# Функция для подсчета количества программ преобразования a -> b
def f(c, m):
    if c > m or c == 11 or c == 14: # Если число стало больше нужного или 11 или 14
        return 0
    if c == m: # Если дошли до нужного числа
        return 1
    return f(c + 1, m) + f(c * 2, m) + f(c * 3, m) # Количество путей до текущего числа

print(f(1, 17) * f(17, 32)) # Найдем ответ по условию задачи

Пусть — количество программ, которые число 1 преобразуют в число n. Тогда верно следующее утверждение:

— если число не делится на 3.

— если число делится на 3.

Заполним таблицу по формулам до 11:

По условию сказано, что траектория должна содержать число 12. Значит , так как число 13 можно получить только командой 1.

Продолжим заполнять таблицу:

По услолвию сказано, что траектория не должна содержать число 27. Значит .

Заполним таблицу до конца:

Отсюда получаме ответ — 27343

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

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

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

# Функция для подсчета количества программ преобразования a -> b
def f(c, m):
    if c > m or c == 27: # Если число стало больше нужного или 27
        return 0
    if c == m: # Если дошли до нужного числа
        return 1
    return f(c + 1, m) + f(c + 3, m) + f(c * 3, m) # Количество путей до текущего числа

print(f(2, 12) * f(12, 33)) # Найдем ответ по условию задачи. Умножаем пути, чтобы учесть в подсчётах число 12.

Пусть — количество программ, которые число 1 преобразуют в число n. Тогда верно следующее утверждение:

— если число не делится на 2.

— если число делится на 2.

Заполним таблицу по данной формуле до 6:

Так как по условию сказано, что траектория должна содержать число 6, значит последующие числа мы можем получать только из 6. Продолжим заполнять таблицу:

Аналогично с 9. Сразу можно сказать, что число 13 нельзя никак получить, так как по условию траектория не должна через него проходить. Значит . Заполним таблицу до конца:

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

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

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

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

print(f(1, 6) * f(6, 9) * f(9, 15)) # Найдем ответ по условию задачи

Составим формулы:

— если число не делится на 2.

— если число делится на 2.

Заметим, что количество программ будет меняться только на числах кратных 5. Заполним таблицу по данным формулам, учитывая условия траектории:

Лютик точно будет спасён!

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

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

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

# Функция для подсчета количества программ преобразования a -> b
def f(c, m):
    if c > m or c == 25 or c == 40: # Если число стало больше нужного или 25 или 40
        return 0
    if c == m: # Если дошли до нужного числа
        return 1
    return f(c + 5, m) + f(c + 10, m) + f(c * 2, m) # Количество путей до текущего числа

print(f(15, 50) * f(50, 100)) # Найдем ответ по условию задачи. Умножение позволяет гарантированно учесть число 50 в подсчётах.

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

Мы используем динамическое программирование, чтобы посчитать количество программ, которые приводят число 1 к числу 16, учитывая ограничения на числа 8 и 10. Идея заключается в том, чтобы создать массив, где индекс соответствует числу на экране, а значение в ячейке — количество способов добраться до этого числа, используя команды.

1. Создаем массив a из 17 элементов (от 0 до 16) и заполняем нулями.

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

3. Проходим по всем числам от 2 до 16:

- Сначала добавляем количество способов прийти из командой «прибавить 1» (a[i] = a[i-1]).

- Если , добавляем количество способов из командой «прибавить 5» (a[i] += a[i-5]).

- Если четное, добавляем количество способов из командой «умножить на 2» (a[i] += a[i//2]).

- Если , обнуляем ячейку a[i] = 0, так как число 10 запрещено.

- Если , обнуляем все ячейки перед 8 (for j in range(8): a[j] = 0), чтобы гарантировать, что траектория обязательно содержит число 8.

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

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

—

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

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

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

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

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

- f(x+1, y) — добавление 1

- f(x*2, y) — умножение на 2

- f(x+5, y) — добавление 5

Так как траектория должна проходить через число 8, мы делим задачу на два этапа: от 1 до 8 и от 8 до 16. Итоговое количество программ равно произведению результатов двух этапов: f(1,8) * f(8,16).

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

# Вычисляем количество программ, проходящих через 8
print(f(1, 8) * f(8, 16))

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

Мы решаем задачу рекурсивно, создавая функцию f(x, y), которая считает количество программ, преобразующих число в число . 1. Сначала проверяем, нарушает ли текущее число условие задачи: - Если , то дальнейшие преобразования уже не приведут к числу , поэтому возвращаем 0. - Если , то траектория запрещена по условию задачи, возвращаем 0. 2. Проверяем, достигли ли мы цели: - Если , значит найден один корректный путь, возвращаем 1. 3. Если ни одно из условий не выполнено, считаем все возможные переходы из текущего числа: - Прибавляем 1 и вызываем f(x + 1, y) - Умножаем на 2 и вызываем f(x * 2, y) - Умножаем на 3 и вызываем f(x * 3, y) - Складываем результаты всех трёх вызовов, чтобы получить общее количество программ.

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

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

# Вычисляем количество программ от 1 до 14 и от 14 до 50
# и перемножаем результаты, так как траектория должна проходить через 14
print(f(1, 14) * f(14, 50))

—

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

Мы решаем задачу динамическим способом, создавая массив a длиной 51 (для чисел от 0 до 50), где a[i] хранит количество программ, которые преобразуют число 1 в число .

1. Инициализируем массив нулями: a = [0]*51 2. Задаём начальное положение: a[1] = 1, так как изначально мы находимся в числе 1. 3. Перебираем числа от 2 до 50: - Для каждого числа i добавляем количество программ, ведущих в i из i-1 (команда +1): a[i] = a[i-1] - Если i делится на 2, добавляем количество программ, ведущих в i из i//2 (команда *2): a[i] += a[i//2] - Если i делится на 3, добавляем количество программ, ведущих в i из i//3 (команда *3): a[i] += a[i//3] - Если i = 14, нужно сбросить все значения для чисел меньше 14, так как траектория до 14 должна быть из 1 без промежуточного попадания в запрещенные числа: for j in range(14): a[j] = 0 - Если i = 16, обнуляем a[i] по условию запрета на число 16: a[i] = 0

4. После прохода по всем числам a[50] содержит количество программ от 1 до 50 с учётом всех условий.

# Создаем массив для чисел от 0 до 50, изначально заполненный нулями
a = [0]*51
# Начальное положение — число 1
a[1] = 1
# Перебираем числа от 2 до 50 включительно
for i in range(2, 51):
    # Добавляем количество программ, ведущих из i-1
    a[i] = a[i-1]
    # Добавляем количество программ, ведущих из i//2, если возможно
    if i % 2 == 0:
        a[i] += a[i//2]
    # Добавляем количество программ, ведущих из i//3, если возможно
    if i % 3 == 0:
        a[i] += a[i//3]
    # Если достигли числа 14, обнуляем все числа меньше 14
    if i == 14:
        for j in range(14):
            a[j] = 0
    # Если число 16 запрещено, обнуляем его
    if i == 16:
        a[i] = 0

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

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

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

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

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

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

- прибавить 1 (x + 1)

- прибавить 2 (x + 2)

- умножить на 3 (x * 3)

Итоговое количество программ, которые проходят через число 10 и не содержат 14, получается произведением f(2, 10) и f(10, 15), так как каждая траектория до 10 может соединяться с любой траекторией от 10 до 15.

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

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

—

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

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

1. Инициализируем массив нулями: a = [0]*16, так как максимальное число, которое нам нужно рассчитать, 15.

2. Устанавливаем исходное положение: a[2] = 1, так как стартуем с числа 2 и существует ровно один способ быть в этом положении.

3. Для каждого числа i от 3 до 15 включительно:

- добавляем количество способов из предыдущих чисел, если можно добраться командой +1 или +2: a[i] = a[i-1] + a[i-2]

- если i делится на 3, прибавляем количество способов, приходящих из i//3: if i % 3 == 0: a[i] += a[i//3]

- если i == 10, обнуляем все предыдущие значения, чтобы обеспечить прохождение через 10: for j in range(1, i): a[j] = 0

- если i == 14, запрещенное число, обнуляем a[i]

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

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

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

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

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

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

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

- прибавить 1 (x + 1)

- прибавить 3 (x + 3)

- умножить на 4 (x * 4)

Так как траектория должна содержать число 12, общее количество программ вычисляется как произведение f(3, 12) и f(12, 20).

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

# Вычисляем количество программ: сначала от 3 до 12, затем от 12 до 20
print(f(3, 12) * f(12, 20))

—

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

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

1. Инициализируем массив нулями: a = [0]*21, так как максимальное число 20.

2. Устанавливаем стартовое положение: a[3] = 1, так как начинаем с числа 3.

3. Для каждого числа i от 4 до 20 включительно:

- добавляем количество способов, приходящих из i-1 и i-3 (команды +1 и +3): a[i] = a[i-1] + a[i-3]

- если i делится на 4, учитываем команду умножить на 4: if i % 4 == 0: a[i] += a[i//4]

- если i == 12, обнуляем все предыдущие значения, чтобы обеспечить прохождение через 12: for j in range(i): a[j] = 0

- если i == 7, запрещенное число, обнуляем a[i]

После завершения цикла a[20] содержит количество программ, которые преобразуют 3 в 20, проходя через 12 и не содержат 7.

# Создаем массив для хранения количества программ для каждого числа
a = [0]*21
# Стартовое число 3 имеет один способ
a[3] = 1
# Проходим по всем числам от 4 до 20
for i in range(4, 21):
    # Считаем количество программ, приходящих через +1 и +3
    a[i] = a[i-1] + a[i-3]
    # Если число делится на 4, учитываем команду *4
    if i % 4 == 0:
        a[i] += a[i//4]
    # Обеспечиваем прохождение через число 12
    if i == 12:
        for j in range(i):
            a[j] = 0
    # Запрещенное число 7 обнуляем
    if i == 7:
        a[i] = 0
# Выводим количество программ, приводящих 3 к 20 с условием задачи
print(a[20])

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

Мы используем рекурсивный подход для подсчета количества программ. Основная идея: создаем функцию, которая считает количество программ, преобразующих число в число , учитывая ограничения на числа, которые нельзя проходить. В функции проверяем следующие условия:

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

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

3. Если текущее число меньше целевого, то функция вызывает саму себя для каждого возможного действия:

- прибавить 1 к числу,

- прибавить 3 к числу,

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

Мы разделяем вычисление на два этапа: от начального числа 3 до промежуточного 12 и от 12 до конечного 20. Количество программ на каждом этапе подсчитывается рекурсивно. Итоговое количество программ вычисляется как произведение числа способов для первой и второй части, так как каждый путь из первой части можно соединить с любым путем второй части.

# Функция для перевода числа в шестнадцатеричную или другую систему счисления
def perevod(n):
    # Инициализируем пустую строку для хранения результата
    s = ’’
    # Пока число не равно 0
    while n != 0:
        # Получаем остаток от деления на 6 и добавляем к строке слева
        s = str(n % 6) + s
        # Делим число на 6 целочисленно
        n //= 6
    # Возвращаем строковое представление числа
    return s

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

# Вычисляем произведение количества программ на двух этапах
# от 3 до 10 (соответствует 12) и от 10 до 45 (соответствует 20)
print(perevod(f(3, 10) * f(10, 45)))

—

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

Мы используем динамическое программирование для подсчета количества программ. Создаем массив, где индекс соответствует числу на экране, а значение — количеству способов достичь этого числа. Сначала заполняем массив нулями и устанавливаем значение для начального числа 3 как 1, так как изначально мы находимся в этом числе. Далее перебираем все числа от 4 до 45 и обновляем количество способов для каждого числа:

- прибавляем количество способов попасть из ,

- если число делится на 2, прибавляем количество способов попасть из ,

- если число равно запрещенному 15, обнуляем значение,

- если число равно промежуточному 10 (соответствует 12), обнуляем все предыдущие ячейки, чтобы исключить траектории, не проходящие через 12.

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

# Функция для перевода числа в систему счисления с основанием a
def perevod(n, a):
    # Инициализируем пустую строку
    s = ’’
    # Пока число не равно 0
    while n != 0:
        # Получаем остаток от деления на a и добавляем к строке слева
        s = str(n % a) + s
        # Делим число на a целочисленно
        n //= a
    # Возвращаем строковое представление числа
    return s

# Создаем массив для хранения количества программ
a = [0]*46
# Устанавливаем начальное число 3 как 1
a[3] = 1
# Перебираем числа от 4 до 45
for i in range(4, 46):
    # Любое число можно получить прибавлением 1 к предыдущему
    a[i] = a[i-1]
    # Если число делится на 2, можно попасть из i//2
    if i % 2 == 0:
        a[i] += a[i//2]
    # Если число равно запрещенному 15, путь невозможен
    if i == 15:
        a[i] = 0
    # Если число равно промежуточному 10, обнуляем все предыдущие пути
    if i == 10:
        for j in range(i):
            a[j] = 0
# Выводим количество программ в шестиричной системе
print(perevod(a[45], 6))

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

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

1. Сначала мы проверяем базовые случаи:

- Если текущее число s превысило целевое fi, путь невозможен, возвращаем 0.

- Если текущее число равно 99, путь запрещён, возвращаем 0.

- Если текущее число равно 50, отмечаем флаг flag = True, чтобы зафиксировать, что условие "траектория содержит 50"выполнено.

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

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

- прибавляем 2 (s + 2)

- умножаем на 3 (s * 3)

3. Суммируем результаты этих вызовов и возвращаем как общее количество программ.

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

# Запускаем функцию с начальным числом 10, целевым 100 и флагом False
print(f(10, 100, False))

—

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

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

1. Создаём массив длиной 101 (от 0 до 100) и заполняем его нулями.

2. Начальное число 10 имеет один способ быть достигнутым, поэтому a[10] = 1.

3. Проходим по всем числам от 11 до 100 включительно:

- Считаем количество программ, которые ведут в число i из числа i-2 командой "прибавить 2".

- Если i делится на 3, добавляем a[i//3], так как можно прийти командой "умножить на 3".

- Если число равно 99, обнуляем a[i], так как траектория через 99 запрещена.

- Если число равно 50, обнуляем все предыдущие значения a[j] для j < 50, чтобы обеспечить прохождение через 50.

4. В конце a[100] содержит количество программ, соответствующих условиям.

# Создаем массив для подсчета количества программ для чисел от 0 до 100
a = [0] * 101
# Начальное число 10 имеет один способ быть достигнутым
a[10] = 1
# Перебираем все числа от 11 до 100
for i in range(11, 101):
    # Количество программ для числа i складывается из:
    # 1) прибавить 2
    # 2) умножить на 3, если i делится на 3
    a[i] = a[i - 2] + a[i // 3] * (i % 3 == 0)
    # Если число равно запрещенному 99, путь невозможен
    if i == 99:
        a[i] = 0
    # Если число равно 50, обнуляем все предыдущие значения,
    # чтобы гарантировать, что траектория проходит через 50
    if i == 50:
        for j in range(i):
            a[j] = 0

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

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

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

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

2. Если совпало с , значит мы нашли корректную программу, и функция возвращает 1.

3. Если ни одно из этих условий не выполнено, то мы пробуем все три возможные команды: прибавляем 3, умножаем на 2 и возводим в третью степень, вызывая функцию рекурсивно для каждого из этих вариантов. Итоговое количество программ получается суммой результатов всех трёх рекурсивных вызовов.

Поскольку траектория должна содержать число 12, мы делим задачу на два этапа: от 3 до 12 и от 12 до 96. Общее количество программ равно произведению количества программ каждого этапа, так как для каждого пути из первой части можно выбрать любой путь из второй части.

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

# Вычисляем количество программ как произведение этапов:
# от 3 до 12 и от 12 до 96
print(f(3, 12) * f(12, 96))

—

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

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

1. Инициализируем массив нулями.

2. Записываем a[3] = 1, так как стартуем с числа 3, существует ровно один способ находиться в этом положении.

3. Перебираем числа i от 4 до 96 включительно и для каждого числа:

- Добавляем a[i-3], чтобы учесть команду "прибавить 3".

- Если число делится на 2, добавляем a[i//2], чтобы учесть команду "умножить на 2".

- Вычисляем кубический корень числа i, если его куб равен i, добавляем a[x], чтобы учесть команду "возвести в третью степень".

4. Если i == 12, обнуляем все предыдущие значения a[j] для , так как траектория должна содержать число 12.

5. Если i == 25, обнуляем a[i], чтобы исключить запрещённое число из траектории.

В конце a[96] содержит количество программ, которые из числа 3 приводят к числу 96 с учётом всех условий.

# Создаем массив из 97 элементов, все значения изначально равны 0
a = [0] * 97
# В ячейку с индексом 3 записываем 1, так как стартуем с числа 3
a[3] = 1
# Перебираем все числа от 4 до 96 включительно
for i in range(4, 97):
    # Для числа i добавляем количество способов прийти командой "прибавить 3"
    a[i] = a[i - 3] + a[i // 2] * (i % 2 == 0)
    # Проверяем, можно ли прийти командой "возвести в третью степень"
    x = int(i ** (1 / 3))
    if x ** 3 == i:
        a[i] += a[x]
    # Если дошли до 12, обнуляем все предыдущие значения, чтобы траектория содержала 12
    if i == 12:
        for j in range(i):
            a[j] = 0
    # Если число 25, обнуляем его значение, так как оно запрещено
    if i == 25:
        a[i] = 0
# Выводим количество программ, которые приводят от 3 к 96
print(a[96])

Стоит сказать, что динамическое решение данной задачи более трудоемкое и занимает большее количество времени для исполнения. Поэтому рекомендуется использовать именно рекурсивную реализацию.

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

Мы используем рекурсивную функцию f(st, fn, flag, flag_number, count, end_count), которая подсчитывает количество программ из текущего числа st в целевое число fn.

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

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

- fn — целевое число, которое должно получиться после выполнения всех команд.

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

- flag_number — число, через которое должна пройти траектория (в данном случае 15).

- count — количество выполненных команд на текущий момент.

- end_count — общее количество команд в программе (20).

2. Логика работы функции:

- Если текущее число равно целевому fn, количество команд достигло end_count, и флаг flag установлен (число 15 уже встречалось), возвращаем 1 — найден подходящий путь.

- Если текущее число больше целевого или количество команд превышает end_count, возвращаем 0 — путь недопустим.

- Если текущее число равно проверочной точке flag_number, устанавливаем флаг flag = True.

- Рекурсивно считаем количество путей для всех трёх команд:

- st + 1 — прибавить 1.

- st * 2 — умножить на 2.

- st + st * 0.75 — прибавить к числу 0.75 его самого, учитываем только если st % 8 == 0 (для этого умножаем на булеву проверку (st % 8 == 0)).

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

3. Запускаем рекурсию с исходного числа 3, целевого числа 50, флага False, проверочной точки 15, текущего количества команд 0 и общего числа команд 20.

# Рекурсивная функция для подсчета количества программ
def f(st, fn, flag, flag_number, count, end_count):
    # Проверка, достигли ли мы цели при полном количестве команд и посещении проверочной точки
    if st == fn and count == end_count and flag:
        return 1
    # Проверка выхода за пределы целевого числа или превышения количества команд
    if st > fn or count > end_count:
        return 0
    # Установка флага при достижении проверочной точки
    if st == flag_number:
        flag = True
    # Рекурсивные вызовы для всех команд
    x = f(st + 1, fn, flag, flag_number, count + 1, end_count)  # Команда 1: прибавить 1
    y = f(st * 2, fn, flag, flag_number, count + 1, end_count)  # Команда 3: умножить на 2
    z = f(st + st * 0.75, fn, flag, flag_number, count + 1, end_count) * (st % 8 == 0)
    # Команда 2: прибавить 0.75 числа, если число кратно 8
    # Суммируем результаты всех возможных переходов
    return x + y + z

# Запуск функции с исходного числа 3 и целевого числа 50
print(f(3, 50, False, 15, 0, 20))

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

Мы используем динамический способ, создавая список ans, где каждая пара (число, флаг) показывает текущее число на экране и информацию о том, достигнута ли проверочная точка 15.

1. Инициализация:

- В список ans добавляем исходное число 3 с флагом 0, что означает, что проверочная точка ещё не достигнута.

2. Основной цикл:

- Для каждой из 20 команд создаём новый список can_get, который будет хранить все возможные значения после применения команд.

- Для каждой пары (a, flag) из ans:

- Если a + 1 == 15, добавляем (a + 1, 1), иначе (a + 1, flag).

- Если a % 8 == 0, проверяем команду 2:

- Если int(a + a * 0.75) == 15, добавляем (int(a + a * 0.75), 1), иначе (int(a + a * 0.75), flag).

- Для команды 3 добавляем (a * 2, flag).

- После обработки всех чисел обновляем ans = can_get.

3. Подсчёт результата:

- Перебираем все элементы ans, если число равно 50 и флаг равен 1 (т.е. траектория проходила через 15), увеличиваем счётчик otv.

- Выводим otv — количество подходящих программ.

# Динамическое решение
ans = []
ans.append((3, 0))  # Начальное число 3, проверочная точка не достигнута
for operations in range(20):
    can_get = []
    for i in ans:
        a, flag = i
        # Применяем команду 1: прибавить 1
        if a + 1 == 15:
            can_get.append((a + 1, 1))
        else:
            can_get.append((a + 1, flag))
        # Применяем команду 2: прибавить 0.75 числа, если число кратно 8
        if a % 8 == 0:
            if int(a + a * 0.75) == 15:
                can_get.append((int(a + a * 0.75), 1))
            else:
                can_get.append((int(a + a * 0.75), flag))
        # Применяем команду 3: умножить на 2
        can_get.append((a * 2, flag))
    ans = can_get
# Подсчет количества программ, результат которых 50 и проходящих через 15
otv = 0
for i in ans:
    a, flag = i
    if (a == 50) and (flag):
        otv += 1
print(otv)

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

Мы создаём функцию f(st, fn, exit_number, count, end_count), которая будет рекурсивно подсчитывать количество программ, приводящих число st к числу fn, учитывая: - исключение числа exit_number из траектории; - количество уже выполненных команд count и необходимое общее количество end_count.

Алгоритм работы функции следующий:

1. Проверяем, достигли ли мы целевого числа с нужным количеством команд:

- если st == fn и count == end_count, возвращаем 1 — найден один корректный путь.

2. Проверяем условия выхода:

- если st > fn (число стало больше целевого),

- или count > end_count (исполнено больше команд, чем нужно),

- или st == exit_number (текущий элемент траектории запрещён), то возвращаем 0 — такой путь недопустим.

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

- переменная x — результат рекурсивного вызова при выполнении команды «прибавить 2», если число кратно 3;

- переменная y — результат рекурсивного вызова при выполнении команды «прибавить 3», если число кратно 2;

- переменная z — результат рекурсивного вызова при выполнении команды «прибавить 1», если число не кратно ни 2, ни 3;

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

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

# Запускаем функцию с начальным числом 3, конечным 27, запретом числа 22,
# с 0 выполненными командами и общим числом команд 12
print(f(3, 27, 22, 0, 12))

—

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

Мы создаём список ans, который будет хранить все возможные текущие значения числа на каждом шаге программы. Изначально он содержит только стартовое число 3.

Далее мы последовательно выполняем 12 шагов (по количеству команд):

1. Создаём временный список can_get, куда будем добавлять новые числа, полученные после применения команд.

2. Для каждого числа i в списке ans:

- если i == 22, пропускаем это число, так как траектория не должна его содержать;

- если i % 3 == 0, добавляем i+2 в can_get — команда 1;

- если i % 2 == 0, добавляем i+3 в can_get — команда 2;

- если i % 2 != 0 и i % 3 != 0, добавляем i+1 в can_get — команда 3;

3. После обработки всех чисел текущего шага обновляем список ans как can_get.

После выполнения всех 12 операций в ans будут все числа, которых можно достичь за 12 шагов, обходя запрещённое число 22. Подсчёт количества элементов, равных 27, даст количество программ, удовлетворяющих условиям.

# Создаем список возможных чисел на каждом шаге
ans = []
ans.append(3)  # Начальное число 3
# Выполняем 12 шагов (команд)
for operations in range(12):
    can_get = []  # Временный список для чисел, полученных на этом шаге
    for i in ans:
        # Пропускаем число 22, так как оно запрещено
        if i == 22:
            continue
        # Применяем команду 1, если число кратно 3
        if i % 3 == 0:
            can_get.append(i + 2)
        # Применяем команду 2, если число кратно 2
        if i % 2 == 0:
            can_get.append(i + 3)
        # Применяем команду 3, если число не кратно ни 2, ни 3
        if (i % 2 != 0) and (i % 3 != 0):
            can_get.append(i + 1)
    # Обновляем список ans для следующего шага
    ans = can_get
# Подсчитываем количество программ, которые приводят к числу 27
print(ans.count(27))

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

Динамический способ решения заключается в подсчете количества траекторий до каждого числа с учетом двух условий: траектория не должна содержать число 11 и должна содержать число 13. Для этого мы будем хранить пары , где флаг указывает, встречалось ли число 13 в пути.

1. Создаем список ans и добавляем начальное состояние: число 1, флаг 0 (число 13 пока не встречалось).

2. Для каждой из 9 команд делаем следующие шаги:

- Создаем временный список can_get, куда будем добавлять новые состояния после применения команд.

- Для каждой пары (a, flag) из текущего списка ans проверяем:

- Если число равно 11, пропускаем этот вариант, так как траектория через 11 запрещена.

- Для каждой команды вычисляем новое число и обновляем флаг, если новое число равно 13.

- Добавляем новые пары((новое число, новый флаг) в can_get.

- После обработки всех пар обновляем ans новым списком can_get.

3. После 9 шагов перебора считаем количество пар, где число равно 28 и флаг равен 1 (число 13 встречалось).

# Инициализация списка с начальным состоянием
ans = []
ans.append((1, 0))  # (текущее число, флаг посещения 13)

# Перебор всех 9 команд
for operations in range(9):
    can_get = []
    for i in ans:
        a, flag = i
        if a == 11:
            continue  # Пропускаем состояния с числом 11
        # Применяем команду +3
        if a + 3 == 13:
            can_get.append((a + 3, 1))
        else:
            can_get.append((a + 3, flag))
        # Применяем команду +1
        if a + 1 == 13:
            can_get.append((a + 1, 1))
        else:
            can_get.append((a + 1, flag))
        # Применяем команду умножение на 2
        if 2 * a == 13:
            can_get.append((2 * a, 1))
        else:
            can_get.append((2 * a, flag))
    ans = can_get

# Подсчет количества программ, достигающих 28 с посещением 13
otv = 0
for i in ans:
    a, flag = i
    if (a == 28) and (flag):
        otv += 1
print(otv)

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

Мы определяем функцию f(st, fn, flag, flag_number, exit_number, count, end_count), которая рекурсивно проверяет все программы:

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

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

- fn — целевое число (28).

- flag — флаг, встречалось ли число 13 в траектории.

- flag_number — число 13, которое должно встретиться.

- exit_number — число 11, через которое проходить нельзя.

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

- end_count — общее количество команд (9).

2. Логика функции: - Если st == fn, count == end_count и flag=True, возвращаем 1 (найден подходящий путь).

- Если st > fn или count > end_count или st == exit_number, возвращаем 0 (недопустимый путь).

- Если st == flag_number, устанавливаем flag=True.

- Рекурсивно вызываем функцию для каждой команды (+1, +3, умножить на 2) с увеличением счетчика команд на 1.

- Суммируем результаты трех рекурсий и возвращаем.

# Рекурсивная функция для подсчета количества программ
def f(st, fn, flag, flag_number, exit_number, count, end_count):
    # Проверка завершения программы
    if st == fn and count == end_count and flag:
        return 1
    # Проверка недопустимых условий
    if st > fn or count > end_count or st == exit_number:
        return 0
    # Проверка посещения числа 13
    if st == flag_number:
        flag = True
    # Рекурсивный вызов для каждой команды
    x = f(st + 1, fn, flag, flag_number, exit_number, count + 1, end_count)
    y = f(st + 3, fn, flag, flag_number, exit_number, count + 1, end_count)
    z = f(st * 2, fn, flag, flag_number, exit_number, count + 1, end_count)
    return x + y + z

# Запуск рекурсии с начального числа 1
print(f(1, 28, False, 13, 11, 0, 9))

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

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

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

Так как нужно, чтобы траектория содержала число 10, но не содержала чисел 8 и 15, то общее количество программ равно произведению f(3, 10) и f(10, 22). Первая часть считает количество способов дойти от 3 до 10, вторая — от 10 до 22, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

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

 

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

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

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

По условию траектория не должна содержать числа 8 и 15, поэтому при подсчете количества траекторий значения в ячейках с индексами 8 и 15 должны остаться 0. Также по условию траектория должна содержать число 10. Для этого разделим вычисления на два независимых этапа: из 3 в 10, из 10 в 22. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 3 до 10 (с обязательным исключением числа 8)
# Создаем массив для хранения количества путей до чисел от 0 до 10
# a[i] - количество программ, которые преобразуют число 3 в число i
a = [0] * (10 + 1)
a[3] = 1  # Исходное положение - только один способ быть в числе 3

# Перебираем все числа от 4 до 10 включительно
for i in range(4, 10 + 1):
    if i == 8:
          continue  # Пропускаем числа 8 и 15 согласно условию задачи
    # Можно прийти командами прибавь 1 и прибавь 2
    ways = a[i-1] + a[i-2]

    # Можно прийти командой умножь на 3 (только для чисел кратных 3)
    if i % 3 == 0:
        ways += a[i // 3]

    a[i] = ways

# Второй этап: от 10 до 22 (с обязательным исключением числа 15)
# Массив для чисел от 0 до 22
# b[i] - количество программ, которые преобразуют число 10 в число i
b = [0] * (22 + 1)
b[10] = 1  # Начинаем из числа 10, которое должно быть в траектории

# Перебираем все числа от 11 до 22 включительно
for i in range(11, 22 + 1):
    if i == 15:
        continue  # Пропускаем числа 8 и 15 согласно условию задачи

    # Можно прийти командами прибавь 1 и прибавь 2
    ways = b[i-1] + b[i-2]

    # Можно прийти командой умножь на 3 (только для чисел кратных 3)
    if i % 3 == 0:
        ways += b[i // 3]

    b[i] = ways
                                                                                                     
                                                                                                     

# Общее количество программ равно произведению путей до 10 и от 10 до 22
print(a[10] * b[22])

Рекурсия:

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

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

Так как нужно, чтобы траектория содержала число 8, но не содержала чисел 10 и 11, то общее количество программ равно произведению f(1, 8) и f(8, 28). Первая часть считает количество способов дойти от 1 до 8, вторая — от 8 до 28, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

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

 

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

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

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

По условию траектория не должна содержать числа 10 и 11, поэтому при подсчете количества траекторий значения в ячейках с индексами 10 и 11 должны остаться 0. Также по условию траектория должна содержать число 8. Для этого разделим вычисления на два независимых этапа: из 1 в 8, из 8 в 28. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 1 до 8
# Создаем массив для хранения количества путей до чисел от 0 до 8
# a[i] - количество программ, которые преобразуют число 1 в число i
a = [0] * (8 + 1)
a[1] = 1  # Исходное положение - только один способ быть в числе 1

# Перебираем все числа от 2 до 8 включительно
for i in range(2, 8 + 1):
    # Можно прийти командами прибавь 1 и прибавь 2
    ways = a[i-1] + a[i-2]

    # Можно прийти командой умножь на 3 (только для чисел кратных 3)
    if i % 3 == 0:
        ways += a[i // 3]

    a[i] = ways

# Второй этап: от 8 до 28 (с обязательным исключением чисел 10 и 11)
# Массив для чисел от 0 до 28
# b[i] - количество программ, которые преобразуют число 8 в число i
b = [0] * (28 + 1)
b[8] = 1  # Начинаем из числа 8, которое должно быть в траектории

# Перебираем все числа от 9 до 28 включительно
for i in range(9, 28 + 1):
    if i == 10 or i == 11:
        continue  # Пропускаем числа 10 и 11 согласно условию задачи

    # Можно прийти командами прибавь 1 и прибавь 2
    ways = b[i-1] + b[i-2]

    # Можно прийти командой умножь на 3 (только для чисел кратных 3)
    if i % 3 == 0:
        ways += b[i // 3]

    b[i] = ways

# Общее количество программ равно произведению путей до 8 и от 8 до 28
                                                                                                     
                                                                                                     
print(a[8] * b[28])

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

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

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

- s — список, содержащий последовательность чисел, полученных после применения команд. Последний элемент списка s[-1] является текущим числом на экране.

2. Логика работы функции:

- Получаем текущее число a = s[-1].

- Проверяем, достигнута ли цель: если длина списка больше 1 и текущее число равно 12, возвращаем 1 — найден подходящий путь.

- Проверяем корректность текущего числа:

- Если оно меньше 10 или больше 30, путь недопустим.

- Если текущее число уже встречалось в траектории (a in s[:-1]), путь недопустим.

- В этих случаях возвращаем 0.

- Если число корректное, рекурсивно вызываем функцию для всех трёх возможных команд:

- a + 2 — прибавить 2

- a + 1 — прибавить 1

- a - 3 — вычесть 3

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

3. Запускаем рекурсию с исходного числа 20, помещенного в список [20].

4. Выводим результат.

# Рекурсивная функция для подсчета количества программ
def f(s):
    # Текущее число на экране — последний элемент последовательности
    a = s[-1]
    # Если достигли цели (12) и есть хотя бы одно число в траектории
    if len(s) > 1 and a == 12:
        return 1
    # Проверка, что число в допустимом диапазоне и не повторяется в траектории
    if a < 10 or a > 30 or (a in s[:-1]):
        return 0
    # Рекурсивно проверяем все три команды и суммируем результаты
    return sum(f(s + [a + h]) for h in [2, 1, -3])

# Запуск функции с исходного числа 20
print(f([20]))