Opole, dn. 31 marca 2004

Laboratorium Algorytmów i Struktur Danych

Temat:

Analiza algorytmu obliczającego wyrazy ciągu Fibonacciego

Autor: Dawid Najgiebauer

Informatyka, sem. II, grupa lab. 11

Prowadzący: dr inż. Jan Sadecki

1. Temat

Napisać funkcję rekurencyjną obliczania n-tego elementu ciągu Fibonacciego. Obliczyć ilości wywołań rekurencyjnych dla n=5, 10, 15,..., 45. Napisać funkcję nierekurencyjną obliczania n-tego elementu ciągu Fibonacciego. Obliczyć ilości wykonanych podstawień.

2. Analiza, projektowanie

Celem badania jest sprawdzenie i porównanie metod wyszukiwania n-tego wyrazu dla ciągu Fibonacciego.

Zgodnie z tematem zostaną stworzone dwie funkcje - rekurencyjna i iteracyjna, które będą spełniać to zadanie.

1. Ciag Fibbonaciego

Ciąg Fibonacciego jest to ciąg liczb, w którym dwiema początkowymi są 0 i 1 (w niektórych założeniach przyjmuje się, że są to dwie jedynki), a kolejne liczby są sumą dwóch poprzednich liczb w ciągu. W przyjętym przypadku pierwszą liczbę uważa się za wyraz zerowy.

Tak więc liczby, wg tych założeń, układają się w następujący ciąg:

0, 1, 1 (0+1), 2 (1+1), 3 (1+2), 5 (2+3), 8, 13, 21, 34, 55, 89 itd...

2. Implementacja algorytmu - realizacja przez rekurencję

unsigned long fibbrek(int n)

{

wywrek++;

if (n==1) return 1;

if (n==0) return 0;

return fibbrek(n-1)+fibbrek(n-2);

}

3. Implementacja algorytmu - realizacja w sposób iteracyjny

unsigned long fibbite(int n)

{

unsigned long wm1=1,wm2=0,w=1;

if (n==1) return 1;

if (n==0) return 0;

for(int i=3;i<=n;i++)

{

wm2=wm1;

wm1=w;

w=wm1+wm2;

podst+=3;

}

return w;

}

3. Wyniki badania

Wynika badania przedstawiono w tabelce:

N	Ilość wywołań dla algorytmu rekurencyjnego	Ilość podstawień dla algorytmu iteracyjnego
5	15	9
10	177	27
15	1 973	42
20	21 891	57
25	242 785	72
30	2 692 537	87
35	29 860 703	102
40	331 160 281	117
45	3 672 623 805	132

4. Uwagi i wnioski z testowania i uruchamiania

1. Realizacja w sposób rekurencyjny jest dużo bardziej czasochłonna.

2. Ilość wywołań funkcji rekurencyjnej rośnie wykładniczo do zadanego numeru wyrazu ciągu.

3. Ilość podstawień w funkcji iteracyjnej rośnie liniowo wobec zadanej wartości.

4 Dawid Najgiebauer

Wyniki badania 5

Temat 3