Discussion :

[sayari7]

Bonjour à tous:

l'énoncé de l'exercice:

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[droggo]

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).

[Graffito]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[sayari7]

Merci énormément Graffito


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

[droggo]

Keo,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Wachter]

Bonsoir,

Keo,

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

Tu voulais parler de ça ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

[droggo]

Jei,

Bonsoir,


Tu voulais parler de ça ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.