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.

#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(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

Sponsor Główny	Sponsorzy	Partnerzy