Utiliser la méthode « diviser pour régner »
- Fiche de cours
- Quiz et exercices
- Vidéos et podcasts
- Comprendre la méthode « diviser pour régner ».
- Écrire un programme qui utilise la méthode « diviser pour régner ».
- La méthode « diviser pour régner » consiste à découper la donnée que l’on veut traiter en plusieurs parties, puis à appliquer l’algorithme étudié sur chacune de ces parties, pour enfin combiner les résultats obtenus afin d’obtenir un résultat sur la donnée initiale.
- La récursivité est utilisée dans la méthode « diviser pour régner ».
- Le tri fusion utilise la méthode
« diviser pour régner ».
Le tri fusion consiste à diviser le tableau à trier en deux sous-tableaux, à trier récursivement chacun des deux sous-tableaux, puis à les fusionner.
- Utiliser la récursivité en Python
- Connaitre l’algorithme de recherche dichotomique dans un tableau trié
En pratique, il s’agit souvent de découper la donnée que l’on veut traiter en plusieurs parties, puis à appliquer l’algorithme étudié sur chacune de ces parties, pour enfin combiner les résultats obtenus afin d’obtenir un résultat sur la donnée initiale.
L’avantage de cette méthode est d’obtenir une résolution simple d’un problème complexe ou d’un problème dont la résolution itérative aurait été complexe.
- Diviser : on divise le problème initial en plusieurs sous-problèmes indépendants (souvent en découpant la donnée initiale).
- Régner : on résout chacun des sous-problèmes.
- Combiner : on mutualise les réponses des sous-problèmes pour résoudre le problème initial.
La recherche dichotomique d’un élément dans un tableau trié peut être programmée avec la méthode « diviser pour régner ».
Cet algorithme consiste à rechercher la position d’un élément en le comparant au milieu du tableau, il est donc en effet possible, si l’élément recherché n’est pas au milieu, d’appliquer la recherche dichotomique au sous-tableau dans lequel l’élément peut se trouver.
Par exemple, on applique la recherche dichotomique de 8 dans le tableau :-
Étape 1 : le milieu du tableau est 25,
la partie gauche est [1, 2, 3, 5, 8, 13, 21] et la partie droite
est [30, 31, 32, 35, 38, 41, 42].
Comme 8 < 25, alors on applique la recherche dichotomique à la partie gauche [1, 2, 3, 5, 8, 13, 21]. -
Étape 2 : le milieu
de [1,
2, 3, 5, 8, 13, 21] est 5, la partie gauche
est [1,
2, 3] et la partie droite
est [8, 13, 21].
Comme 8 > 5, alors on applique la recherche dichotomique à la partie droite [8, 13, 21]. -
Étape 3 : le milieu
de [8, 13, 21] est 13, la partie gauche
est [8] et la
partie droite est [21].
Comme 8 < 13, alors on applique la recherche dichotomique à la partie gauche [8]. - Étape 4 : [8] contient 8. On a trouvé l’élément.
Ainsi en divisant trois fois successivement le tableau initial et en appliquant la recherche dichotomique au sous-tableau choisi, on a trouvé 8. On a ainsi divisé le problème initial en sous-problèmes que l’on a résolu (régner) pour finalement obtenir le résultat final.
Ce tri utilise la méthode « diviser pour régner ».
En informatique, « trier » consiste à ranger dans l’ordre croissant.
Voici un algorithme de la fonction récursive de tri fusion d’un tableau tab.
| Algorithme | Explication |
| Fonction tri_fusion(tab): |
On définit la fonction tri_fusion qui prend pour
paramètre un tableau tab. Cette fonction permet de trier tab. |
| n ← taille(tab) | On affecte à n la taille de tab. |
|
Si n < 2, alors retourner tab |
Si tab contient au plus 1 élément, on retourne tab. |
|
Sinon retourner fusion (tri_fusion(tab[0 : n/2]), tri_fusion(tab[n/2 : n])) |
Sinon on retourne la fusion de la moitié gauche triée tab[0 : n/2] et de la moitié droite triée tab[n/2 : n]. |
| FinSi | Fin de l’instruction conditionnelle. |
La fonction fusion(tab1, tab2) prend en paramètres deux tableaux triés tab1 et tab2 et les fusionne pour obtenir un tableau trié.
fusion([1, 5, 8, 9], [2, 3, 6]) renvoie [1, 2, 3, 5, 6, 8, 9].
La fusion n'est pas une concaténation (mise bout à bout), mais un traitement qui renvoie un tableau trié à partir de deux tableaux triés.
En Python, la fonction tri_fusion(tab) implémente le tri fusion de tab.
| Python | Explication |
| def tri_fusion(tab): | On définit la fonction tri_fusion. |
| n = len(tab) | La longueur de la table len(tab) est affectée à la variable n. |
| if n < 2: | Si n est inférieure à 2, |
| return tab | on retourne tab. |
| else: | Sinon |
|
return fusion (tri_fusion(tab[:n//2]), tri_fusion(tab[n//2:])) |
on retourne la fusion de la partie gauche triée tri_fusion(tab[:n//2]) et de la partie droite triée tri_fusion(tab[n//2:]) |
En Python, il reste à implémenter la partie « combiner » de la méthode « diviser pour régner » : il faut définir la fonction fusion(tab1, tab2) qui est utilisée dans la fonction tri_fusion(tab).
La fonction fusion prend pour paramètres des tableaux triés dans l’ordre croissant. Ces tableaux peuvent être de taille différente.
Dans cette fonction, on compare successivement les éléments de tab1 et de tab2 pour tous les ranger dans l’ordre croissant.
| Python | Explication |
| def fusion(tab1, tab2): | On définit la fonction fusion. |
|
n1 = len(tab1) n2 = len(tab2) i1 = 0 i2 = 0 tab_sortie = [] |
La variable n1 référence
la taille de tab1. La variable n2 référence la taille de tab2. Les variables i1 et i2 sont initialisées à 0. La variable tab_sortie référence le tableau de sortie initialisé à []. |
| while i1 < n1 and i2 < n2: | Tant que i1 est inférieure à n1 et i2 est inférieure à n2 |
| if tab1[i1] < tab2[i2]: | Si l’élément d’indice i1 du tableau tab1 est inférieur à l’élément d’indice i2 du tableau tab2, |
|
tab_sortie.append(tab1[i1]) i1 = i1 + 1 |
on ajoute tab1[i1] au tableau de sortie et on incrémente i1 de 1. |
| else: | Sinon, |
|
tab_sortie.append(tab2[i2]) i2 = i2 + 1 |
on ajoute tab1[i2] au tableau de sortie et on incrémente i2 de 1. |
|
if i1 == n1: tab_sortie = tab_sortie + tab2[i2:] |
Si i1 vaut n1, alors on a parcouru tout tab1, donc on ajoute la fin de tab2 au tableau de sortie. |
|
else: tab_sortie = tab_sortie + tab1[i1:] |
Sinon, on a parcouru tout tab2, donc on ajoute la fin de tab1 au tableau de sortie. |
| return tab_sortie |
on retourne tab_sortie. |
On souhaite trier le tableau [1, 6, 5, 7, 8, 2, 4, 9, 3].
Voici l’exécution de l’algorithme tri fusion sur Pythontutor. On obtient le tableau trié [1, 2, 3, 4, 5, 6, 7, 8, 9].
Évalue ce cours !
Des quiz et exercices pour mieux assimiler sa leçon
La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.
Des exercices variés pour ne pas s’ennuyer
Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !
Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.
Des quiz pour une évaluation en direct
Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.
myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.
Des vidéos et des podcasts pour apprendre différemment
Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.
Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !
Des podcasts pour les révisions
La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.
Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.
Des vidéos de cours pour comprendre en image
Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !
Fiches de cours les plus recherchées
NSI
Programmer de manière dynamique
NSI
Étudier la complexité mémorielle
NSI
Rechercher un motif dans un texte : l'algorithme de Boyer-Moore
NSI
Comprendre les requêtes HTTP et la réponse serveur
NSI
Comprendre la notion de réseau et de protocole
NSI
Comprendre les protocoles de la couche physique
NSI
Comprendre les protocoles de la couche liaison dans un réseau local
NSI
Comprendre les protocoles de la couche réseau
NSI
Comprendre les protocoles de la couche transport
NSI
Décrire des protocoles de récupération de paquets
NSI
Affecter une valeur, utiliser une séquence d'actions
NSI
Utiliser des structures conditionnelles
NSI
Utiliser des boucles
Fermer
Accédez gratuitement à
