Алгоритм вычисления функции F(n)

Question

На первый взгляд задача легка и выглядит она вот так:
Алгоритм вычисления функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:

F(n) = n + 3, при n ≤ 3  
F(n) = F(n – 2) + n, при n > 3 и четном значении F(n-1),  
F(n) = F(n – 2) + 2· n, при n > 3 и нечетном значении F(n-1)

Определите сумму значений, являющихся результатом вызова функции для значений n в диапазоне [40; 50].

Мой код:

def f(n):
    if n <= 3:
        return n + 3
    elif n > 3 and (f(n-1)) % 2 == 0:
        return f(n-2) + n
    elif n > 3 and (f(n-1)) % 2 != 0:
        return f(n-2) + 2*n
k = 0
for n in range(40, 50+1):
    k += f(n)
print(k)

Но идет зацикливание уже на первом элементе. Моя проблема: не могу понять - это условие неправильное или это в коде ошибка?

Answer 1

import functools

def cache(func):
    """Кэш предыдущих вызовов функций"""
    @functools.wraps(func)
    def wrapper(*args, **kwargs):
        cache_key = args + tuple(kwargs.items())
        if cache_key not in wrapper.cache:
            wrapper.cache[cache_key] = func(*args, **kwargs)
        return wrapper.cache[cache_key]
    wrapper.cache = dict()
    return wrapper

@cache
def f(n):
    if n <= 3:
        return n + 3
    elif f(n-1) % 2 == 0:
        return f(n-2) + n
    elif f(n-1) % 2 != 0:
        return f(n-2) + 2*n

k = 0
for n in range(40, 50+1):
    k += f(n)

print(k) # 8508

Answer 2

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

from functools import lru_cache

@lru_cache()
def f(n):
    if n <= 3:
        return n + 3

    if f(n-1) % 2 == 0:
        return f(n-2) + n

    return f(n-2) + 2*n

k = sum(map(f, range(40, 50+1)))
print(k)

Answer 3

Необходимости в дополнительных модулях и прочих наворотах нет, должны были изучать расчёт чисел Фибоначчи со складыванием посчитанного в массив/список, здесь всё похоже.

def calc(lo, hi):
    f = [3,4,5,6] + [0]*(hi-3)
    for i in range(4, hi+1):
        f[i] = f[i-2] + i + i*(f[i-1]&1) #учёт нечётности - младший бит единица
    return sum(f[lo:hi+1])

print(calc(40, 50))

БЛОГ НА HUSL

Алгоритм вычисления функции F(n)

Ответы (3 шт):