12
19/06/22 19/06/22 La récursivité La récursivité 1 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

22/01/2014 La récursivité 1 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

Embed Size (px)

Citation preview

Page 1: 22/01/2014 La récursivité 1 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

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

Page 2: 22/01/2014 La récursivité 1 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

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;

Page 3: 22/01/2014 La récursivité 1 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

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

Page 4: 22/01/2014 La récursivité 1 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

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

Page 5: 22/01/2014 La récursivité 1 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

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

Page 6: 22/01/2014 La récursivité 1 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

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! :)))

Page 7: 22/01/2014 La récursivité 1 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

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

Page 8: 22/01/2014 La récursivité 1 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

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

Page 9: 22/01/2014 La récursivité 1 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

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

Page 10: 22/01/2014 La récursivité 1 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

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

Page 11: 22/01/2014 La récursivité 1 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

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.

Page 12: 22/01/2014 La récursivité 1 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

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.