Rendre un alogorithme C plus rapide !

Question

Bonjour @ tous ! Voici j'ai un algo en C. Cet algo sert à calculer la suite de fibonacci. Pour ceux qui ne la connaisse, ma suite de fibonacci est définie par : u(0)= 1 u(1)=1 u(n)=u(n-1)+u(n-2) J'ai donc créer un algo qui permet de faire ce calcul ! Le voila : #include #include int fibonacci(int n) { if(n<2) { return 1; }else{ return fibonacci(n-1)+ fibonacci(n-2); } } Pour l'appeller voilà ce que j'utilise : int main() { int n; scanf("%d", &n); printf("%d ", fibonacci(n)); return 0; } Mon problème dès que n>35 le temps d'éxécution de mon algo commence à devenir long ! Voila des contraintes qui mon été impossées : LIMITES DE TEMPS ET DE MEMOIRE

Temps : 0.25 s sur une machine à 1Ghz.

Mémoire : 2000 Ko.

CONTRAINTES

n < = 5000

u(n) < 1000000000

Merci de m'aider à améliorer cette alogo pour qu'il aille plus vite ! @++ Optitech C'est super le forum de Codes-sources.com ! On trouve tout ce que l'on a besoin !

vecchio56 · Answer

C'est très simple, un petit tableau te suffit. Le tout c'est de pas faire ca de manière récursive, sinon tu calcules plein de fois la même chose
Un tableau de 2 éléments devrait suffire, mais pour commencer, tu peux faire avec un tableau de n éléments si tu veux calculer fibo(n)

BruNews · Answer

Essaie, devrait aller:

DWORD Fibonacci(DWORD n)
{
  if(n < 2) return 1;
  DWORD i = 2;  DWORD d 0, a 0, b = 1;  while(i++ <n) {d a + b; a = b; b = d;}
  return d;
}

ciao...
http://dev.winsysdev.com
BruNews, MVP VC++

vecchio56 · Answer

Fallait pas lui donner la réponse, c'est pour un concours :)

Optitech · Answer

C'est pour ca que j'ai modif&#233; l'enonc&#233;e !

Optitech 

C'est super le forum de Codes-Sources.com ! On trouve tout ce que l'on a besoin !

BruNews · Answer

ben vraiment je ne fais que des conneries aujourd'hui, d&#233;sol&#233;.

ciao...
http://dev.winsysdev.com
BruNews, MVP VC++

neodelphi · Answer

C'est pas grave c pour le prologin je parie lol...

neodelphi

Rendre un alogorithme C plus rapide !

6 réponses

Votre réponse

Discussions similaires