23.06 Количество программ из A в B где траектория вычислений N команда

Решение 1: Рекурсия

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

1. Сначала проверяем, достигли ли мы цели: если текущее число st равно целевому fn и количество использованных команд count равно end_count, то мы нашли подходящую программу и возвращаем 1.

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

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

- Вызываем функцию для варианта st // 2, увеличивая счётчик команд на 1. Умножаем результат на (st % 2 == 0), чтобы учитывать деление только для чётных чисел.

- Вызываем функцию для варианта st - 3, увеличивая счётчик команд на 1.

- Вызываем функцию для варианта st - 1, увеличивая счётчик команд на 1.

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

5. Вызываем функцию с начальными значениями st = 33, fn = 12, count = 0, end_count = 9 и выводим результат.

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

# Вызываем функцию для исходного числа 33, целевого 12 и 9 команд
print(f(33, 12, 0, 9))

—

Решение 2: Динамика

Мы используем динамический способ через перебор всех возможных чисел на каждом шаге программы.

1. Создаём список a, изначально содержащий одно число 33. Этот список хранит все текущие значения чисел после каждой команды.

2. Запускаем цикл по количеству команд (9 итераций). На каждой итерации:

- Сохраняем текущую длину списка n = len(a) для перебора всех элементов на текущем шаге.

