2.
Числа Фибоначчи: Мемоизация рекурсии (Python)
Основная теория описана в задаче Числа Фибоначчи: Мемоизация рекурсии (C++)
Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.
По заданному n, вычислите F(n) (0 <= n <= 80).
(в коде программы длина одного отступа равна 4 пробелам!)
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 |
1 |
| 2 |
3 |
2 |
| 3 |
4 |
3 |
Запрещенные операторы: for;while
Вставьте недостающие фрагменты кода
Python
| 1 |
cash = {0: 0, 1: 1} # для хранения будем использовать словарь
|
| 2 |
def f(n):
|
| 3 |
if n in cash:
|
| 4 |
return cash[n]
|
| 5 |
|
| 6 |
return cash[n]
|
| 7 |
|
| 8 |
|
| 9 |
n = int(input())
|
| 10 |
print(f(n))
|