Diviser pour régner

Le cours et les exercices seront faits sur papier.

Quelques activités interactives pour comprendre le principe :

1. le jeu du "plus ou moins"
2. trier une liste de nombres

Exercices sur Codex :

1. Fusion de deux listes triées
2. Tri par insertion
3. Tri par sélection
4. Recherche dichotomique (booléen)
5. Recherche dichotomique (indice)
6. Sommet d'un tableau unimodal

Indication pour les tris : il peut être avantageux de les découper en deux fonctions.

Bonus : insérez dans les fonctions un compte des comparaisons pour estimer leurs coûts. Programmez les fonctions qui s'y prêtent de deux manières : de façon itérative (avec des boucles) et récursive.

L'exercice 1 du sujet de bac écrit 24-NSIJ2JA1 propose un problème intéressant à résoudre par la méthode diviser pour régner.