Quelles sont les trois étapes de la méthode diviser pour régner ?
Réponse courte
Diviser pour régner consiste à découper le problème en sous-problèmes plus petits, résoudre ceux-ci de même nature, puis combiner leurs solutions. Il faut aussi un cas de base et une réduction qui mène à l’arrêt.
Comprendre
Diviser le problème
Commence par décomposer l’instance en sous-problèmes plus petits, généralement de même nature. Pour trier une liste, par exemple, coupe-la en deux parties de tailles proches. Si la liste contient 5 valeurs, une coupure au milieu produit des listes de 2 et 3 valeurs.
Résoudre les sous-problèmes
Applique la même méthode à chaque partie. Les appels récursifs continuent jusqu’à un cas assez simple pour être traité directement. Pour le tri, une liste vide ou à un seul élément est déjà triée : c’est un cas de base qui ne demande pas de nouvel appel.
Combiner les résultats
Une fois les sous-problèmes résolus, assemble leurs solutions pour obtenir celle de l’instance initiale. Dans le tri fusion, on fusionne les sous-listes triées afin de produire une liste triée complète. Concaténer les listes ne suffit pas toujours, car leurs valeurs peuvent être entrelacées.
Vérifier la terminaison
La taille de chaque sous-problème doit diminuer, sinon la récursion peut ne jamais atteindre le cas de base. Une méthode qui coupe la liste mais conserve la liste entière dans un appel ne progresse pas vers l’arrêt.
Étapes
- Divise l’instance en sous-problèmes plus petits de même nature.
- Résous chaque partie, en utilisant un cas de base pour les petites instances.
- Combine les solutions partielles pour répondre au problème initial.
- Vérifie que chaque appel récursif se rapproche effectivement du cas de base.
Exemples
- Pour trier [7, 2, 5, 1], divise en [7, 2] et [5, 1], trie les parties en [2, 7] et [1, 5], puis fusionne pour obtenir [1, 2, 5, 7].
- Pour n = 5, une coupure au milieu crée des sous-problèmes de tailles 2 et 3, toutes deux inférieures à 5.
Pièges fréquents
- Oublier de combiner les résultats : résoudre séparément les deux moitiés ne donne pas encore la solution du problème entier.
- Écrire un cas de base sans réduire la taille des appels : le programme peut continuer à appeler la même instance et ne jamais s’arrêter.
