Tutorial
Tik tak tik tak tik tak... chrrrr zzzzz
Powsta� w g�owie nowy algorytm. W my�l niego mo�na napisa� ten program przy pomocy rekurencji, bo przecie� liczby Fibonacciego s� zdefiniowane rekurencyjnie.
var d,n,i : longint; function fib(x: longint): longint; begin if x=0 then fib:=0; if x=1 then fib:=1; fib:=(fib(x-1)+fib(x-2)) mod 10000 end; begin readln(d); while (d>0) do begin d:=d-1; readln(n); writeln(fib(n)); end; end.
Wys�anie takiego programu spowoduje, �e Sprawdzarka zwr�ci ocen�:
Time Limit Exceeded
Oznacza to, �e w program dzia�a� za d�ugo. W tym przypadku liczby Fibonacciego licz� si� zbyt wiele razy i to powoduje, �e komputer wykonuje mn�stwo niepotrzebnych operacji. Np. dla N = 4 wyliczymy fib(4) => (fib(3) i fib(2)), potem fib(3) => (fib(2) i fib(1)) i fib(2) => (fib(1) i fib(0)), a potem jeszcze raz fib(2) => (fib(1) i fib(0)). Jak wida� te same warto�ci licz� si� kilka razy. Dla du�ych liczb powtarzaj�cych si� operacji b�dzie bardzo du�o i program b�dzie dzia�a� d�ugo. M�wi�c fachowo, algorytm taki ma z�o�ono�� rz�du O(2N). Oznacza to, �e algorytm jest wyk�adniczy i b�dzie dzia�a� zbyt d�ugo.
Uwaga! Program uruchomiony na Sprawdzarce testowany jest na innych danych, ni� te z tre�ci zadania. Je�li w tre�ci s� przyk�ady o ma�ych warto�ciach zmiennych (np. N = 2), nie oznacza to wcale, �e takie same b�d� na Sprawdzarce. Wr�cz przeciwnie, ka�dy program jest testowany na danych du�ych (np. N = 20000), a tak�e z�o�liwych przypadkach szczeg�lnych (np. N = 0).