Alice se décide à ranger ses bandes dessinées par ordre alphabétique de titre.
Le travail est fastidieux car elle en possède une bonne centaine.
Elle appelle son frère Basile à la rescousse. Ils se partagent les bandes dessinées et chacun d'eux trie sa moitié, sous la forme d'une pile de bande dessinées.
Ensuite, les bandes dessinées sont rangées dans la bibliothèque en fusionnant les deux piles, c'est-à-dire en prenant à chaque fois celle des deux bandes dessinées au sommet des deux piles qui vient avant l'autre dans l'ordre alphabétique.
Si la fratrie est plus grande, on peut même imaginer décomposer le travail plus encore.
Ainsi, la pile d'Alice ou de Basile pourrait être triée en étant elle-même décomposée.
Dans un contexte informatique, cette façon de procéder suggère que plusieurs ordinateurs ou plusieurs programmes pourraient collaborer pour effectuer une tâche telle qu'un tri.
C'est effectivement le cas. Mais d'une façon très surprenante, il s'avère que même un unique programme peut tirer avantage à ainsi décomposer un problème en sous-problèmes plus petits, ou plus
simples, qu'il va lui-même résoudre successivement.
Ainsi, même si Alice est seule pour trier ses bandes dessinées, elle peut tout à fait partager les bandes dessinées en deux tas égaux, les trier puis les fusionner.
Et pour trier chacun des deux tas, elle peut recommencer ainsi avec la même idée, jusqu'à ce que chaque tas soit suffisamment petit pour pouvoir être trié sans effort.
Alice vient ainsi d'inventer le tri fusion, une méthode extrêmement efficace pour trier.
C'est là une instance du principe «diviser pour régner».
D'une manière générale, ce principe consiste à décomposer un problème à résoudre en sous-problèmes, plus petits, puis à les résoudre, éventuellement en appliquant le même principe autant de fois que nécessaire, puis enfin à combiner les résultats des sous-problèmes pour en déduire le résultat du
problème initial.
L'idée de se ramener à la résolution de sous-problèmes plus petits a déjà été explorée dans la séquence consacré à la récursivité.
En effet, quand on calcule la factorielle de n récursivement, on se ramène au calcul de la factorielle de n — 1, un problème identique mais «plus petit».
De même, le principe «diviser pour régner» invite à penser la solution
d'un problème récursivement.
Cependant, les sous-problèmes «plus petits» traités récursivement seront généralement plus nombreux ou nettement plus petits.
Dans cette séquence, nous détaillons deux exemples d'application du principe «diviser pour régner».
La première application est la recherche dichotomique dans un tableau trié, déjà étudiée en classe de première, mais reformulée ici à l'aide de récursion.
La seconde application est celle du tri fusion, suggérée ci-dessus avec l'exemple des bandes dessinées.
Les exercices proposés contiennent d'autres applications, dont un algorithme pour effectuer la rotation d'une image de 90 degrés.
On rappelle qu'il s'agit de déterminer si un entier v apparaît dans un tableau t, ce dernier étant supposé trié par ordre croissant.
Plus précisément, on cherche à écrire une fonction qui renvoie un indice où la valeur v apparaît dans t, en choisissant arbitrairement s'il y a plusieurs réponses possibles, et None si la valeur v n'apparaît pas dans t.
L'idée principale de la recherche dichotomique consiste à délimiter une portion du tableau dans laquelle la valeur v peut encore se trouver, avec deux indices g et d.
On peut illustrer ainsi la situation à chaque étape:
0 g. d
t
| éléments < v | ... | éléments > v |
On compare alors la valeur au centre de cet intervalle avec la valeur v et, selon le cas, on signale qu'on a trouvé la valeur v ou on se déplace vers la moitié gauche ou la moitié droite.
Il s'agit bien là d'une instance de l'idée «diviser pour régner», car on réduit le problème de la recherche dans
l'intervalle g ... d à celui de la recherche dans un intervalle plus petit.
Dans le programme de première, nous avions écrit la recherche dichotomique sous la forme d'une boucle while, en modifiant la valeur de g ou de d à chaque étape.
Cette fois, nous allons l'écrire sous la forme d'une fonction récursive, ce qui illustre encore mieux le principe «diviser pour régner».
En effet, l'appel récursif va directement exprimer la résolution d'un problème identique mais nlus petit.
Nous écrivons done une fonction récursive qui prend quatre arguments:
- le tableau,
- la valeur recherchée
- et les deux indices délimitant la portion dans laquelle se fait la recherche:
def recherche(t, v, g, d):
On commence par traiter le cas d'un intervalle qui ne contient aucune valeur, c'est-à-dire lorsque la borne gauche g est plus grande que la borne droite d.
Dans ce cas, on renvoie None pour signaler l'échec de la recherche.
if g > d:
return None
Si l'intervalle n'est pas vide, on calcule la position centrale de cet intervalle, en faisant la moyenne de g et d.
Ensuite, on compare la valeur v à la valeur t[m].
Si elle est plus grande, cela veut dire qu'il faut poursuivre la recherche dans la moitié droite, délimitée par les indices m+1 et d.
On rappelle donc récursivement la fonction recherche sur cet intervalle.
if tm] < v:
return recherche(t, v, m + 1, d)
Attention à ne pas oublier le return devant l'appel à recherche, car il s'agit de renvoyer le résultat de l'appel récursif.
C'est justement là qu'on exprime l'idée que la solution de notre problème est ramenée à la solution d'un problème plus petit.
D'une façon symétrique, on rappelle récursivement la fonction sur la moitié gauche de l'intervalle, délimitée par les indices g et m-1, si la valeur v est plus petite que la valeur t[m]:
elif t[ml > v:
return recherche(t, v, g, m - 1)
Enfin, il ne reste que le cas où la valeur v vient d'être trouvée à la position m que l'on renvoie alors.
else:
return m
Le programme complet de la recherche dichotomique s'en déduit en appelant la fonction recherche sur l'intégralité du tableau.
def recherche _dichotomique(t, v):
return recherche(t, v, 0, len(t) - 1)
Le code complet est le suivant:
Programme — Recherche dichotomique dans un tableau trié
def recherche(t, v, g, d):
\"\"\"renvoie une position de v dans t[g..d],
supposé trié, et None si elle ne s'y trouve pas\"\"\"
if g > d:
return None
m = (g + d) // 2
if t[m] < v:
return recherche(t, v, m + 1, d)
elif t[m] > v:
return recherche(t, v, g, m - 1)
else:
return m
def recherche_dichotomique(t, v):
\"\"\"renvoie une position de v dans le tableau t,
supposé trié, et None si elle ne s'y trouve pas\"\"\"
return recherche(t, v, 0, len(t) - 1)
Tester le cpde avec les instructions suivantes:
t1 = [randint(0,10000) for _ in range(10000)]
t1.sort()
v1 = randint(0,10000)
print(recherche_dichotomique(t1,v1))
Mettre le résultat ici (code et figure).
Correction et efficacité
Il est important de se persuader que ce programme ce termine toujours.
L'argument n'est pas différent de celui utilisé en première avec la boucle while:
la quantité d - g est un variant de notre fonction récursive. En effet, il s'agit d'une quantité entière qui décroît strictement à chaque appel récursif, tout en restant positive ou nulle.
On peut également se persuader qu'il n'y a pas de risque d'obtenir l'erreur RecursionError à cause d'un trop grand nombre d'appels récursifs. En effet, la taille de l'intervalle étant divisée par deux à chaque étape, il faudrait un tableau de plus de 21000 éléments pour que la fonction recherche soit appelée récursivement plus de 1000 fois. Or, la mémoire d'un ordinateur n'autorise aujourd'hui que des tableaux de quelques
milliards d'éléments, c'est-à-dire de l'ordre de 230. Il n'y a donc aucun risque de provoquer l'erreur RecursionError.
Mettre le résultat ici (code et figure).
Supposons que l'on veuille trier une liste chaînée contenant des entiers par ordre croissant. Plus précisément, on cherche à écrire une fonction qui reçoit en argument une liste chaînée et renvoie une nouvelle liste contenant les mêmes éléments mais triés par ordre croissant.
On pourrait tout à fait utiliser le tri par sélection ou le tri par insertion vus
au programme de première.
Cependant, le principe «diviser pour régner» peut être avantageusement utilisé pour concevoir un algorithme de tri plus efficace encore, appelé tri fusion.
L'idée a été évoquée dans l'introduction.
Elle consiste à séparer les éléments de la liste en deux listes de même taille, à un élément près.
Ensuite, on trie chacune des deux listes avec le tri fusion, récursivement.
Enfin, on fusionne les deux listes triées, ce qui est facile car il suffit d'examiner uniquement le premier élément de chaque liste.
Il s'agit bien là d'une application du principe «diviser pour régner» car on ramène le problème du tri d'une liste aux sous-problèmes du tri de deux listes plus petites, jusqu'à parvenir à des listes d'au plus un élément, pour lesquelles il n'y a rien à faire.
Le code Python qui traduit cette idée est le suivant:
def tri_fusion(lst):
if 1st is None or lst.suivante is None:
return lst
l1, l2 = coupe(lst)
return fusion(tri_fusion(l1), tri_fusion(l2))
Bien entendu, il reste à réaliser les fonctions coupe et fusion mais le principe «diviser pour régner» est capturé entièrement par la fonction tri fusion et c'est pour cela que nous la donnons tout de suite.
Écrivons maintenant la fonction coupe qui sépare les éléments d'une liste donnée dans deux listes de même taille, à un près, qui sont renvoyées sous la forme d'un couple de listes.
Il y a plusieurs façons de procéder. On pourrait par exemple commencer par calculer la longueur n de la liste, puis mettre les n/2 premiers éléments dans la première liste et le reste dans la seconde.
Üne autre solution consiste à considérer les éléments deux par deux, en en mettant un dans chaque liste.
Pour éviter de faire un cas particulier pour un éventuel dernier élément, dans le cas d'un nombre impair d'éléments, on peut adopter une troisième approche:
on considère les éléments un par un, en les mettant alternativement dans la première et dans la seconde liste,
Une façon élégante de réaliser cela consiste à échanger à chaque étape le rôle des deux listes. C'est cette dernière approche que nous adoptons.
Le code de la fonction coupe est donné dans le programme ci-dessous.
Enfin, il nous reste à écrire la fonction fusion qui reçoit deux listes triées en arguments et renvoie une liste triée contenant les éléments de ces deux listes.
Nous allons l'écrire comme une fonction récursive, car c'est là le plus simple.
La fonction fusion reçoit en argument deux listes l1 et l2, supposées triées par ordre croissant.
def fusion(l1, l2):
Elle doit renvoyer une liste contenant les mêmes éléments que l1 et l2, triée par ordre croissant.
On commence par le cas où l'une des deux listes est vide => il suffit alors de renvoyer l'autre.
if l1 is None:
return l2
if l2 is None:
return l1
Sinon, cela veut dire que les deux listes sont non vides.
On peut donc sans risque examiner maintenant le premier élément de chaque liste.
Le plus petit des deux sera le premier élément du résultat, car les deux listes sont triées.
On compare donc les deux éléments l1.valeur et l2.valeur.
Si le plus petit provient de la première liste, on le place en tête du résultat et le reste de la liste est construit en fusionnant récursivement le reste de l1 avec l2.
if l1.valeur <= l2.valeur:
return Cellule(l1.valeur, fusion(l1.suivante, l2))
Dans le cas contraire, c'est l'inverse:
le premier élément de l2 est placé en tête du résultat et le reste de la liste est construit en fusionnant l1 avec le reste de l2.
else:
return Cellule(l2.valeur, fusion(l1, l2.suivante))
Ceci achève le code de la fonction fusion.
Le code complet du tri fusion est le suivant:
Programme — Tri fusion d'une liste chaînée
def coupe(lst):
\"\"\"sépare une liste en deux listes ayant le même nombre
d'éléménts, à un près\"\"\"
l1, l2 = None, None
while lst is not None:
l1, l2 = Cellule(lst.valeur, l2), l1
lst = lst.suivante
return l1, l2
def fusion(l1, l2):
\"\"\"fusionne deux listes triées\"\"\"
if l1 is None:
return l2
if l2 is None:
return l1
if l1.valeur <= l2.valeur:
return Cellule(l1.valeur, fusion(l1.suivante, l2))
else:
return Cellule(l2.valeur, fusion(l1, l2.suivante))
def tri_fusion(lst):
\"\"\"trie une liste avec le tri fusion\"\"\"
if lst is None or lst.suivante is None:
return lst
l1, l2 = coupe(lst)
return fusion(tri_fusion(l1), tri_fusion(l2))
Tester avec:
def creer_lst_hasard(n,maxhasard):
\"\"\"Creer une liste chainée de nombres aux hasards\"\"\"
lst = None
while n>0 :
lst = Cellule(randint(0,maxhasard),lst)
n -= 1
return lst
def affiche_lst(lst):
\"\"\"affiche le contenue d'une liste chainée\"\"\"
print(lst.valeur,end=\" \")
c = lst.suivante
while c.suivante is not None:
print(c.valeur,end=\" \")
c = c.suivante
print()
#Création de la liste chainée
lst1 = creer_lst_hasard(500,5000)
affiche_lst(lst1)
#Tri de la liste
lst2 = tri_fusion(lst1)
affiche_lst(lst2)
Tester avec 1000 éléments dans la liste lst1 et conclure.
Mettre le résultat ici (code et figure).
Limites de la récursion
Si on cherche à trier une liste de plus de mille éléments avec notre fonction
tri_fusion, on obtient l'erreur RecursionError, qui signifie qu'on a fait un trop grand nombre d'appels récursifs imbriqués.
Plus précisément, c'est la fonction fusion qui est responsable de cette erreur.
Une solution consiste à augmenter le nombre maximal d'appels, avec setrecursionlimit. Une autre solution consiste À réécrire la fonc-
tion fusion avec une boucle while, ce que propose lexercice 112. C'est
cependant un peu plus délicat à écrire que la version récursive.
La fonction tri_fusion, bien que récursive, ne conduira en revanche
jamais à l'erreur RecursionError. En effet, la taille de la liste étant divisée par deux à chaque fois, il faudrait une liste de plus de 21000 éléments pour conduire à une erreur.
La mémoire de notre machine ne nous permet pas de construire une liste aussi grande.
Et quand bien même nous le pourrions, le tout premier appel à la fonction coupe ne termincrait pas avant très longtemps.
Mettre le résultat ici (code et figure).
Efficacité
Il est intéressant de se demander si le tri fusion constitue une bonne méthode de tri. En particulier, on peut chercher à le comparer aux tris par sélection et par insertion du programme de première.
Par exemple. nous avions observé que le tri par sélection nous permettait de trier 16 000 valeurs en un peu moins de 7 secondes (sur notre machine).
Avec notre tri fusion, il ne faut que 0,28 secondes pour trier autant de valeurs.
Plus généralement, voici un tableau comparatif, à gauche, et un tracé des performances du tri fusion, à droite.
| taille | sélection | fusion |
| 1000 | 0,06s | 0,01s |
| 2000 | ||
| 4000 | ||
| 8000 | ||
| 16000 | ||
| 32000 | ||
| 64000 |
Comme on le constate, la courbe n'est pas tout à fait linéaire.
Néanmoins, les performances sont bien meilleures qu'avec le tri par sélection et il en serait de même si l'on comparait avec le tri par insertion.
Pour être précis, rappelons que, dans le pire des cas, les tris par sélection
et par insertion peuvent prendre un temps quadratique, c'est-à-dire proportionnel à N2 où N désigne le nombre d'éléments à trier.
Ainsi, chaque fois que le nombre d'éléments à trier double, le temps est multiplié par quatre.
Le tri fusion, en revanche, demande un temps qui est proportionnel à N.log2N, où
log2 désigne la fonction logarithme.
Le logarithme est une fonction qui croît
relativement lentement.
Ainsi, log2(1030) < 30.
Ccla veut dire que lorsque le nombre d'éléments à trier double, le coût du tri fusion fait un peu plus que doubler, mais pas beaucoup plus.
On peut l'observer empiriquement dans le tableau ci-dessus.
Pour être complet, mentionnons qu'une telle complexité en N.log2N est optimale pour le problème du tri par comparaison.
En effet, la théorie nous dit que, dès lors qu'on ne connaît rien quant aux valeurs à trier, notamment leur distribution, et qu'on peut seulement les comparer deux à deux, alors il faut au moins N.log2N comparaisons, dans le pire des cas, pour trier N valeurs, et donc un temps au moins proportionnel à N.log2N.
Le tri fusion est donc optimal.
Mettre le résultat ici (code et figure).
Remarque : Trier un tableau
Il est possible d'utiliser le tri fusion pour trier un tableau.
Cependant, c'est assez délicat à mettre en œuvre, car réaliser la fusion en place dans le tableau est extrêmement difficile.
Du coup, on utilise un second tableau comme espace de travail temporaire pour
réaliser la fusion et le code s'en trouve tout de suite un peu compliqué.
Il existe un autre algorithme de tri mettant en œuvre le principe «diviser
pour régner» qui s'adapte mieux au cas d'un tableau.
Il s'agit du tri rapide. H consiste à choisir une valeur arbitraire apparaissant dans le tableau et s'en servir comme “pivot”, c'est-à-dire déplacer les éléments dans le tableau pour mettre à gauche les éléments plus petits que le pivot et à droite les éléments plus grands que le pivot, et enfin à trier récursivement les deux moitiés.
Il reste cependant difficile à mettre en
œuvre efficacement. Le tri rapide n'est pas au programme de terminale.
Le principe «diviser pour régner» consiste à décomposer un problème en un ou plusieurs sous-problèmes de même nature, mais plus petits:
- résoudre ces sous-problèmes, éventuellement en les décomposant à leur tour récursivement en problèmes plus petits encore;
- déduire des solutions des sous-problèmes la solution du problème initial.
Le tri fusion est un algorithme de tri efficace qui met en œuvre la technique «diviser pour régner».
Mettre le résultat ici (code et figure).
Donner la séquence des appels à la fonction recherche pendant l'évaluation des deux appels suivants :
recherche_dichotomique([0,1,1,2,3,5,8,13,21], 13)
recherche_dichotomique([0,1,1,2,8,5,8,13,21], 12)
Mettre le résultat ici (code et figure).
recherche(t, 13, O0, 8)
recherche(t, 13, 5, 8)
recherche(t, 13, 7, 8)
À ce moment-là, on obtient m = 7, position à laquelle on trouve la valeur 13.
recherche(t, 12, O0, 8)
recherche(t, 12, 5, 8)
recherche(t, 12, 7, 8)
recherche(t, 12, 7, 6)
À ce moment-là, on a g > d et la recherche termine avec le résultat None.
Quelles sont les deux listes renvoyées par la fonction coupe() lorsqu'on lui passe la liste 8 1 3 0 1 2 5?
L'ordre relatif des éléments est-il préservé?
Est-ce important?
","title":"Exercice","tagtitle":"h1"},{"edit":"Mettre le résultat ici (code et figure).
La première liste est 5 1 3 8
et la seconde 2 0 1.
On constate que l’ordre relatif est inversé, car les premiers éléments de la
liste l sont ajoutés en premier dans les deux listes l1 et l2.
Ce n’est pas important, car les deux listes vont être triées avant d’être fusionnées.
Réécrire La fonction fusion à l'aide d'une boucle while plutôt que comme une fonction récursive.
Indication : Construire le résultat en
ordre décroissant, puis le renverser avec une seconde boucle while.
Tester avec:
def creer_lst_hasard(n,maxhasard):
\"\"\"Creer une liste chainée de nombres aux hasards\"\"\"
lst = None
while n>0 :
lst = Cellule(randint(0,maxhasard),lst)
n -= 1
return lst
def affiche_lst(lst):
\"\"\"affiche le contenue d'une liste chainée\"\"\"
print(lst.valeur,end=\" \")
c = lst.suivante
while c.suivante is not None:
print(c.valeur,end=\" \")
c = c.suivante
print()
#Création de la liste chainée
lst1 = lsthasard(1000,5000)
affiche_lst(lst1)
#Tri de la liste
lst2 = tri_fusion(lst1)
affiche_lst(lst2)
Mettre le résultat ici (code et figure).
def coupe(lst):
\"\"\"sépare une liste en deux listes ayant le même nombre
d'éléménts, à un près\"\"\"
l1, l2 = None, None
while lst is not None:
l1, l2 = Cellule(lst.valeur, l2), l1
lst = lst.suivante
return l1, l2
def fusion(l1, l2):
lst = None
while l1 is not None or l2 is not None:
if l1 is not None and \\
(l2 is None or l1.valeur <= l2.valeur):
lst, l1 = Cellule(l1.valeur, lst), l1.suivante
else:
lst, l2 = Cellule(l2.valeur, lst), l2.suivante
# puis on renverse lst
r = None
while lst is not None:
r, lst = Cellule(lst.valeur, r), lst.suivante
return r
def tri_fusion(lst):
\"\"\"trie une liste avec le tri fusion\"\"\"
if lst is None or lst.suivante is None:
return lst
l1, l2 = coupe(lst)
return fusion(tri_fusion(l1), tri_fusion(l2))
Le problème des tours de Hanoï est un jeu célèbre constitué de trois tiges verticales sur lesquelles sont empilés des disques de diamètres différents.
![](\"https://sciencesappliquees.com/images/nsi/diviser1.png\")
Il s'agit de déplacer tous les disques de la première tige (dessin de gauche) vers la dernière tige (dessin de droite) en respectant deux contraintes:
- d'une part, on ne peut déplacer qu'un seul disque à la fois;
- d'autre part, on ne peut pas poser un disque sur un disque de diamètre plus petit.
Sur l'exemple ci-dessus, avec quatre disques, il ne faut pas moins de 15 déplacements pour y parvenir.
Écrire une fonction hanoiï(n) qui affiche la solution du problème des tours de Hanoï pour n disques, sous la forme de déplacements élémentaires désignant les trois tiges par les entiers 1, 2 et 3, de la manière suivante:
déplace de 1 vers 3
déplace de 1 vers 2
Indication: Commencer par une fonction récursive deplace(a, b, c, k) qui résout le problème plus général du déplacement de k disques de la tige a vers la tige b en se servant de la tige c comme stockage intermédiaire.
Tester avec:
hanoi(4)
Résultat:
déplace de 1 vers 2
déplace de 1 vers 3
déplace de 2 vers 3
déplace de 1 vers 2
déplace de 3 vers 1
déplace de 3 vers 2
déplace de 1 vers 2
déplace de 1 vers 3
déplace de 2 vers 3
déplace de 2 vers 1
déplace de 3 vers 1
déplace de 2 vers 3
déplace de 1 vers 2
déplace de 1 vers 3
déplace de 2 vers 3
Mettre le résultat ici (code et figure).
On suit l'indication. Il n’est pas nécessaire de faire un cas particulier pour k = 1, c’est-à-dire un seul disque.
Il suffit de ne rien faire lorsque k = 0.
def deplace(a, b, c, k):
\"\"\"déplace k disques de La tour a vers la tour b,
en se servant de la tour c comme intermédiaire\"\"\"
if k > 0:
deplace(a, c, b, k - 1)
print(\"déplace de\", a, \"vers\", b)
deplace(c, b, a, k - 1)
#La solution s’en déduit facilement :
def hanoi(n):
deplace(1, 3, 2, n)
Dans le problème des tours de Hanoï (exercice précédent), combien faut-il de déplacements élémentaires au total pour déplacer les N disques de la tour de départ à la tour d'arrivée?
Indication : Regarder les 3 vidéos pour vous aider.
Mettre le résultat ici (code et figure).
Pour déplacer 1 disque, il suffit d’un seul mouvement.
Pour déplacer 2 disques, il faut 1 + 1 + 1 = 3 déplacements.
Pour déplacer 3 disques, il faut 3 + 1 + 3 = 7 déplacements (on en déplace deux,
puis le grand, puis on en déplace deux de nouveau).
En continuant ainsi, on trouve ensuite les valeurs 15, 31, 63, ...,
c’est-à-dire les nombres de la forme :
2N - 1.
On peut le prouver à l’aide d’une récurrence.
En effet, c’est bien le cas pour N = 1, car 21 - 1 = 1 et s’il faut 2N-1 - 1 déplacements pour N — 1 tours, alors on aura au total (2N-1 -1)+ 1 +(2N-1 -1) = 2N - 1 déplacements pour N tours.
Reprendre l'exercice sur les tours de Hanoï en utilisant trois piles, chacune contenant des entiers qui représentent les tailles des disques que cette pile contient.
Mettre le résultat ici (code et figure).
Les trois arguments a, b, c ne sont plus des entiers mais des piles. Dans le code de la fonction deplace, il suffit de remplacer la ligne
print (\"déplace de\", a, \"vers\", b)
par la ligne
b.empiler(a.depiler())
Dans le code de la fonction hanoi, il faut construire les trois piles, la première contenant les n disques.
def deplace2(a, b, c, k, posi):
\"\"\"déplace k disques de La tour a vers la tour b,
en se servant de la tour c comme intermédiaire\"\"\"
if k > 0:
deplace2(a, c, b, k - 1,[posi[0],posi[2],posi[1]])
b.empiler(a.depiler())
#affichage contenu pile
for i in range(3):
if posi[i] == 0 :
tab = afficher_pile(a)
print(tab)
elif posi[i] == 1 :
tab = afficher_pile(b)
print(tab)
else :
tab = afficher_pile(c)
print(tab)
print()
deplace2(c, b, a, k - 1,[posi[2],posi[1],posi[0]])
def hanoi2(n):
a = Pile()
for i in range(1,n+1):
a.empiler(i)
print(afficher_pile(a))
deplace2(a, Pile(), Pile(), n,[0,1,2])
def afficher_pile(pile:Pile):
if pile.contenu is None:
return []
tab = [pile.contenu.valeur]
c = pile.contenu.suivante
while c is not None:
tab.append(c.valeur)
c = c.suivante
return tab
On a pris soin d’empiler les diamètres en partant du plus grand. Suggestion :
ajouter un affichage du contenu des trois piles après chaque déplacement.
Dans cet exercice, on cherche à écrire une fonction qui effectue la rotation d'une image de 90 degrés en utilisant le principe «diviser pour régner».
Pour manipuler une image en Python, on peut utiliser par exemple la bibliothèque PIL (Python Image Library) et plus précisément son module Image.
Avec les quatre lignes suivantes:
from PIL import Image
im = Jmage.open(\"image.png\")
largeur, hauteur = im.size
px = im.load()
on charge l'image contenue dans le fichier image.png, on obtient ses dimensions dans les variables largeur et hauteur, et la variable px est la matrice
des pixels constituant l'image.
Pour 0 < x < largeur et 0 < y < hauteur, la couleur du pixel (x, y) est donnée par px[x, y].
Une couleur est un triplet donnant les composantes rouge, vert et bleu, sous la forme d'entiers entre 0 et 255.
On peut modifier la couleur d'un pixel avec une affectation de la forme px[x,y]=c où c est une couleur.
Dans cet exercice, on suppose que l'image est carrée et que sa dimension est une puissance de deux, par exemple 256 x 256.
Notre idée consiste à découper l'image en quatre, à effectuer la rotation de 90 degrés de chacun des quatre morceaux, puis à les déplacer vers leur position finale.
On peut illustrer les deux étapes ainsi:
![](\"https://sciencesappliquees.com/images/nsi/diviser2.png\")
![](\"https://sciencesappliquees.com/images/nsi/diviser3.png\")
Afin de pouvoir procéder récursivement, on va définir une fonction rotation_aux(px, x, y, t) qui effectue la rotation de la portion carrée
de l'image comprise entre les pixels (x,y) et (x+t,y+t).
Cette fonction ne renvoie rien. Elle modifie le tableau px pour effectuer la rotation de cette portion de l'image, au même endroit.
On suppose que t est une puissance de 2.
Écrire le code de la fonction rotation_aux.
En déduire une fonction rotation(px, taille) qui effectue une rotation de l'image toute entière, sa dimension étant donnée par le paramètre taille.
Une fois la rotation effectuée, on pourra sauvegarder le résultat dans un autre fichier avec la commande im.save(\"rotation.png\").
Tester avec:
from PIL import Image
im = Image.open(\"image1.png\")
largeur, hauteur = im.size
px = im.load()
rotation(px, largeur)
im.save(\"rotation.png\")
et l'image suivante (Clique droit enregistrer sous):
![](\"https://sciencesappliquees.com/images/nsi/image1.png\")
Résultat en ouvrant rotation.png:
![](\"https://sciencesappliquees.com/images/nsi/rotation.png\")
Mettre le résultat ici (code et figure).
On commence par traiter le cas d’une région réduite
à un unique pixel. Dans ce cas, il n’y a strictement rien à faire :
def rotation_aux(px, x0, y0, t):
if t == 1:
return
#Sinon, on peut découper la région en quatre sous-régions, de dimension deux
#fois plus petite, dont on effectue la rotation récursivement :
t //=2
rotation_aux(px, x0 , y0 , t)
rotation_aux(px, x0+t , y0 , t)
rotation_aux(px, x0 , y0+t , t)
rotation_aux(px, x0+t , y0+t , t)
#Il faut ensuite déplacer chacune des quatre régions, ce que l’on peut faire
#élégamment avec une double boucle et une affectation simultanée des quatre
#pixels qui échangent leur position :
for x in range(x0, x0+t):
for y in range(y0, y0+t):
px[x,y+t],px[x+t,y+t],px[x+t,y],px[x,y] \\
= px[x,y], px[x,y+t], px[x+t,y+t], px[x+t,y]
La rotation de l’image toute entière est obtenue avec une région qui couvre
toute l’image:
def rotation(px, taille):
rotation_aux(px, 0, 0, taille)
Dans cet exercice, on se propose d'appliquer le principe «diviser pour régner» pour multiplier deux entiers, avec la méthode de Karatsuba.
Le principe est le suivant. Supposons deux entiers x et y ayant chacun 2n chiffres en base 2.
On peut les écrire sous la forme
x = a2n+b
y = c2n+d
avec 0 < a,b,c,d < 2n, c'est-à-dire avec quatre entiers a, b, c, d qui s'écrivent
chacun sur n chiffres en base 2.
Dès lors, on peut calculer le produit de x et y de la façon suivante:
xy = (a2n + b)(c2n + d)
= ac22n + (ad + bc)2n + bd
= ac2n + (ac + bd — (a — b)(c — d))2n + bd
Cette dernière forme, d'apparence inutilement compliquée, fait apparaître
seulement trois produits, à savoir ac, bd et (a — b}(c — d).
Ainsi, on a ramené la multiplication de deux entiers de 2n chiffres à trois multiplications d'entiers de n chiffres.
Pour faire chacune de ces trois multiplications, on peut appliquer le même principe, et ainsi de suite jusqu'à obtenir de petits entiers dont la multiplication est immédiate.
Au final, cela permet d'effectuer la multiplication en un temps proportionnel à n1,58 (environ) au lieu de n2, ce qui est un gain significatif lorsque le nombre de chiffres n est grand.
1. Écrire une fonction taille(x) qui renvoie le nombre de chiffres de l'entier x lorsqu'il est écrit en base 2.
2. Écrire une fonction karatsuba(x, y, n) qui calcule le produit de x et y par la méthode de Karatsuba, en supposant que x et y s'écrivent sur n chiffres en base 2.
Indication : On peut calculer 2n en Python avec l'expression 1 << n.
On peut décomposer x sous la forme a2n+b
avec a, b = x>>n, x % (1 << n).
3. En déduire une fonction mult(x, y) qui calcule le produit de x et y.
Remarque : Il n'est pas nécessaire d'utiliser la base 2. On pourrait tout aussi bien utiliser la base 10 par exemple. Mais les opérations liées à la base deux (multiplication, division ou reste par une puissance de deux sont faciles à réaliser pour la machine).
Tester avec:
print(mult(31478987896658567686786785446,2311675667575656756575765757554))
Mettre le résultat ici (code et figure).
Pour la fonction taille, il suffit de diviser x par deux jusqu’à obtenir zéro.
def taille(x):
n=1
while x > 0:
x //= 2
n += 1
return n
Pour la fonction karatsuba, on suit l’algorithme proposé, en s’arrêtant lorsqu'il ne reste qu’un seul chiffre.
def karatsuba(x, y, n):
\"\"\"multiplie x et y par La méthode de Karatsuba\"\"\"
if n <= 1:
return x * y
n //=2
m = 1<<n
a , b = x >> n , x % m
c , d = y >> n , y % m
ac = karatsuba(a, c, n)
bd = karatsuba(b, d, n)
abcd = karatsuba(a - b, c - d, n)
return (ac << ( 2 * n ) ) + ((ac + bd - abcd) << n ) + bd
Enfin, la fonction mult calcule la valeur de n comme le maximum des deux tailles (l'algorithme reste correct si l’un des deux entiers a moins que n chiffres).
def mult(x, y):
n = max(taille(abs(x)), taille(abs(y)))
return karatsuba(x, y, n)