Probléme : récursivité
Fermé
assma.m
Messages postés
3
Date d'inscription
vendredi 17 octobre 2008
Statut
Membre
Dernière intervention
22 janvier 2009
-
22 janv. 2009 à 18:48
Mahmah Messages postés 496 Date d'inscription lundi 17 septembre 2007 Statut Membre Dernière intervention 22 juin 2010 - 24 janv. 2009 à 23:25
Mahmah Messages postés 496 Date d'inscription lundi 17 septembre 2007 Statut Membre Dernière intervention 22 juin 2010 - 24 janv. 2009 à 23:25
1 réponse
Mahmah
Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
125
24 janv. 2009 à 23:25
24 janv. 2009 à 23:25
Salutations,
Tout d'abord je me permets de remettre le même code un peu mieux disposé.
Dans tout exercice de récursivité on retrouvera des cas d'arrêts et un ou des cas généraux. Le premier travail pour écrire ou comprendre un algorithme récursif est d'identifier ces deux parties. (On voit très bien ici pourquoi il faut commenter son code...)
1) Le cas général :
Cela ressemble d'ailleurs à l'énoncé : au tout début de la procédure un '$' est écrit pour noircir une case, puis on recommence avec x + 1 et y - 1. Le cas général est trouvé, à partir d'une case il trace la case suivante dans la diagonale.
Le rôle des variables est également très important, ici le cas général ne permet pas de comprendre le rôle de x_droite ou y_bas.
On remarque que ce cas général ne suffit pas à tracer toutes les diagonales mais une seule, le reste du code regroupe donc des cas d'arrêts et une autre partie qui sert à changer de diagonale à dessiner.
2) Les cas d'arrêts :
Pour une fois dans ce code, c'est commenté (Youpi !)
Premier cas d'arrêt :
Autres cas d'arrêt :
Essayons de comprendre le reste :
Pour comprendre l'algorithme, une bonne façon de faire est de l'exécuter soi-même (avec une feuille et un crayon)
J'ai vu sur un site que le tout premier appel était trace ( 1, 1, 1, 1, 1 )
1)
2)
3)
4)
x qui valait 1 reste 1 (x_droite)
y qui valait 1 devient 2
Si y dépasse la limite du tableau, on lui retire 1
y_bas devient 2 aussi.
5)
On trace la case suivante avec trace( 1, 2, 1, 2, 2 );
6)
Dans ce nouvel appel, y n'est pas 1 et x ne dépasse pas dim, le cas général est exécuté :
trace ( 2, 1, 1, 2, 3 )
7)
y = 1 : on peut remarquer dans le 4) que tant que x >= dim est faux et que y > dim est faux, ce morceaux de code ne va faire que incrémenter mettre y_bas + 1 dans y et x_droite dans x
Ici, le code va dessiner les premières diagonales en appelant successivement les procédures suivantes :
trace( 1, 1, 1, 1, 1 ) y = 1 -> première diagonale finie
trace( 1, 2, 1, 2, 2 ) -> cas général
trace( 2, 1, 1, 2, 3 ) y = 1 -> deuxième diagonale finie
trace( 1, 3, 1, 3, 4 ) -> cas général
trace( 2, 2, 1, 3, 5 ) -> cas général
trace( 3, 1, 1, 3, 6 ) y = 1 -> troisième diagonale finie
trace( 1, 4, 1, 4, 7 ) -> cas général
trace( 2, 3, 1, 4, 8 ) -> cas général
trace( 3, 2, 1, 4, 9 ) -> cas général
trace( 4, 1, 1, 4, 10 ) y = 1 -> quatrième diagonale finie
trace( 1, 5, 1, 5, 11 ) -> cas général
...
C'est de cette manière que j'ai compris l'utilisation de x_droite et y_bas : il donne le point de départ de la diagonale courante pour savoir quelle sera la suivante à dessiner.
Lorsque l'on dessine les diagonales les premières sont finies lorsqu'elles ont atteint la première ligne du tableau
Ensuite, dans la deuxième moitié du tableau, on sait quand une diagonale est finie lorsque celle-ci touche le bord droit du tableau. c'est ce qui est fait dans if x >= dim then
x_droit et y_bas vont donc désigner toutes les cases de la première colonne puis toutes celles de la dernière lignes.
On peut donc remarquer que l'auteur a manqué de logique :
lorsqu'il dessine la première moitié, celles qui sont au dessus de la plus grande diagonale, on ne peut pas avoir fini de dessiner tout le tableau, donc dans le code suivant :
Le total de cases dessinées est obligatoirement plus petit que le nombre total de cases du tableau (dim * dim)
(sauf dans le cas où dim vaut 1)
L'auteur, afin de rendre son code plus illisible a choisi de faire systématiquement le même test avant tous les appels à la procédure récursive (if total_posees < dim * dim then // carré rempli ?) Il aurait suffit de faire ce test au début de la procédure. Il se serait rendu compte ce test est le même que celui qui est déjà fait (if (x >= dim) and (y >= dim) then) puisque avoir rempli le tableau jusqu'à x et y = dim revient à avoir le atteint le nombre total de cases. le dernier paramètre est donc inutile. (Je me serait attendu à faire le premier appel à la fonction avec les paramètres trace ( 1, 1, 1, 1, 0 ) puisque lorsque je demande de tracer le nombre de cases déjà dessinées est zéro, en tout cela me parait plus logique)
Je ne sais pas si j'ai bien expliqué ce que j'avais compris de ce code donc : J'écoute toutes tes questions ;-)
Je te laisse le soin de simplifier ce code et de le ré-écrire dans les autres langages. N'hésite surtout pas à poster ces codes en même temps que tes questions si tu veux notre avis sur ceux-ci.
Voili voilou, à bientôt,
M.
Tout d'abord je me permets de remettre le même code un peu mieux disposé.
procedure trace(x, y, x_droite, y_bas, total_posees: integer); begin tab[x, y] := '$'; afficher_tableau; if (x >= dim) and (y >= dim) then exit; // point d'arrêt if y = 1 then begin if x >= dim then inc(x_droite); // effet de bord x := x_droite; y := y_bas + 1; if y > dim then dec(y); // effet de bord y_bas := y; if total_posees < dim * dim then // carré rempli ? trace(x, y, x_droite, y_bas, total_posees + 1); end else if x >= dim then begin if y_bas = dim then inc(x_droite); // effet de bord x := x_droite; y := y_bas; if total_posees < dim * dim then // carré rempli ? trace(x, y, x_droite, y_bas, total_posees + 1); end else if total_posees < dim * dim then // carré rempli ? trace(x + 1, y - 1, x_droite, y_bas, total_posees + 1); end;
Dans tout exercice de récursivité on retrouvera des cas d'arrêts et un ou des cas généraux. Le premier travail pour écrire ou comprendre un algorithme récursif est d'identifier ces deux parties. (On voit très bien ici pourquoi il faut commenter son code...)
1) Le cas général :
if ( y = 1 ) -> Pas ici ... else if ( x >= dim ) -> pas ici ... else ... -> Il ne reste plus que ici
Cela ressemble d'ailleurs à l'énoncé : au tout début de la procédure un '$' est écrit pour noircir une case, puis on recommence avec x + 1 et y - 1. Le cas général est trouvé, à partir d'une case il trace la case suivante dans la diagonale.
Le rôle des variables est également très important, ici le cas général ne permet pas de comprendre le rôle de x_droite ou y_bas.
On remarque que ce cas général ne suffit pas à tracer toutes les diagonales mais une seule, le reste du code regroupe donc des cas d'arrêts et une autre partie qui sert à changer de diagonale à dessiner.
2) Les cas d'arrêts :
Pour une fois dans ce code, c'est commenté (Youpi !)
Premier cas d'arrêt :
if (x >= dim) and (y >= dim) then exit; // point d'arrêtLa case à dessiner est la dernière en bas à droite.
Autres cas d'arrêt :
if total_posees < dim * dim then // carré rempli ?Si le nombre de cases dessinées n'est pas atteint on dessine une case en rappelant trace (on cherchera après la quelle) sinon, la fonction se termine sans se rappeler elle-même, donc fin de la récursivité.
Essayons de comprendre le reste :
Pour comprendre l'algorithme, une bonne façon de faire est de l'exécuter soi-même (avec une feuille et un crayon)
J'ai vu sur un site que le tout premier appel était trace ( 1, 1, 1, 1, 1 )
1)
tab[x, y] := '$';La case x = 1, y = 1 est noircie.
2)
if y = 1 thenC'est vrai
3)
if x >= dim then inc(x_droite); // effet de bordC'est faux, d'ailleurs ce cas ne sera vrai que pour la case la plus en haut à droite : y = 1 et x >= dim (ou en cas de dépassement vers la droite sur la première ligne)
4)
x := x_droite; y := y_bas + 1; if y > dim then dec(y); // effet de bord y_bas := y;
x qui valait 1 reste 1 (x_droite)
y qui valait 1 devient 2
Si y dépasse la limite du tableau, on lui retire 1
y_bas devient 2 aussi.
5)
trace(x, y, x_droite, y_bas, total_posees + 1);
On trace la case suivante avec trace( 1, 2, 1, 2, 2 );
6)
Dans ce nouvel appel, y n'est pas 1 et x ne dépasse pas dim, le cas général est exécuté :
trace ( 2, 1, 1, 2, 3 )
7)
y = 1 : on peut remarquer dans le 4) que tant que x >= dim est faux et que y > dim est faux, ce morceaux de code ne va faire que incrémenter mettre y_bas + 1 dans y et x_droite dans x
Ici, le code va dessiner les premières diagonales en appelant successivement les procédures suivantes :
trace( 1, 1, 1, 1, 1 ) y = 1 -> première diagonale finie
trace( 1, 2, 1, 2, 2 ) -> cas général
trace( 2, 1, 1, 2, 3 ) y = 1 -> deuxième diagonale finie
trace( 1, 3, 1, 3, 4 ) -> cas général
trace( 2, 2, 1, 3, 5 ) -> cas général
trace( 3, 1, 1, 3, 6 ) y = 1 -> troisième diagonale finie
trace( 1, 4, 1, 4, 7 ) -> cas général
trace( 2, 3, 1, 4, 8 ) -> cas général
trace( 3, 2, 1, 4, 9 ) -> cas général
trace( 4, 1, 1, 4, 10 ) y = 1 -> quatrième diagonale finie
trace( 1, 5, 1, 5, 11 ) -> cas général
...
C'est de cette manière que j'ai compris l'utilisation de x_droite et y_bas : il donne le point de départ de la diagonale courante pour savoir quelle sera la suivante à dessiner.
Lorsque l'on dessine les diagonales les premières sont finies lorsqu'elles ont atteint la première ligne du tableau
Ensuite, dans la deuxième moitié du tableau, on sait quand une diagonale est finie lorsque celle-ci touche le bord droit du tableau. c'est ce qui est fait dans if x >= dim then
x_droit et y_bas vont donc désigner toutes les cases de la première colonne puis toutes celles de la dernière lignes.
On peut donc remarquer que l'auteur a manqué de logique :
lorsqu'il dessine la première moitié, celles qui sont au dessus de la plus grande diagonale, on ne peut pas avoir fini de dessiner tout le tableau, donc dans le code suivant :
if y = 1 then begin ... if total_posees < dim * dim then // carré rempli ? trace(x, y, x_droite, y_bas, total_posees + 1);
Le total de cases dessinées est obligatoirement plus petit que le nombre total de cases du tableau (dim * dim)
(sauf dans le cas où dim vaut 1)
L'auteur, afin de rendre son code plus illisible a choisi de faire systématiquement le même test avant tous les appels à la procédure récursive (if total_posees < dim * dim then // carré rempli ?) Il aurait suffit de faire ce test au début de la procédure. Il se serait rendu compte ce test est le même que celui qui est déjà fait (if (x >= dim) and (y >= dim) then) puisque avoir rempli le tableau jusqu'à x et y = dim revient à avoir le atteint le nombre total de cases. le dernier paramètre est donc inutile. (Je me serait attendu à faire le premier appel à la fonction avec les paramètres trace ( 1, 1, 1, 1, 0 ) puisque lorsque je demande de tracer le nombre de cases déjà dessinées est zéro, en tout cela me parait plus logique)
Je ne sais pas si j'ai bien expliqué ce que j'avais compris de ce code donc : J'écoute toutes tes questions ;-)
Je te laisse le soin de simplifier ce code et de le ré-écrire dans les autres langages. N'hésite surtout pas à poster ces codes en même temps que tes questions si tu veux notre avis sur ceux-ci.
Voili voilou, à bientôt,
M.
