Upload
norberta-benoist
View
104
Download
0
Embed Size (px)
Citation preview
11/04/2311/04/23 La récursivitéLa récursivité 11
Problème de 8 dames:
Sachant que dans un jeu des échecs, une dame peut pendre toute pièce se trouvant sur la colonne ou sur la ligne ou sur les diagonales de la case qu’elle occupe, le problème consiste à trouver toutes les solutions possibles pour placer 8 dames sur un échiquier sans qu’aucune dame ne peut prendre une autre comme le montre la figure ci-contre
Solution N° 1
11/04/2311/04/23 La récursivitéLa récursivité 22
Problème de 8 dames:
Il existe plusieurs façons pour résoudre ce problème. Dans ce qui suit on va adopter la méthode suivante:
Structure de données:Caque dame sera défini par son numéro et les positions des dames qui ont étaient posées.NBDAMES = 8;COORD =record X, Y: integer; end;Tdame = record Position: array [1..Nbdames] of COORD; Numdame: integer; end;
11/04/2311/04/23 La récursivitéLa récursivité 33
Problème de 8 dames:
On va définir une procédure qui permet de placer, chaque fois où c’est possible, une dame à sa bonne position. Si le nombre de dames est 8 on affiche la solution et on recommence de nouveau jusqu ‘à avoir tester toute les combinaisons possibles.
DD
DD
DD
DD
DD DD
Principe:la dame N ne peut être posée que sur la ligne N, donc on parcourt la ligne N de son de but jusqu’à sa fin (compteur j ) et on teste si la case (N,j) peut être occupée ou non par une dame sans intersection avec les dame précédente. Si oui on pose la dame à sa place et si le nombre de dame n’a pas atteint 8 on passe à la ligne suivante pour y placer une autre dame sinon on affiche la solution trouvée puis on recommence en revenant un pas en arrière pour chercher les éventuelle solutions
Dame à poser dans la ligne 5 peut occuper la colonne 4 ou 8 donc il faut chercher les combinaisons pour C4 et C8
11/04/2311/04/23 La récursivitéLa récursivité 44
0- procedure PLACE_Dame( dame: Tdame; N: entier);1- Pour J de 1 à Nbdames faire Si (Non intersection (dame, N, J)) alors Dame.NumDame dame.NumDame + 1; Dame.Position[Dame.NumDame].X N; Dame.Position[Dame.NumDame].Y J; Si N < NbDames Alors PLACE_Dame(Dame, N+1) Sinon
AffSolution(Dame); FinSi Dame.NumDame := Dame.NumDame – 1 FinSi FinPour2- Fin Place_Dame
Problème de 8 dames: Parcourt de toutes les cases de la ligne N de l’échiquier. La dame numéro N ne peut se placer que dans la ligne Numéro N.
Fonction qui vérifie si la case N,J peut être occupée par la dame
en cours ou non
si le nombre de dames placées est < nb des dames à placer alors placer la dame Numéro N+1} appel
récursif de la fonction
Si N = 8affichage de la
solution trouvéeRetour à la dame précédente pour trouver les éventuelles solutions restantes
11/04/2311/04/23 La récursivitéLa récursivité 55
Problème de 8 dames:
0- Fonction intersection( dame: Tdame; POSI, POSJ: Entier):booléen;1- inter := Faux; I 1; Tantque non inter et (I <= dame.NumDame) faire inter (POSI = dame.Position[I].x) ou (POSJ = dame.Position[I].y) ou (absolue(POSI - dame.Position[I].x) = absolue (POSJ - dame.Position[I].y)); I I + 1; Fin TantQue 2- intersection := inter 3- Fin Intersection ;
Algorithme de la fonction Intersection
Dame sur la même ligne
Dame sur la même colonne
Dame sur la même diagonale
11/04/2311/04/23 La récursivitéLa récursivité 66
Problème des Tours de Hanoï:
Un problème bien connu qui se résout très facilement par un algorithme récursif (et difficilement par un algorithme itératif) est "les tours de Hanoi". La légende dit que dans un temple de Hanoï, à l'origine du monde, 64 disques de diamètre croissant étaient empilés sur un taquet. Deux autres taquets sont disponibles, qui sont utilisés pour déplacer les disques, la condition étant qu'un disque d'un certain diamètre ne peut pas être placé au dessus d'un disque de diamètre inférieur. Donc, les disques sont toujours empilés dans un certain ordre: les plus grands sont toujours en bas du taquet. La légende dit aussi que des moines sont en train de déplacer les 64 disques vers l'un des deux autres, au rythme de un par seconde et quand ils auront terminé, ce sera la fin du monde. En faisant un petit calcul rapide, on a 264-1 secondes, ce qui correspond à 585 milliards d'années et sachant que l'âge de l'univers est de seulement 15 milliards d'années, on a encore de la marge : ouf ! On l'a échappé belle! :)))
11/04/2311/04/23 La récursivitéLa récursivité 77
Problème des Tours de Hanoï:
Voyons maintenant la programmation de cet algorithme.
On décide que les disques ont un numéro correspondant à leur diamètre, et que les diamètres vont de 1 à 64.
Nous allons d'abord étudier deux cas concrets de déplacement: comme d'habitude, d'abord on observe, ensuite on programme l'algorithme.
Soit deux disques à déplacer du taquet 1 vers le 3.Le taquet final est 3, celui initial est 1, donc celui intermédiaire est 2.Opérations de déplacement :- disque 1 de taquet 1 vers taquet 2- disque 2 de taquet 1 vers taquet 3 ---> milieu- disque 1 de taquet 2 vers taquet 3 1 2 3
11/04/2311/04/23 La récursivitéLa récursivité 88
Problème des Tours de Hanoï:
Soit trois disques à déplacer du taquet 1 vers le 3.Le taquet final est 3, celui initial est 1, donc celui intermédiaire est 2.Maintenant on doit se retrouver avec les deux premiers disques sur le taquet 2, de façon à pouvoir déplacer le disque 3 vers la taquet 3 et ensuite les deux premiers du taquet 2 vers le taquet 3.Opérations de déplacement :- disque 1 de taquet 1 vers taquet 3- disque 2 de taquet 1 vers taquet 2- disque 1 de taquet 3 vers taquet 2- disque 3 de taquet 1 vers taquet 3 - disque 1 de taquet 2 vers taquet 1- disque 2 de taquet 2 vers taquet 3- disque 1 de taquet 1 vers taquet 3
1 2 3
11/04/2311/04/23 La récursivitéLa récursivité 99
Problème des Tours de Hanoï:
En regardant bien les déplacements effectués, on constate les choses suivantes :- si on a "n" disques à déplacer :
- On déplace "n-1" disques vers le taquet intermédiaire
- On déplace le disque "n" du taquet initial vers le taquet final
- On déplace les "n-1" disques du taquet intermédiaire vers le taquet final
1 2 3
11/04/2311/04/23 La récursivitéLa récursivité 1010
Problème des Tours de Hanoï:
On peut d'ores et déjà en déduire l'algorithme :
0- procedure Deplacer(nb_disques, depart, arrivee:entier) 1- Si nb_disques = 1 Alors
Ecrire(depart,’ vers ‘ arrivee) Sinon intermediaire 6 - depart - arrivee deplacer (nb_disques - 1, depart, intermediaire);
Ecrire(depart,’vers’,arrivee) Deplacer(nb_disques - 1, intermediaire, arrivee); FinSi2- Fin Deplacer
Pour déplacer 4 disques du pilier 1 vers le pilier 3 par exemple appeler la procédure déplacer avec les paramètres suivants: deplacer (4, 1, 3);
11/04/2311/04/23 Formation AlgorithmiqueFormation Algorithmique 1111
Tri rapideTri rapidePrincipePrincipe On choisit un élément particulier appelé pivot.On choisit un élément particulier appelé pivot.
On réorganise le tableau (par échanges) de façon à avoir On réorganise le tableau (par échanges) de façon à avoir
les éléments inférieurs au pivot d’un coté et les éléments les éléments inférieurs au pivot d’un coté et les éléments
supérieurs d’un autre. Le pivot est alors à sa place supérieurs d’un autre. Le pivot est alors à sa place
définitive.définitive.
On recommence récursivement sur chacune de deux On recommence récursivement sur chacune de deux
parties tant qu'elle n'est pas réduite à un seul élément.parties tant qu'elle n'est pas réduite à un seul élément.
11/04/2311/04/23 1212
Choix du pivotChoix du pivot : :
L'idéal est de choisir une valeur médiane qui coupe le L'idéal est de choisir une valeur médiane qui coupe le tableau en deux parties à peu près égales, mais sa tableau en deux parties à peu près égales, mais sa recherche ralentit l’algorithme. recherche ralentit l’algorithme.
On peut prendre arbitrairement le premier élément, le On peut prendre arbitrairement le premier élément, le dernier ou celui du milieu. dernier ou celui du milieu.