- Для каждого элемента списка:

   - Убираем число из списка с помощью pop(0).

   - Если число больше целевого (12), добавляем в список новые значения, полученные применением каждой команды:

      - Деление на 2 для чётных чисел ((k // 2) * (k % 2 == 0)).

      - Вычитание 3 (k - 3).

      - Вычитание 1 (k - 1).

3. После всех 9 итераций считаем, сколько раз число 12 встречается в списке с помощью a.count(12), это и есть количество программ, которые за 9 шагов приводят число 33 к 12.

# Создаём список с исходным числом 33
a = [33]
# Перебираем все 9 команд
for i in range(9):
    # Сохраняем количество элементов на текущем шаге
    n = len(a)
    # Перебираем все текущие элементы
    for j in range(n):
        # Извлекаем число из списка
        k = a.pop(0)
        # Если число больше целевого 12, создаём новые состояния
        if k > 12:
            # Деление на 2, только если число чётное
            a.append((k // 2) * (k % 2 == 0))
            # Вычитание 3
            a.append(k - 3)
            # Вычитание 1
            a.append(k - 1)
# Считаем количество раз, когда в списке встречается число 12
print(a.count(12))

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

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

1. Проверяем, достигли ли мы цели:

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

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

- если count > end_count, возвращаем 0, так как путь не соответствует требуемой длине программы.

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

- x — количество программ, если применить команду "поделить на 2"(только если число четное, проверяем через st % 2 == 0).

- y — количество программ, если применить команду "прибавить 1".

- z — количество программ, если применить команду "прибавить треть числа"(только если число кратно 3, проверяем через st % 3 == 0).

4. Складываем x + y + z для получения общего количества программ из данного состояния.

Для ускорения вычислений мы используем кэширование с помощью functools.lru_cache, чтобы повторно не вычислять одно и то же значение. Вызов функции f(1, 60, 0, 25) вернёт итоговое количество программ, начиная с числа 1, заканчивая на числе 60 ровно после 25 команд.

# Импортируем кэш для ускорения рекурсии
from functools import lru_cache

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

# Вызываем функцию для исходного числа 1, целевого 60, 0 использованных команд и 25 команд всего
print(f(1, 60, 0, 25))

—

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

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

1. Инициализируем список ans с исходным числом 1.

2. Для каждой операции от 1 до 25:

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

   - Для каждого числа i из текущего списка ans:

      - если i четное, добавляем в can_get число i // 2 (команда "делить на 2");

      - добавляем i + 1 (команда "прибавить 1");

   - если i кратно 3, добавляем i + i // 3 (команда "прибавить треть числа").

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

3. После 25 шагов список ans содержит все числа, которые могут быть получены после 25 команд. Количество вхождений числа 60 в списке ans — это ответ.

# Инициализируем список с исходным числом
ans = []
ans.append(1)

# Перебираем все 25 команд
for operations in range(25):
    # Создаем новый список для чисел, которые можно получить на следующем шаге
    can_get = []
    for i in ans:
        # Если число четное, можно применить команду "делить на 2"
        if i % 2 == 0:
            can_get.append(i // 2)
        # Применяем команду "прибавить 1"
        can_get.append(i + 1)
        # Если число кратно 3, применяем команду "прибавить треть числа"
        if i % 3 == 0:
            can_get.append(i + i // 3)
    # Обновляем список чисел для следующей итерации
    ans = can_get

# Считаем, сколько раз число 60 встречается в итоговом списке
print(ans.count(60))

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

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

Идея решения: на каждом шаге мы проверяем, достигли ли мы максимального количества команд. Если c == 7, то проверяем, равно ли текущее число a целевому числу 27. Если да, возвращаем 1 (найден подходящий путь), если нет — 0.

Если количество команд меньше 7, то мы пробуем применить каждую из трёх команд и рекурсивно вызываем функцию с обновлёнными значениями: - Используем команду "прибавить 1 увеличиваем c на 1. - Используем команду "прибавить 4 увеличиваем c на 1. - Используем команду "умножить на 2 увеличиваем c на 1.

Результаты этих трёх рекурсивных вызовов суммируются, чтобы получить общее количество программ, которые из числа 3 после 7 команд приводят к числу 27.

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

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

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

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

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

2. c — количество уже использованных команд.

Мы проверяем два условия:

- Если c == 10, то мы достигли предела команд. В этом случае проверяем, равно ли текущее число a цели (1). Если да, возвращаем 1 (найден путь), иначе 0.

- Если c < 10, мы пробуем три варианта команды: прибавить 4, прибавить 7 и разделить на 2 нацело. Каждый вариант увеличивает c на 1, и мы рекурсивно вызываем функцию для нового числа. Результаты трёх вызовов суммируются, чтобы получить общее количество программ.

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

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

—

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

Мы можем использовать динамический подход, чтобы последовательно строить все состояния после каждой команды. Идея: создаём список a, который хранит все возможные числа после каждой команды.

1. Начинаем с a = [1] — исходное число на экране.

2. Проходим 10 итераций (по количеству команд).

- На каждой итерации берём текущее количество элементов n = len(a).

- Для каждого элемента из списка (берём по индексу j от 0 до n-1), убираем его из списка (pop(0)) и создаём три новых значения:

* прибавляем 4

* прибавляем 7

* делим нацело на 2

- Добавляем эти новые значения в конец списка (append).

3. После всех 10 итераций считаем количество элементов, равных 1 (a.count(1)). Это и есть количество программ, которые после 10 команд вернули число 1.

# Инициализируем список с исходным числом
a = [1]
# Проходим 10 итераций, соответствующих 10 командам
for i in range(10):
    # Сохраняем текущую длину списка
    n = len(a)
    # Проходим по всем текущим элементам
    for j in range(n):
        # Берем первый элемент списка
        l = a.pop(0)
        # Применяем все три команды и добавляем результаты в конец списка
        a.append(l + 4)
        a.append(l + 7)
        a.append(l // 2)
# Подсчитываем, сколько элементов равно 1 после 10 команд
print(a.count(1))

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

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

1. Сначала создаём список a, содержащий только исходное число 245. Оно является начальным состоянием:

- a = [245]

2. Далее выполняем цикл по количеству команд (16 шагов), на каждом шаге обновляя список a:

- Перед началом итерации превращаем список в множество и обратно, чтобы убрать повторяющиеся числа (a = list(set(a))).

- Определяем количество чисел, которые будут обработаны на текущем шаге (n = len(a)).

- Для каждого числа в списке:

      - Извлекаем число из списка (l = a.pop(0)).

      - Применяем первую команду: вычитаем 1 и добавляем результат в список (a.append(l - 1)).

      - Применяем вторую команду: умножаем на (-2) и добавляем результат в список (a.append(l * (-2))).

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

- a = list(set(a))

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

- print(len([j for j in a if j >= 0]))

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

# Инициализируем список a исходным числом 245
a = [245]
# Повторяем процесс 16 раз, так как программа содержит 16 команд
for i in range(16):
    # Преобразуем список в множество и обратно, чтобы удалить повторяющиеся числа
    a = list(set(a))
    # Определяем количество чисел для обработки на этом шаге
    n = len(a)
    # Перебираем все числа в списке
    for j in range(len(a)):
        # Извлекаем число из списка
        l = a.pop(0)
        # Применяем первую команду: вычесть 1 и добавляем результат в список
        a.append(l - 1)
        # Применяем вторую команду: умножить на -2 и добавляем результат в список
        a.append(l * (-2))
# Убираем повторяющиеся числа после всех 16 шагов
a = list(set(a))
# Считаем количество неотрицательных чисел в списке
print(len([j for j in a if j >= 0]))

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

Идея рекурсивного решения заключается в том, что мы создаём функцию, которая перебирает все возможные последовательности команд и добавляет результаты в множество. Каждая команда обозначена числом: 1 — прибавить 2, 2 — прибавить 5, 3 — умножить на 2. Мы используем параметр k, чтобы отслеживать количество выполненных команд, и параметр r, чтобы запомнить номер команды, выполненной на предыдущем шаге, так как повторять её нельзя.

1. Создаём пустое множество s, в котором будут храниться все полученные результаты. 2. Определяем функцию f(a, k=0, r=0): - a — текущее число на экране, - k — количество выполненных команд, - r — номер команды, выполненной на предыдущем шаге. 3. В функции проверяем условие окончания рекурсии: если k == 13, значит выполнено 13 команд, добавляем текущее число a в множество s и возвращаем управление. 4. Для каждой команды проверяем, не совпадает ли её номер с предыдущей (r): - если предыдущая команда не 1, вызываем рекурсию с a + 2, увеличивая счётчик команд на 1 и устанавливая r = 1, - если предыдущая команда не 2, вызываем рекурсию с a + 5, увеличивая счётчик команд на 1 и устанавливая r = 2, - если предыдущая команда не 3, вызываем рекурсию с a * 2, увеличивая счётчик команд на 1 и устанавливая r = 3. 5. После завершения рекурсий выводим количество элементов множества s, которое и будет количеством различных результатов.

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

# Определяем рекурсивную функцию f(a, k=0, r=0)
def f(a, k=0, r=0):
    # Если выполнено 13 команд, добавляем текущее число в множество
    if k == 13:
        s.add(a)
        return
    # Если предыдущая команда не была 1, выполняем команду "прибавить 2"
    if r != 1:
        f(a + 2, k + 1, 1)
    # Если предыдущая команда не была 2, выполняем команду "прибавить 5"
    if r != 2:
        f(a + 5, k + 1, 2)
    # Если предыдущая команда не была 3, выполняем команду "умножить на 2"
    if r != 3:
        f(a * 2, k + 1, 3)

# Запускаем рекурсивное вычисление, начиная с числа 8
f(8)

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

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

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

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

2. В функции f(x, k) проверяем, сколько команд осталось:

- Если , значит команд больше нет, и текущее значение добавляем в множество a как результат.

- Если , то делаем два рекурсивных вызова:

- f(x - 4, k - 1), что соответствует применению команды "вычесть 4"и уменьшению количества оставшихся команд на 1.

- f(x * -1, k - 1), что соответствует применению команды "умножить на -1"и также уменьшению количества оставшихся команд на 1.

3. После выполнения всех рекурсивных вызовов множество a будет содержать все возможные значения, полученные после применения 10 команд к числу 123.

4. Чтобы посчитать количество неотрицательных результатов, мы перебираем все элементы множества a и считаем те, которые больше или равны 0.

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

# Определяем рекурсивную функцию для подсчета всех значений
def f(x, k):
    # Если команд больше нет, добавляем текущее число в множество
    if k == 0:
        a.add(x)
        return 0
    # Применяем команду "вычесть 4" и уменьшаем количество команд на 1
    f(x - 4, k - 1)
    # Применяем команду "умножить на -1" и уменьшаем количество команд на 1
    f(x * -1, k - 1)

# Запускаем функцию с исходным числом 123 и 10 командами
f(123, 10)

# Считаем количество неотрицательных чисел в множестве
kol = 0
for i in a:
    if i >= 0:
        kol += 1

# Выводим результат
print(kol)

—

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

Мы можем решить задачу и с помощью динамического подхода, используя списки для хранения всех возможных значений после каждой команды. Алгоритм строится пошагово:

1. Создаем список a, содержащий текущее множество чисел, начинаем со списка [123].

2. Для каждой из 10 команд (в цикле for i in range(10)) выполняем следующие действия:

- Преобразуем список a в множество и обратно в список, чтобы исключить повторяющиеся значения.

- Сохраняем текущее количество элементов в переменную n.

- Для каждого элемента списка a (от 0 до n-1):

      - Извлекаем первый элемент с помощью pop(0) и сохраняем его в l.

      - Добавляем два новых элемента в конец списка: l - 4 (применение первой команды) и l * (-1) (применение второй команды).

3. После всех 10 итераций получаем множество всех возможных чисел.

4. Считаем количество неотрицательных чисел в множестве с помощью генератора списка и функции len.

# Инициализируем список с исходным числом
a = [123]

# Повторяем процесс для 10 команд
for i in range(10):
    # Убираем повторяющиеся значения
    a = list(set(a))
    # Сохраняем текущее количество элементов
    n = len(a)
    # Для каждого элемента применяем обе команды
    for j in range(n):
        # Извлекаем первый элемент
        l = a.pop(0)
        # Добавляем результат применения команды "вычесть 4"
        a.append(l - 4)
        # Добавляем результат применения команды "умножить на -1"
        a.append(l * (-1))

# Преобразуем список в множество для уникальных значений
a = set(a)

# Считаем количество неотрицательных чисел
print(len([j for j in a if j >= 0]))

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

Мы используем рекурсию для перебора всех возможных последовательностей команд, соблюдая условие о допустимых номерах команд на каждом шаге. Определим функцию f(a, h, c), где:

- — текущее значение на экране;

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

- — номер последней команды, которая была выполнена (0 для первого шага, когда предыдущей команды нет).

1. На каждом шаге мы проверяем, достигли ли количества команд, равного 10:

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

2. Если это первый шаг (), разрешены все команды, поэтому вызываем функцию рекурсивно для всех шести команд: прибавление 1, 2, 3 и умножение на 2, 3, 4;

3. Если это не первый шаг, проверяем номер последней команды и разрешаем только команды с номерами, отличающимися на 1:

- Например, если , то на следующем шаге разрешены команды 1 и 3, так как их номера отличаются на 1 от 2;

- Для разрешена только команда 2;

- Для разрешена только команда 5;

- Для промежуточных номеров выполняем оба варианта (влево и вправо), чтобы соблюсти условие различия номеров на 1.

На каждом рекурсивном вызове мы увеличиваем счётчик шагов на 1 и передаём новый номер выполненной команды, чтобы следующий вызов функции мог правильно определить доступные команды. Когда рекурсия достигает 10 шагов, значение добавляется в множество s. После завершения всех рекурсивных веток количество уникальных значений в s даёт ответ на задачу.

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

# Определяем рекурсивную функцию
def f(a, h, c):
    # Если выполнено 10 команд, добавляем результат в множество
    if h == 10:
        s.add(a)
        return
    # Если это первый шаг, можно использовать любую команду
    if c == 0:
        f(a + 1, h + 1, 1)   # прибавляем 1
        f(a + 2, h + 1, 2)   # прибавляем 2
        f(a + 3, h + 1, 3)   # прибавляем 3
        f(a * 2, h + 1, 4)   # умножаем на 2
        f(a * 3, h + 1, 5)   # умножаем на 3
        f(a * 4, h + 1, 6)   # умножаем на 4
    # Если последняя команда была 1, следующий шаг только команда 2
    elif c == 1:
        f(a + 2, h + 1, 2)
    # Если последняя команда была 2, следующий шаг команды 1 и 3
    elif c == 2:
        f(a + 1, h + 1, 1)
        f(a + 3, h + 1, 3)
    # Если последняя команда была 3, следующий шаг команды 2 и 4
    elif c == 3:
        f(a + 2, h + 1, 2)
        f(a * 2, h + 1, 4)
    # Если последняя команда была 4, следующий шаг команды 3 и 5
    elif c == 4:
        f(a + 3, h + 1, 3)
        f(a * 3, h + 1, 5)
    # Если последняя команда была 5, следующий шаг команды 4 и 6
    elif c == 5:
        f(a * 2, h + 1, 4)
        f(a * 4, h + 1, 6)
    # Если последняя команда была 6, следующий шаг только команда 5
    elif c == 6:
                                                                                                     
                                                                                                     
        f(a * 3, h + 1, 5)

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

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

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

В динамическом подходе мы моделируем все возможные состояния после каждого шага программы с помощью списка a, где каждый элемент — это пара [значение, номер последней команды].

1. Изначально в списке только одно состояние: [1, ’0’] — число 1 и отсутствие предыдущей команды.

2. Для каждого из 10 шагов:

- Создаём новый список состояний после выполнения текущего шага.

- Для каждого состояния определяем список всех возможных команд: прибавление 1,2,3 и умножение на 2,3,4.

- Если предыдущая команда ’0’ (первый шаг), добавляем все команды в новый список.

- Если предыдущая команда крайняя (1 или 6), добавляем только соседнюю команду, чтобы не выйти за границы.

- Для остальных случаев добавляем две соседние команды: c-1 и c+1.

3. После 10 шагов остаётся множество всех возможных конечных значений. Преобразуем его в множество, чтобы исключить повторения, и считаем длину множества — это и есть количество различных результатов.

# Начальное состояние: число 1, предыдущая команда отсутствует
a = [[1, ’0’]]

# Выполняем 10 шагов программы
for i in range(10):
    n = len(a)
    for j in range(n):
        l = a.pop(0)
        # Список всех возможных команд
        command = [[l[0] + 1, ’1’], [l[0] + 2, ’2’], [l[0] + 3, ’3’],
                   [l[0] * 2, ’4’], [l[0] * 3, ’5’], [l[0] * 4, ’6’]]
        # Первый шаг - все команды доступны
        if l[1] == ’0’:
            for k in range(6):
                a.append(command[k])
        # Крайние команды: только одна соседняя
        elif l[1] == ’1’:
            a.append(command[1])
        elif l[1] == ’6’:
            a.append(command[4])
        # Для остальных команд: добавляем соседние по номерам
        else:
            a.append(command[int(l[1]) - 2])
            a.append(command[int(l[1])])

# Преобразуем все значения в множество, чтобы исключить дубликаты
a = set([j[0] for j in a])

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

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

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

1. Сначала мы создаем множество a, куда будем добавлять все полученные неотрицательные числа. Множество удобно, так как автоматически исключает повторения.

2. В функции f(n, c) реализуем проверку:

- если c == 8 (все команды выполнены), то проверяем знак числа:

      - если n >= 0, добавляем n в множество a.

- если c < 8, то выполняем оба возможных действия:

      - вычесть 3 (передаем n-3 в следующий вызов с увеличением счетчика команд на 1)

      - умножить на (-1) (передаем n*(-1) с увеличением счетчика команд на 1)

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

3. Запускаем функцию с исходным числом 82 и нулевым счетчиком команд (f(82, 0)). После завершения всех рекурсивных вызовов в множестве a будут храниться все возможные неотрицательные результаты. Выводим это множество, чтобы получить ответ.

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

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

# Запускаем рекурсию с исходного числа 82 и 0 выполненных команд
f(82, 0)

# Выводим множество всех возможных неотрицательных результатов
print(a)

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

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

1. Создаем пустое множество a = set(), которое будет хранить все уникальные результаты. Множество автоматически исключает дубликаты, поэтому если одно и то же число получится разными способами, оно будет учтено только один раз.

2. Определяем функцию f(n, c):

- Проверка количества команд: если c == 13, значит мы выполнили ровно 13 команд. В этом случае:

      - Добавляем текущее число n в множество a, используя a.add(n).

- Иначе: если команд меньше 13, продолжаем рекурсивный перебор всех вариантов команд:

      - Вызываем f(n+1, c+1), что соответствует выполнению команды «прибавить 1».

      - Вызываем f(n*3, c+1), что соответствует выполнению команды «умножить на 3».

      - Вызываем f(n*2, c+1), что соответствует выполнению команды «умножить на 2».

3. Запускаем функцию с начальными значениями f(7, 0), где 7 — исходное число, а 0 — количество выполненных команд.

4. После завершения рекурсивных вызовов множество a будет содержать все уникальные числа, которые можно получить после 13 команд. Чтобы узнать количество различных результатов, выводим длину множества через print(len(a)).

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

# Определяем рекурсивную функцию f(n, c)
# n — текущее число на доске
# c — количество выполненных команд
def f(n, c):
    # Если выполнено ровно 13 команд,
    # добавляем текущее число в множество результатов
    if c == 13:
        a.add(n)
    else:
        # Иначе продолжаем выполнение рекурсивно для всех трех команд
        # 1) Прибавляем 1 и увеличиваем счетчик команд на 1
        f(n+1, c+1)
        # 2) Умножаем на 3 и увеличиваем счетчик команд на 1
        f(n*3, c+1)
        # 3) Умножаем на 2 и увеличиваем счетчик команд на 1
        f(n*2, c+1)

# Запускаем рекурсивный перебор, начиная с числа 7 и 0 выполненных команд
f(7, 0)

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

Исполнитель Лето преобразует число, записанное на доске. У исполнителя есть две команды:

1. Прибавить 2 2. Умножить на 2

Программа для исполнителя Лето — это последовательность команд. Сколько различных результатов можно получить из исходного числа 3 в ходе исполнения программы, содержащей ровно 8 команд?

—

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

Идея решения заключается в том, что мы будем строить все возможные траектории исполнения программы с помощью рекурсивной функции. Мы создаём множество a, в котором будут храниться все уникальные результаты, полученные после применения ровно 8 команд. Функция f(n, c) принимает два параметра: n — текущее число на доске, и c — количество уже выполненных команд.

1. На каждом вызове функции проверяем условие завершения: - если c == 8, это значит, что выполнено ровно 8 команд, и текущий результат n добавляется в множество a, чтобы учесть его как один из возможных результатов; - если c < 8, мы продолжаем рекурсивно применять команды.

2. Для рекурсивного перехода применяем обе доступные команды: - вызываем f(n+2, c+1), что соответствует прибавлению 2 к текущему числу и увеличению счётчика команд на 1; - вызываем f(n*2, c+1), что соответствует умножению текущего числа на 2 и увеличению счётчика команд на 1.

3. После завершения всех рекурсивных вызовов множество a будет содержать все уникальные числа, которые можно получить из числа 3 с помощью ровно 8 команд. Количество различных результатов вычисляется с помощью функции len(a).

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

# Определяем рекурсивную функцию f
# n - текущее число, c - количество выполненных команд
def f(n, c):
    # Если выполнено ровно 8 команд, добавляем текущее число в множество
    if c == 8:
        a.add(n)
    else:
        # Иначе продолжаем рекурсию, применяя команду "прибавить 2"
        f(n+2, c+1)
        # И применяя команду "умножить на 2"
        f(n*2, c+1)

# Запускаем рекурсивный перебор с начальным числом 3 и 0 выполненных команд
f(3, 0)
# Выводим количество уникальных результатов после 8 команд
print(len(a))

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

Мы будем использовать рекурсивный способ решения, чтобы подсчитать все возможные результаты после выполнения ровно 6 команд. Идея решения такова: мы определяем функцию f(n, c), где n — текущее число на доске, а c — количество уже совершённых команд.

1. Если количество совершённых команд c достигло 6, то мы добавляем текущее число n в множество результатов a. Множество автоматически исключает повторения, поэтому каждый уникальный результат сохраняется один раз.

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

- прибавить 1 к числу (n+1) и увеличить счётчик команд на 1 (c+1);

- прибавить 10 к числу (n+10) и увеличить счётчик команд на 1;

- умножить число на 3 (n*3) и увеличить счётчик команд на 1.

3. После того как все рекурсивные вызовы завершатся, множество a будет содержать все различные результаты, которые можно получить после 6 команд. Длина множества (len(a)) и будет ответом на задачу.

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

# Определяем рекурсивную функцию f(n, c)
# n - текущее число на доске
# c - количество уже выполненных команд
def f(n, c):
    # Если выполнено ровно 6 команд,
    # добавляем текущее число в множество результатов
    if c == 6:
        a.add(n)
    else:
        # Иначе, для каждого из трёх вариантов команд
        # выполняем рекурсивный вызов с увеличением счётчика команд на 1
        f(n+1, c+1)   # Команда "прибавить 1"
        f(n+10, c+1)  # Команда "прибавить 10"
        f(n*3, c+1)   # Команда "умножить на 3"

# Запускаем рекурсивный перебор, начиная с числа 8 и 0 совершённых команд
f(8, 0)

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

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

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

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

2. — число, к которому нужно прийти после выполнения всех команд;

3. — количество уже выполненных команд.

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

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

- Если , то программа завершена.

* В этом случае функция возвращает True (или 1), если текущее число равно , и False (или 0) в противном случае.

2. Если , то продолжаем рекурсию:

- Пробуем первую команду: прибавляем 4 к числу , увеличиваем счётчик команд на 1, и вызываем функцию рекурсивно.

- Пробуем вторую команду: прибавляем 7 к числу , увеличиваем счётчик команд на 1, и вызываем функцию рекурсивно.

- Пробуем третью команду: делим число на 2 нацело (используя целочисленное деление), увеличиваем счётчик команд на 1, и вызываем функцию рекурсивно.

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

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

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

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