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(2^N). Oznacza to, że algorytm jest wykładniczy i będzie działał zbyt długo. Jeśli chcecie dowiedzieć się więcej o złożoności obliczeniowej i notacji "duże O", skorzystajcie z następujących stron: link 1 i link 2.

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).

Dalej

Wstecz