Citat:
bags:
Moram uraditi algoritam za fibbonaci niz ali sa vremenom O(n) plus mora biti rekurzivan.
:) Dakle ceo niz + rekurzivan + O(n), tako da je samo ovo poslenje rešenje ispravno, kako se meni čini
BTW, da nije uslov rekurzija i da ne treba ceo niz, moglo bi na još par načina da se odradi, evo nešto napamet, moguće je i da ne radi tačno, ali bar je ideja tu
Code:
// O(n)
int fibonaci1(int n)
{
int f2 = 1; // f(0) = 1
int f1 = 1; // f(1) = 1
int i;
for(i=2; i<=n; i++)
{
f = f2 + f1;
f2 = f1;
f1 = f;
}
return f;
}
// O(1) - uslovno, ako zanemarimo slozenost funkcije pow
int fibonaci2(int n)
{
float sqrt5 = pow(5, 0.5) / 0.5;
return (int) ((pow(0.5 + sqrt5, n) - pow(0.5 - sqrt5, n)) / (sqrt5 * 2.0));
}
ex.
trooper
Oh goody... it's my Illudium PU-36 Explosive Space Modulator!
Softversko Inženjerstvo
♪♫♪