Bonjour,
 
Je bloque sur un exos de TP, je vais vous l'exposer:

 
Bon alors évidement, tout le monde ce doute que j'ai le début :
 

 
Et la le noir totale, plus rien!
 
DOnc si on pouvais me filer un coup de pouce! Merci !

Bah t'écris une boucle qui pour chaque itération utilise les résultats des itérations précédentes.
 
Au passage, ca doit craquer l'exemple chez google.

je sait que ça doit craquer mais j'essaye de trouver seul, donc avec des pistes uniquement.

Euuuh la première erreur, c'est que la suite de Fibonacci renvoie 0 si on lui donne 0, pas 1.
 
Sinon, ben commences par créer une fonction récursive qui réplique exactement la définition de l'algo.

J'en refais un avec les switch/case ?

+1

 
Si tu sèches déjà sur cet algo de base, je crains pour la suite. D'ailleurs c'est plus un topic "algo" que "C"...
Tu définis un tableau "int u[3]={1, 1, 0}"
Tu fais une itération de 1 à n
A chaque boucle, tu recalcules "u[2]" en fonction de "u[0]" et "u[1]" puis tu copies "u[1]" dans "u[0]" puis "u[2]" dans "u[1]" comme ça les valeurs sont prêtes pour recalculer "u[2]" au tour de boucle suivant.
En fin de boucle, tu affiches "u[2]"...
 

Utiliser la récursivité sur Fibonacci, c'est aller droit dans le mur. Essaye de calculer "fib(26)" en récursif...

stack overflow spotted  

J'ai parlé de commencer comme ça, sans vouloir être méchant au stade où il en est c'est largement suffisant d'utiliser la définition canonique

fibbase 0 = 0
fibbase 1 = 1
fibbase n = fibbase (n-1) + fibbase (n-2)

 
C'est un peu trop facile en fait, alors je vais plutôt te donner une implé récursive qui sort du fibo(5000) ok?

Math> fibo 5000
3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

Implé:

module Math where

fiboIter 0 a _ = a
fiboIter x a b = fiboIter (x - 1) b (a + b)

fibo x = fiboIter x 0 1

Pipeau ahead, captain.
 
$ ./fib 48
fib 48 -> 4807526976
 
En C, récursif et super lent.

Je n'ai pas parlé de cet exemple en particulier, un stack overflow n'arrive pas pour une boucle si petite et cela dépend aussi du langage utilisé et de la ram libre disponible.

Primo, ce n'est pas une boucle puisque c'est récursif. Secundo, qu'essayes tu donc de dire? Je rappelle que nous sommes dans la section 'C' du forum et qu'il y a fort peu de chance qu'un tel overflow arrive, même dans une implementation particulierement déficiente, avant que d'exploser la limite généralement constatée des 32bits par int; cf le code du post initial.

fibbase 0 = 0
fibbase 1 = 1
fibbase n = fibbase (n-1) + fibbase (n-2)

Math> fibo 5000
3878968454388325633701916308325905312082127714646245106160597214895550139044037097010822916462210669479293452858882973813483102008954982940361430156911478938364216563944106910214505634133706558656238254656700712525929903854933813928836378347518908762970712033337052923107693008518093849801803847813996748881765554653788291644268912980384613778969021502293082475666346224923071883324803280375039130352903304505842701147635242270210934637699104006714174883298422891491273104054328753298044273676822977244987749874555691907703880637046832794811358973739993110106219308149018570815397854379195305617510761053075688783766033667355445258844886241619210553457493675897849027988234351023599844663934853256411952221859563060475364645470760330902420806382584929156452876291575759142343809142302917491088984155209854432486594079793571316841692868039545309545388698114665082066862897420639323438488465240988742395873801976993820317174208932265468879364002630797780058759129671389634214252579116872755600360311370547754724604639987588046985178408674382863125

module Math where

fiboIter 0 a _ = a
fiboIter x a b = fiboIter (x - 1) b (a + b)

fibo x = fiboIter x 0 1

 
Arrête de te la raconter. Evidemment si tu utilises un langage que je ne connais pas mais qui semble adapté maths, tu arriveras à calculer fib(5000) mais tu sais parfaitement qu'on est en C. Et une fonction récursive C pour calculer Fibonacci arrivera péniblement à fib(26) et mettra 2 fois plus de temps pour calculer fib(28) car il lui faudra calculer 2 fois fib(26). Et encore 2 fois plus de temps pour fib(30) etc. Ou alors on crée une fonction récursive intelligente qui détecte les valeurs déjà calculées pour ne pas les recalculer à chaque fois. Mais là, on sort du TP de base...

Chacun voit midi à sa porte. Moi je conseille de toujours tenter d'éviter la récursivité autant que possible car elle peut paraître alléchante mais on n'imagine pas le boulot de l'ordi par derrière... Et là, c'est franchement facile de ne pas faire du récursif...

WTF
 
J'ai juste prouvé que tu avais tord, rien de plus  

Ce n'est pas le cas, on peut faire la même chose en C, mais j'avais (et j'ai toujours) autre chose à faire que l'implémenter en C.
 
Le langage est Haskell, sa notation est très proches des mathématiques mais il n'a pas une implémentation spécialement dédiée aux maths (en dehors du fait qu'il est fonctionnel), contrairement à, disons, un Matlab

C'est très exactement ce que fait la première implémentation
 
C'est d'ailleurs la raison pour laquelle tu n'as pas vu de fib(5000) avec la première version

On memoize quoi.

Je sais pas si t'as remarqué, mais là le monsieur a déjà des problèmes avec l'IO, donc les optimisations du genre "implémente la fib en itératif plutôt qu'en récursif" j'pense que ça peut être vu après si tu veux, qu'il commence par l'implé canonique et par la suite il pourra en utiliser d'autres.

alors c'est bien beau tout ça mais moi en cour, j'en suis au boucle et au base de focntion.
 
D'ailleur, je doit faire cette exos a base de for(instruction;conditions;instruction);
 

Ben c'est la méthode de Sve@r alors.

Ce n'est pas la "mienne", c'est celle de la "logique". Juste une petite erreur dans la méthode en question: la boucle doit démarrer à 2 et non à 0...
 

 
La méthode que j'ai expliquée hier. Si t'as pas appris les tableaux, alors la même sans ces derniers...
Tu définis 3 unsigned int a, b et c (unsigned long c'est même encore mieux).
Tu initialises "a" et "b" à 1 car ce sont les 2 premiers termes de la suite
Tu fais une itération de 2 à n (départ à 2 car les valeurs U0 et U1 sont déjà présentes dans "a" et "b" )
A chaque boucle, tu recalcules "c" en fonction de "a" et "b" puis tu copies "b" dans "a" puis "c" dans "b" comme ça les valeurs sont prêtes pour recalculer "c" au tour de boucle suivant.  
En fin de boucle, tu affiches "c"...