1

I. Introduction

Ce chapitre traite des problèmes un peu plus complexes que les problèmes classiques déjà vus

comme de nouvelles méthodes de recherche, de tri, d'approximation ou d'optimisation.

Les algorithmes avancés utilisent le principe "diviser pour régner (divide to conquer) ".

II. Tours de Hanoï

1) Activité

Charger l’URL : http://www.toupty.com/jeutourshanoi.html

Charger l’URL : http://javaboy.free.fr/tourdehanoi/index.htm

Ouvrir le fichier C:\avancé\hanoi.exe

2) Principe :

Le but du problème est de passer en un minimum de déplacements ces N disques du piquet 1 sur le piquet

3 en s'aidant du piquet 2 qui peut servir à des stockages intermédiaires de disques. Les règles suivantes

doivent être respectées :

• on ne peut déplacer qu'un seul disque à la fois,

• un disque peut être déplacé d'un des trois piquets sur l'un des deux autres,

• un disque ne peut être placé que sur le sol ou sur un disque de diamètre supérieur.

1) Tours de Hanoï

2) Tri rapide

3) Huit dames (voir p234-240)

4) Voyageur de commerce (voir livre p226-233)

1 2 3

2

3) Application

Ecrire un programme modulaire en PASCAL, qui saisit N disques (1<=N<=64), affiche les déplacements

effectués.

Analyse du programme principal :

2) Résultat = Proc Hanoi (n, 1, 3, 2) 1) N = proc saisie (n)

Analyse de la procédure Hanoi :

DEF PROC Hanoi (n, depart, but, inter: entier)

Résultat= Hanoi

1) Hanoi =[ ] Si N =1 alors

Ecrire (''déplacer un disque de '',depart , '' en '', but)

sinon

Proc hanoi ( n-1, depart, inter, but )

Ecrire (''déplacer un disque de '', depart , '' en '', but)

Proc hanoi ( n-1, inter, but, depart )

Fin Si

3

III. Tri rapide

1. Activité

2. principe

C’est un algorithme considéré comme l'un des plus rapides, et des plus efficaces. C’est une méthode de

tri récursive basée sur la méthode de conception "diviser pour régner".

L’idée de l’algorithme est très simple ;

Etant donné un vecteur d’éléments à trier :

1. Choisir un élément arbitraire du tableau, que nous appelons élément pivot.

2. Réorganiser les éléments du tableau de sorte que tous les éléments inférieurs au pivot soient à gauche

du pivot, les éléments supérieurs au pivot soient à droite du pivot, ceux qui sont égaux soit à gauche soit à

droite et le pivot choisi entre les deux. Cette opération s’appelle partition.

3. Trier récursivement la partie gauche et la partie droite du tableau jusqu’à obtenir uniquement des sous

tableaux à un seul élément.

Comment choisir le pivot ?

Nous pouvons choisir comme pivot l’élément situé au milieu de la partie à trier. Comme on peut choisir le

premier élément.

3) Application

Ecrire un programme modulaire en Pascal qui remplit un vecteur T, par N entiers aléatoirement

(-100<=T[i]<=100; 5<=N<=50), le trier selon la méthode de tri rapide puis l’afficher.

Analyse du programme principal : 3) Résultat= Proc affiche (T, n) 2) T= Proc tri_rapide (T, 1, n) 1) (T, n) = Proc remplir (T, n)

Analyse de la procédure Tri_rapide

DEF PROC Tri_rapide (var T: Tab; g , d: entier) Résultat = T 1) T= [ ] Si g<d alors proc partition (T, g, d, indpivot) proc tri_rapide (T , g , indpivot-1) proc tri_rapide (T , indpivot+1 , d) Fin Si

4

Analyse de la procédure Partition DEF PROC Partition (var T: Tab; g, d : entier ; var indpivot: entier)

1) T, indpivot= i g+1 Répéter

pivot T[g] Tant que (i < indpivot) et (t[i] < pivot) Faire

indpivot d i i + 1

Fin tant que

Tant que (i <=indpivot) et (pivot <= T[indpivot]) Faire

indpivot indpivot - 1

Fin tant que

Si i<indpivot alors

proc Permut (T[i], T[indpivot])

i i + 1

Indpivot indpivot - 1

Fin si

Jusqu’à (indpivot<=i) Proc Permut (T[g], T[indpivot])

5

IV. Huit dames

1. Activité

1. Charger le fichier C:\avancé\huitdames.exe

2. Fixer le nombre de dames à 4, chercher une distribution possible des dames sur l’échiquier.

3. Charger la page web: http://jellevy.yellis.net/Classes/Activite/recree_8reines.htm

4. Charger la page web: http://www.echecsetmaths.com/echec/prob/8reines/8reines.htm

2. Principe

Le problème des huit dames (dit aussi problème des huit reines), consiste à placer huit reines

d’un jeu d’échecs sur un échiquier de 8x8 cases sans que les dames ne puissent se menacer

mutuellement.

Deux dames ne devraient jamais partager la même ligne ou la même colonne ou la même

diagonale.

3. Constatations

4. Définition

Le Backtracking, ou retour sur trace consiste à revenir en arrière sur des décisions prises à fin

de sortir d’une situation de blocage.

5. Application

Tester la solution proposée dans le livre page 239

V. Voyageur de commerce

1. Activité

Charger l’URL : http://interstices.info/jcms/c_37686/le-probleme-du-voyageur-de-commerce

2. Principe :

Étant donné n points (des « villes ») et les distances séparant chaque point, trouver un chemin de

longueur totale minimale qui passe exactement une fois par chaque point et revienne au point de

départ.

3. Application

Tester la solution proposée dans la livre page 231

Je peux tomber dans

un cas de blocage !!!

Principe du Backtracking

(Retour sur trace)