Олимпиадный тренинг

Задача . Числа Фибоначчи: Мемоизация рекурсии (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).

Примеры

№	Входные данные	Выходные данные
1	2	1
2	3	2
3	4	3

Запрещенные операторы: for; while

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	280

Комментарий учителя

Ваш ответ

C++

1	#include <iostream>
2	#include <unordered_map>
3
4	using namespace std;
5
6	unordered_map<int, long long> memo;
7
8	long long fib(int n)
9	{
10	// Если результат уже вычислен, вернем его из мемоизации
11	if (memo.find(n) != memo.end())
12	{
13	return memo[n];
14	}
15
16	// Если n равно 0 или 1, возвращаем n (базовые случаи)
17	if ()
18	{
19	return 0;
20	}
21	else if (n == 1)
22	{
23
24	}
25
26	// Вычисляем значение числа Фибоначчи и сохраняем его в мемоизации
27
28	return memo[n];
29	}
30
31	int main()
32	{
33	int n;
34	cin >> n;
35	cout << fib(n) << endl;
36	return 0;
37	}

Загруженные файлы

Нет