| 24.2.3.24011240. Napisati funkcije “FibIter“ i “FibRek“ i “FibRekBrza“ koje primaju jedan cjelobrojni parametar “N“, a koje računaju N-ti Fibonačijev broj respektivno iterativnim postupkom, klasičnim rekurzivnim postupkom, i rekurzivnim postupkom uz provedenu tehniku ubrzavanja (memoizaciju). Uporediti brzine izvršavanja sve tri funkcije za N = 30, N = 35 i N = 40. Zaključke zapisati u svesku. Također eksperimentalno provjeriti koliko puta funkcije “FibRek“ i “FibRekBrza“ pozovu same sebe u ova tri slučaja i zabilježiti rezultate. (Uputa: Definirajte neku globalnu promjenljivu koja se uvećava za 1 unutar tijela funkcije “FibRek” odnosno “FibRekBrza”. Prije poziva funkcije postavite ovu promjenljivu na nulu, a nakon poziva funkcije ispišite njenu vrijednost).
Opis rješenja:
Listing programa:
#include <iostream>
#include <conio.h>
using namespace std;
int j;
int FibIter(int n){
if(n<3)return 1;
int a(1),b(1),c,i(3);
while((n/i++)>=1){
c=a+b;
b=a;
a=c;
}
return a;
}
int FibRek(int n){
j++;
if(n<3){if(j==1)j--;return 1;}
return FibRek(n-1)+FibRek(n-2);
}
int FibRekBrza(int n){
const int c(100);
static int F[c];
if(F[n]!=0)return F[n];
if(n<3)return F[n]=1;
else {
if(j<3)j+=3;
else j++;
return F[n]=FibRekBrza(n-1)+FibRekBrza(n-2);
}
}
int main(){
int N;
cin>>N;
j=0;
cout<<FibIter(N);
j=0;
cout<<endl<<FibRek(N);
cout<<endl<<j;
j=0;
cout<<endl<<FibRekBrza(N);
cout<<endl<<j;
getch();
return 0;
}
Izvođenje programa:
Riješeni zadaci 2 Index
|
 |
