Задача про обчислення чисел Фібоначчі

•Обчислення чисел Фібоначчі.
Ряд: 1,1,2,3,5,8,13,21,34,55, …

ТутF1=1, F2=1, Fn=Fn-1+Fn-2 (n≥3)
Псевдокод:
Fib(n)
If (n=1) or (n=2)
then Fib:=1 else
Fib:=Fib(n-1)+ Fib(n-2)
При такому підході, обчислення можуть багатократно повторюватись (чим більше n – тим більше повторень).
Складність~ 1.5n

Прикладзадачі, з підзадачами, що повторюються
•Обчислення чисел Фібоначчі (продовження).
Щоб уникнути зайвих обчислень – треба послідовно обчислювати Fib(n), починаючи з n=3:
Fib(n)
Fib[1]:=1;
Fib[2]:=1;
for i=3 or n
Fib[i]:=Fib[i-1]+ Fib[i-2]
Тут складість 1.5 в степені n.

Задача пошуку Гамільтонового циклу у графі.

Задача про заявки на проведення занять в аудиторії.

Задача про рюкзак (дискретна і безперервна).

Алгоритм Дейкстри.