16.01 Одна функция

Рекурсивное решение

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

def f(n):
    # База: F(1)=1, F(2)=2, F(3)=3
    if n < 4:
        return n
    # Отдельная база для n = 4:
    if n == 4:
        return 3
    # Рекурсия:
    return f(n - 4) + f(n - 3) + n

# Поиск минимального n, удовлетворяющего условиям
for n in range(1, 1000):
    val = f(n)
    # Подсчёт суммы цифр и количества цифр "7"
    summa, count_7 = 0, 0
    while val > 0:
        # Суммируем цифры
        summa += val % 10
        # Если эта цифра равна 7, то выражение
        # прибавит 1 к count_7
        count_7 += val % 10 == 7
        val //= 10

    # Проверка условий: сумма кратна 13 и более двух семёрок
    if count_7 > 2 and summa % 13 == 0:
        print(n)
        break