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.
#include <stdio.h> int d,n,i; int fib(int x) { if (x==0) return 0; if (x==1) return 1; return (fib(x-1)+fib(x-2))%10000; } int main() { scanf("%d\n",&d); while (d--) { scanf("%d\n",&n); printf("%d\n",fib(n)); } return 0; }
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).