MWPZ - Mistrzostwa Wielkopolski w Programowaniu Zespolowym

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:

var
  d,n,i : longint;
   
function fib(x: longint): longint;
{
   funkcja zostala wyprowadzona ze wzoru:
    _    _  x      _                 _
   | 0  1 |       | fib(x-2) fib(x-1) |
   |      |    =  |                   |
   |_1  1_|       |_fib(x-1) fib(x)  _|
}
var
  i,j,k,h,t: longint;
begin
  i:=1; j:=0; k:=0; h:=1; t:=0;
  while x>0 do
  begin
  if odd(x) then
    begin
      t:=(j*h) mod 10000;
      j:=(i*h+j*k+t) mod 10000;
      i:=(i*k+t) mod 10000;
    end;
    t:=(h*h) mod 10000;
    h:=(2*k*h+t) mod 10000;
    k:=(k*k+t) mod 10000;
    x:=x div 2;
  end;
  fib:=j;
end;
  
begin
  readln(d);
  while (d>0) do
  begin
    d:=d-1;
    readln(n);
    writeln(fib(n));
  end;
end.

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*10⁹ 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.

Dalej

Wstecz