Tutorial
A może by tak jeszcze szybciej?
Jeżeli ktoś bardzo chce, to może zaimplementować jeszcze szybszy algorytm niż ten, który widzieliście przed chwilą. Wygląda on następująco:
#include <stdio.h>
int d,n,i;
int fib(int x)
/*
funkcja zostala wyprowadzona ze wzoru:
_ _ x _ _
| 0 1 | | fib(x-2) fib(x-1) |
| | = | |
|_1 1_| |_fib(x-1) fib(x) _|
*/
{
int i=1, j=0, k=0, h=1, t=0;
while (x>0)
{
if (x%2==1)
{
t=(j*h)%10000;
j=(i*h+j*k+t)%10000;
i=(i*k+t)%10000;
}
t=(h*h)%10000;
h=(2*k*h+t)%10000;
k=(k*k+t)%10000;
x=x/2;
}
return j;
}
int main()
{
scanf("%d\n",&d);
while (d--)
{
scanf("%d\n",&n);
printf("%d\n",fib(n));
}
return 0;
}
Nie wnikajmy dlaczego to działa, bo wymaga to trochę bardziej zaawansowanej matematyki (raczej nie wymaganej na zawodach), ale działa ;). Dlatego Sprawdzarka również oceni ten program na:
Accepted
Powyższy program ma złożoność czasową O(logN), czyli znacznie lepszą od złożoności O(N) poprzedniego programu. W ogólności powinniście zaimplementować program o jak najlepszej złożoności, ale w tym konkretnym przypadku nasz wysiłek był nadmiarowy, bo już poprzedni program bez trudu zostałby zaakceptowany. Skąd ta pewność? Ze złożoności O(N) oraz z faktu, że N ≤ 20000 można wywnioskować, że dla każdego zestawu testowego program wykona rzędu 20000 operacji w najgorszym wypadku (pamiętajcie, że to tylko zgrubne oszacowanie!), co zajmie mu pojedyncze milisekundy (dopiero wchodząc w miliony operacji czas zaczyna być zauważalny). Sprawdzarka tego nie wychwyci (limity czasu raczej nie są mniejsze od 50ms). Z drugiej strony, jeśli Wasz program będzie wykonwyać dużo operacji, nawet setki milionów czy miliardy, to jeszcze nie znaczy, że jest zły (choć nie spodziewalibyśmy się limitów powyżej kilku sekund to nie można tego wykluczyć). Może przecież nie istnieć lepszy algorytm. To do Was należy ocenienie czy tak jest. Np. gdyby w tym zadaniu było ograniczenie N ≤ 2*109 to poprzedni program będzie działać długo, a że istnieje dużo lepszy, to należy przyjąć, że dostałby ocenę Time Limit Exceeded. Podsumowując, z ograniczeń na dane można wyciągnąć pożyteczne wnioski, ale podchodźcie do tego ostrożnie i sceptycznie, bo może to Was też zmylić — robicie to na własną odpowiedzialność!
Inna możliwość ulepszenia poprzedniego programu (równie zbędna w tym przypadku, ale wspominamy, bo technikę można użyć przy innych zadaniach) to wyliczenie wszystkich liczb Fibonacciego raz, by dla każdego zestawu testowego już ją tylko wypisać. Uważajcie jednak, żeby nie liczyć liczb większych niż pojawiają się na wejściu, bo testy wcale nie muszą zawierać dużych liczb (dla takich testów oczywiście limity czasowe będą odpowiednio mniejsze). Kolejna możliwość ulepszenia to wygenerować na swoim stanowisku program z tablicą statyczną zawierającą wszystkie wyniki. Jednak w tym przypadku to nie przejdzie, ponieważ wysyłany kod źródłowy nie może mieć więcej niż 20kB.
Warto tutaj jeszcze zaznaczyć, że kluczem do szybkości działania programu jest złożoność czasowa algorytmu. Raczej nie spodziewajcie się, że mając kiepski algorytm ulepszycie go zwykłymi optymalizacjami kodu czy specjalną obsługą przypadków szczególnych (nawet napisanie programu w assemblerze nie pomoże). Z drugiej strony, mając algorytm o poprawnej złożoności, najprawdopodobniej zmieści się on w limitach czasu, ... no chyba że napiszecie go wysoce nieoptymalnie.