Решения задач по информатике

Войти Зарегистрироваться

Задача 47: Простая последовательность

Условие задачи:

Вычислите \(n\)-й член последовательности, заданной формулами: \(a_{2n} = a_n + a_{n-1}, a_{2n+1} = a_n – a_{n-1}, a_0 = a_1 = 1\).

Входные данные:

Вводится одно натуральное число \(n (1≤n≤1000)\).

Выходные данные:

Вывести одно число \(a_n\).

Решение:

dp = [1, 1]
n = int(input())

for i in range(2, n + 1):
    if i % 2 == 0:
        dp.append(dp[i // 2] + dp[i // 2 - 1])
    else:
        dp.append(dp[i // 2] - dp[i // 2 - 1])

print(dp[n])

Пожалуйста, подождите загрузки решения