Ciag Fibonacciego

[raven_ns]

Witam, postanowilem napisac algorytm w c na obliczanie n tego wyrazu ciagu Fibonacciego, jednak sa z nim pewne problemy np nie oblicza wyrazu dla "n" wiekszego od 200, wiecie moze jak temu mozna zaradzic , jezeli macie jakies inne pomysly na rozwiazanie tego problemu -bardziej ekonomiczne czasowo to prosze je tutaj przedstawic.

 

A zadanie brzmialo tak :

 

Napisać program obliczający wartość n-tego wyrazu ciągu Fibonacciego, a więc zdefiniowanego jak następuje:

 

 

Si = 1 dla i = 1

Si = 2 dla i = 2

Si = Si-1 + Si-2 dla i > 2

 

i musi być > 0

I oczywiscie kodzio :) :

#include <stdio.h>#include <stdlib.h>int main(){  int q, a, b, n, z;  q=0, a=0, b=1;  printf("Podaj numer szukanego wyrazu ciagu Fibonacciego\n");  scanf("%d", &z);if (z==0)  {	 printf("Podaj liczbe wieksza od zera\n"); 		system("PAUSE");		}if (z==2)  {	 printf("Wartosc szukanego przez ciebie wyrazu ciagu wynosi 1\n"); 		system("PAUSE");		}else {  	 while (q<z-2)	 {		n=a+b;		a=b;		b=n;		q++;	  }    printf("Wartosc szukanego przez ciebie wyrazu ciagu wynosi %d\n", n);   system("PAUSE");	  }  }

Edytowane 30 Listopada 2005 przez raven_ns

[Haquim]

 

Szybciej to mozna w taki sam sposób jak przy poszukiwaniu liczb pierwszych :) :

zapisz kilka pierwszych wartości w tablicy .

A tak w ogóle to jaki wynik masz dla n=199 co? Zamień int na long long (64 bitowe liczby całkowite w gcc)

[raven_ns]

zgadza sie dla wiekszych wartosci to liczy kosmicznie :) ,ten int tutaj nie pasuje popieram :)

[kfgz]

@raven_ns

 

Zamiast liczenia sumy liczb ciągu w pętli możesz skorzystać z poniższego wzoru:

 

[vtg]

Można sobie napisać funkcje z zastosowaniem rekurencji:

 

unsigned fibonacci(unsigned n) {

if(n < 2) return 1;

else

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

}

[Sam Sung]

unsigned fibonacci(unsigned n) {

if(n < 2) return 1;

else

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

}

Obliczanie n-tego wyrazu ciągu Fibbonacciego oraz obliczanie silni z n to 2 doskonałe przykłady na to, kiedy nie należy stosować rekurencji :-|

[Gierwazy]

OMG przeciesz rekurencja to najszybszy sposob to przeciążenia, a co najmniej obciążenia systemu...

wyobraz sobie ze juz przy 5 elemencie ciągu w wyniku rekurencji ta funkcja powtazana jest 15 razy!

 

juz bardziej polecam zastosowanie petli for (choć są zapewne leprze i szybsze sposoby ;) ):

 

int fib(int n)

{

int minusTwo=1, minusOne=1, answer=2;

 

if (n < 3)

return 1;

 

for (n -= 3; n; n--)

{

minusTwo = minusOne;

minusOne = answer;

answer = minusOne + minusTwo;

}

 

return answer;

}

 

dla n-tej pozycji ciągu

[Sam Sung]

juz bardziej polecam zastosowanie petli for (choć są zapewne leprze i szybsze sposoby ;) ):

(...)

Napisany przez Ciebie kod to prawie to samo co autor wątku zapodał w pierwszym poście :mur:

A jeden lepszy sposób też już jest w tym wątku - tylko trzeba go przejrzeć... konkretnie mam na myśli wzór ogólny podany przez DJ_AnT'a.