MWPZ - Mistrzostwa Wielkopolski w Programowaniu Zespolowym

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(2^N). 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).

Dalej

Wstecz