Informatique · Terminale · 1 exercice vérifié
S’entraîner : Diviser pour régner et tri fusion
Chapitre : Numérique et sciences informatiques (spécialité)
Ce que vous travaillez
Méthode « diviser pour régner » : découper le problème en sous-problèmes de même nature plus petits, les résoudre (souvent récursivement) puis combiner leurs solutions ; tri fusion : couper le tableau en deux moitiés, les trier, puis fusionner deux tableaux triés ; coût en n log₂ n dans tous les cas, contre n² pour les tris par sélection et par insertion dans le pire cas.
À maîtriser avant de commencer
Ces notions sont utilisées ici. Relisez-les si l’une d’elles vous échappe.
- Programmes récursifs — Une fonction récursive s'appelle elle-même sur une donnée plus petite ; elle comporte au moins un cas de base, traité sans appel récursif, qui garantit l'arrêt ; analyser un appel par la pile des appels ou l'arbre des appels ; compter les appels effectués ; écrire une version récursive d'un calcul (factorielle, puissance, somme des chiffres).
- Tris par sélection et par insertion — Tri par sélection : à l'étape i, on cherche le minimum de la partie non triée et on l'échange avec l'élément d'indice i ; il effectue toujours n(n − 1)/2 comparaisons. Tri par insertion : on insère chaque élément à sa place dans la partie déjà triée, en décalant les plus grands ; de n − 1 comparaisons (tableau déjà trié) à n(n − 1)/2 (tableau trié à l'envers). Invariant de boucle (« après l'étape i, les i + 1 premiers éléments sont triés »), terminaison, coût quadratique dans le pire cas.
Comment se déroule la séance
Cette séance s’appuie sur 1 exercice vérifié. Chacun produit un nouvel énoncé à chaque ouverture, avec une solution calculée.
Formats de réponse : Réponse numérique (1). Difficulté 3 sur 5. Environ 5 minutes pour un premier passage.
Dans votre compte : aide graduée (indice, rappel de cours, aide au démarrage), corrigé pas à pas après chaque tentative, suivi de vos progrès.
Essayez un exercice, sans compte
Un exercice réel de cette séance, le même pour chaque visiteur. Répondez, puis vérifiez : la correction est calculée, et le corrigé s’affiche après votre tentative.
Difficulté 3 sur 5 · ≈ 5 minutes
Énoncé
La fonction ci-dessous est l'étape de fusion du tri fusion : elle fusionne deux tableaux triés a et b, et compte dans c les comparaisons effectuées.
| n° | Instruction |
|---|---|
| 1 | def fusion(a, b): |
| 2 | ····i = 0 |
| 3 | ····j = 0 |
| 4 | ····c = 0 |
| 5 | ····r = [] |
| 6 | ····while i < len(a) and j < len(b): |
| 7 | ········c = c + 1 |
| 8 | ········if a[i] <= b[j]: |
| 9 | ············r.append(a[i]) |
| 10 | ············i = i + 1 |
| 11 | ········else: |
| 12 | ············r.append(b[j]) |
| 13 | ············j = j + 1 |
| 14 | ····return c |
| 15 | print(fusion([16, 19, 28, 47, 57], [5, 10, 13, 20, 34])) |
Chaque groupe de quatre points « ···· » marque un niveau d'indentation (quatre espaces en Python).
Quel nombre ce programme affiche-t-il ?
Votre réponse
Continuez dans votre compte
Créez votre compte gratuit pour faire toute la séance avec l’aide graduée, ou connectez-vous pour revenir directement ici.
L’accès gratuit comprend les cours et exercices de votre niveau choisi.