Calcul d'une suite numérique avec une approche itérative et récursive

Bonjour à tous:

l'énoncé de l'exercice:

Citation:

---

Soit la suite (U) définie par:
U0= 2
U1= 3
Un = Un-1+ 2*Un-2 pour tout n >= 2

ecrire un programme qui saisi un entier n , calcul et affiche Un

---

Voici ma solution récursive:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

uses wincrt; var n:integer;   function calcul (n:integer):integer;     begin     if n=0 then calcul:=2 else if n=1 then calcul:=3 else begin     calcul:=calcul(n-1)+2*calcul(n-2); end;   end;   begin write('N= '); readln(n); write(calcul(n)); end.

---

je n'a pas pu formuler la solution itérative.

Goe,

Pour trouver, il suffit d'analyser un peu la formule, OU, d'analyser la liste des quelques premières valeurs obtenues (plus facile, car ça saute littéralement aux yeux). :)

Code:

---

1 2 3 4 5

x:=2 ; y:=3 ; // ... traiter cas particuliers (n<2) for i=2 to n do begin z:=y+2*x ; x:=y ; y:=z ; end ; result:=z

---

Merci énormément Graffito


http://www.developpez.net/forums/ima...es/yaisse2.gif
:yaisse2:

Keo,

Citation:

---

Envoyé par Graffito

Code:

---

1 2 3 4 5

x:=2 ; y:=3 ; // ... traiter cas particuliers (n<2) for i=2 to n do begin z:=y+2*x ; x:=y ; y:=z ; end ; result:=z

---

---

On peut faire mieux (calcul direct sans la moindre boucle :)).

Nettement mieux même, car la boucle montrée ici ne fait que calculer toutes les valeurs qui seraient renvoyées par la fonction de 0 à n (si on a ajouté le traitement des cas n=0 et 1), ce qui n'est pas très efficace.

Bonsoir,

Citation:

---

Envoyé par droggo

Keo,

On peut faire mieux (calcul direct sans la moindre boucle :)).

---

Tu voulais parler de ça ? 8-)

Code:

---

Un = (5 * 2^n + (-1)^n) / 3

---

Citation:

---

Envoyé par droggo

Nettement mieux même, car la boucle montrée ici ne fait que calculer toutes les valeurs qui seraient renvoyées par la fonction de 0 à n (si on a ajouté le traitement des cas n=0 et 1), ce qui n'est pas très efficace.

---

Cependant, ce n'est pas vraiment intéressant de l'utiliser si on débute en programmation, ce qui est le cas ici : le posteur du message désire apprendre les bases de la programmation et par la même occasion, comment fonctionne une boucle, entre autres. Il ne cherche donc pas à optimiser son programme et non plus une formule « magique » comme celle sus-citée. Bref, je rejoins Graffito quoique je comprends parfaitement ta réaction ! ;)

--
Wachter

Jei,

Citation:

---

Envoyé par Wachter

Bonsoir,


Tu voulais parler de ça ? 8-)

Code:

---

Un = (5 * 2^n + (-1)^n) / 3

---

Cependant, ce n'est pas vraiment intéressant de l'utiliser si on débute en programmation, ce qui est le cas ici : le posteur du message désire apprendre les bases de la programmation et par la même occasion, comment fonctionne une boucle, entre autres. Il ne cherche donc pas à optimiser son programme et non plus une formule « magique » comme celle sus-citée. Bref, je rejoins Graffito quoique je comprends parfaitement ta réaction ! ;)

--
Wachter

---

Il cherche à écrire une version non récursive. Il n'est dit nulle part qu'il s'agit d'apprendre à faire une boucle.

Et à partir du moment où on se passe de la récursivité, autant écrire le code le plus performant, et non une boucle qui ne fait finalement que cacher la récursivité en refaisant tout le calcul à chaque appel. :)