23.08 Прочие прототипы

Рекурсивный способ решения

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

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

2. В функции f(st) проверяем:

- Если длина строки st равна 10, увеличиваем count на 1 и выводим строку.

- Если длина строки меньше 10, выполняем рекурсивные вызовы для обеих команд:

- Приписываем "0"справа: st + "0".

- Приписываем копию числа задом наперед: st + st[::-1].

3. Запускаем рекурсию с начального числа "7".

4. После завершения рекурсии выводим значение count.

# Инициализируем глобальный счетчик количества программ
count = 0
# Определяем рекурсивную функцию для построения всех программ
def f(st):
    global count
    # Если длина строки равна 10, найдено подходящее число
    if len(st) == 10:
        count += 1
        print(st)
    # Если длина строки меньше 10, продолжаем применять команды
    if len(st) < 10:
        # Приписываем ’0’ справа
        f(st + "0")
        # Приписываем копию числа задом наперед
        f(st + st[::-1])

# Запускаем рекурсию с числа ’7’
f("7")
# Выводим общее количество программ
print(count)

Динамический способ решения

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

1. Инициализируем массив ans пустым списком и счетчик otv = 0.

2. Добавляем начальное число "7"в ans.

3. Перебираем последовательность операций (до 1000 итераций, достаточно для достижения длины 10):

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

- Для каждой строки i из ans выполняем:

- Если длина строки равна 10, увеличиваем otv на 1.

- Применяем первую команду: приписываем "0"справа. Если длина новой строки не превышает 10, добавляем в can_get.

- Применяем вторую команду: приписываем копию строки задом наперед. Если длина новой строки не превышает 10, добавляем в can_get.

- Если список can_get пуст, прекращаем цикл.

- Иначе присваиваем ans = can_get для следующей итерации.

4. После завершения цикла выводим otv — общее количество программ.

# Инициализируем список для хранения текущих строк
ans = []
# Счетчик количества программ длины 10
otv = 0
# Добавляем начальное число ’7’
ans.append("7")

# Перебираем операции (ограничение по числу итераций)
for operations in range(1000):
    # Список для хранения новых строк после текущей итерации
    can_get = []
    # Обрабатываем каждую строку из текущего списка
    for i in ans:
        # Если длина строки равна 10, увеличиваем счетчик
        if len(i) == 10:
            otv += 1
        # Применяем команду приписать ’0’ справа
        new_st = i + "0"
        if len(new_st) <= 10:
            can_get.append(new_st)
        # Применяем команду приписать копию строки задом наперед
        new_st = i + i[::-1]
        if len(new_st) <= 10:
            can_get.append(new_st)
    # Если новые строки не получены, прекращаем цикл
    if len(can_get) == 0:
        break
    # Обновляем список текущих строк
    ans = can_get

# Выводим общее количество программ длины 10
print(otv)