.P3 - Programovanie 3

Po zvládnutí základov programovania sa vyučujú rôzne techniky programovania - napr. Prehľadávanie s návratom, ako aj Rozdeľuj a panuj. Zvyčajne nasleduje ukážka, že v niektorých prípadoch to nie je efektívne a výpočty sa opakujú. Tu prichádza na scénu memoizácia (dynamické programovanie zhora nadol). Typickou úlohou na memoizáciu býva výpočet Fibonacciho čísla, teda hodnoty v postupnosti 0, 1, 1, 2, 3, 5, 8, 13, ..., kde ďalší prvok je súčtom dvoch predchádzajúcich.

Nižšie sú uvedené kódy na výpočet v jazyku Python rekurziou aj memoizáciou.

Na lepšiu predstavu zobrazujeme stromy volaní pre N=5:

Úloha

Pre zadanú hodnotu N vypočítajte koľko volaní sa ušetrí použitím uvedenej memoizácie (oproti čisto rekurzívnemu výpočtu) pri výpočte n-tého Fibonacciho čísla.

Vstup

V prvom riadku vstupu je celé číslo T – počet testovacích vstupov. Nasleduje T riadkov, v každom je jedno kladné celé číslo N.

.P3

1 ≤ T ≤ 1 000
0 ≤ N ≤ 80

Výstup

Pre každý vstup vypíšte jeden riadok výstupu, obsahujúci počet ušetrených volaní.

Príklad

Vstup:

2
5
10

Výstup:

6
158