Exercices corrigés — Parcourir, trier, prouver (NSI (première))
37 exercices avec corrigé rédigé, du plus simple au plus exigeant.
Parcourir et prouver
- Donner l'invariant de la boucle de recherche , et mener les trois… Exercice de TD
- Écrire minimum et maximum(t) en un seul parcours, renvoyant un couple Exercice de TD
- Écrire sommes prefixes(t) , qui rend le tableau des sommes des i… Exercice de TD
Les deux tris, leurs invariants, leur coût
- Même travail avec tri insertion sur le même tableau Exercice de TD
- Modifier tri insertion pour trier par ordre décroissant Exercice de TD
- Que se passe-t-il si l'on remplace t j - 1 x par t j - 1 = x Exercice de TD
- Le tri par sélection est-il stable Exercice de TD
- On appelle inversion d'un tableau un couple d'indices avec et Exercice de TD
Variants, terminaison, mesure
- Écrire un variant pour la boucle while n!= 1 Exercice de TD
- Instrumenter le tri par insertion pour compter ses comparaisons, et… Exercice de TD
Parcours élémentaires
- Écrire derniere occurrence(t, v) Application directe du cours
- Écrire somme(t) et produit(t) par accumulateur Application directe du cours
- Écrire indice minimum(t), symétrique de indice maximum Application directe du cours
Dérouler, compter, vérifier
- Dérouler à la main tri selection sur [5, 2, 8, 1] , en écrivant l'état… Application directe du cours
- Pourquoi la boucle externe de tri selection s'arrête-t-elle à n - 1 et… Application directe du cours
- Vérifier expérimentalement que tri selection compte renvoie exactement… Application directe du cours
- Écrire contient(t, v), qui rend un booléen, à partir de recherche Application directe du cours
Parcours, occurrences, cas limites
- Écrire compte occurrences(t, v) par parcours séquentiel, puis comparer… Exercice d'entraînement
- Écrire toutes occurrences(t, v), qui rend le tableau des indices Exercice d'entraînement
- Que fait moyenne([]) avec l'assertion du cours ? Et sans elle ? Exercice d'entraînement
- Dans indice maximum, remplacer par = Exercice d'entraînement
Variantes des deux tris
- Écrire la variante du tri par sélection qui cherche le maximum et le… Exercice d'entraînement
- Le tri par insertion cherche la place de la carte séquentiellement Exercice d'entraînement
- Démontrer, par l'invariant, que le tri par insertion est stable, puis… Exercice d'entraînement
- Adapter tri insertion pour trier une table (chapitre 6) suivant une… Exercice d'entraînement
Ce qu'un invariant fait voir
- Voici une version fautive du tri par sélection Exercice d'entraînement
- La postcondition d'un tri a deux moitiés Exercice d'entraînement
D'autres tris que les deux du programme
- Écrire le tri à bulles Exercice supplémentaire
- Écrire le tri par comptage, qui trie des entiers bornés sans jamais… Exercice supplémentaire
- Écrire le tri fusion : couper en deux, trier chaque moitié, fusionner. Exercice supplémentaire
- Le tri de Shell applique le tri par insertion à des éléments distants… Exercice supplémentaire
Ce que coûte un tri : bornes et mesures
- Compter les comparaisons que fait réellement le sorted de Python, sur… Exercice supplémentaire
- On démontre qu'aucun tri fondé sur des comparaisons ne peut faire… Exercice supplémentaire
- Chronométrer les deux tris du cours plutôt que compter leurs… Exercice supplémentaire
Terminaison, échanges, partitions
- Voici une boucle : while n != 1: n = n // 2 if n % 2 == 0 else 3 n + 1… Exercice supplémentaire
- L'échange t i, t m = t m, t i se passe de variable temporaire Exercice supplémentaire
- Écrire la partition : ranger un tableau autour d'un pivot, les plus… Exercice supplémentaire