Задача про функции

Question

Помогите, пожалуйста, с задачей. Задача про Функции. у меня в коде ошибка, видимо неправильно понял задачу:

n = int(input())
m = n
def f(n):
    if n == 0:
        print(0)
    elif 2 > n > 0:
        print(1)
    if n > 1:
        n %= 2
        if n == 1:
            print((m+1)//2)
        else:
            print(m//2)
f(n)

Answer 1

Ну вот прямо по написанному определению:

def f(n):
    if n < 2:
        return n
    if n%2:
        return f(n//2) + f(1 + n//2)
    else:
        return f(n//2)

n = int(input())
print(f(n))

Это довольно долго может считаться, поскольку такая организация рекурсии приводит к многократному вычислению одних и тех же значений. (Для n<1000 это неважно)

Но их можно записывать в список и брать оттуда, когда нужно. А можно пойти и от начала, вычисляя последовательно f(2), f(3) и так до нужного значения.

Answer 2

Еще вариант с мемоизацией:

def memo(f):
    ret = {}
    def helper(i):
        if i not in ret:
            ret[i] = f(i)
        return ret[i]
    return helper

@memo
def f(n):
    if n < 2:
        return n
    return f(n // 2) + (n % 2) * f(n // 2 + n % 2)
    
n = int(input())
print(f(n))

БЛОГ НА HUSL

Задача про функции

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