Exercices corrigés — Dichotomie, voisins et gloutons (NSI (première))
37 exercices avec corrigé rédigé, du plus simple au plus exigeant.
La recherche dichotomique
- Dérouler dichotomie sur 1, 3, 5, 7, 9, 11 en cherchant, puis Exercice de TD
- Combien de tours au maximum pour un tableau de éléments Exercice de TD
- Que renvoie dichotomie sur un tableau vide Exercice de TD
- Écrire une variante qui, lorsque v est absente, renvoie l'indice où il… Exercice de TD
- Sur un tableau contenant plusieurs fois la même valeur, quelle… Exercice de TD
- Écrire est trie(t) et l'utiliser comme précondition explicite Exercice de TD
Les plus proches voisins
- Sur un jeu d'exemples à deux classes que vous construirez, appliquer k… Exercice de TD
- Pourquoi choisir impair avec deux classes Exercice de TD
Les algorithmes gloutons
- Modifier rendu monnaie pour qu'il renvoie un dictionnaire \{valeur Exercice de TD
- Trouver, pour le système [6, 4, 1] , toutes les sommes de 1 à 50 pour… Exercice de TD
Dichotomie
- n° 50 Application directe du cours
- Combien de tours au maximum pour éléments Application directe du cours
- Que renvoie dichotomie([], 7) ? Sans exécuter, dire pourquoi la… Application directe du cours
Voisins et gloutons
- Vérifier que distance((0, 0), (3, 4)) vaut Application directe du cours
- Avec le jeu [((0,0),"A"), ((1,0),"A"), ((5,5),"B"), ((6,5),"B")]… Application directe du cours
- Vérifier à la main que le rendu glouton de 67 centimes donne quatre… Application directe du cours
- Vérifier sur le système [6, 4, 1] et la somme 8 que le glouton rend… Application directe du cours
Variantes de la dichotomie
- Écrire dichotomie sous forme récursive Exercice d'entraînement
- Écrire une fonction qui compte les tours de la dichotomie dans le pire… Exercice d'entraînement
- Un tableau trié a été décalé circulairement Exercice d'entraînement
- Écrire fusion triee(a, b) qui fusionne deux tableaux triés en un seul… Exercice d'entraînement
Les voisins, pour de vrai
- Reprendre l'avertissement du cours sur les grandeurs non comparables Exercice d'entraînement
- Comment savoir si un choix de est bon Exercice d'entraînement
Gloutons : jusqu'où ?
- Écrire une résolution exhaustive du rendu de monnaie par programmation… Exercice d'entraînement
- Trouver d'autres systèmes de pièces où le glouton échoue Exercice d'entraînement
- Dans le sac à dos, comparer trois stratégies gloutonnes Exercice d'entraînement
- Réécrire le rendu glouton sans supposer les pièces triées Exercice d'entraînement
Le défaut de 2006, et la dichotomie ailleurs
- Le cours raconte qu'en 2006, un débordement d'entier a été découvert… Exercice supplémentaire
- La dichotomie ne sert pas qu'aux tableaux Exercice supplémentaire
Les outils, et ce qu'ils coûtent
- Le module bisect fournit la dichotomie de la bibliothèque standard Exercice supplémentaire
- Mesurer le coût de maintenir une liste triée Exercice supplémentaire
- Améliorer les k plus proches voisins en pondérant chaque vote par… Exercice supplémentaire
Aux frontières
- La «malédiction de la dimension» Exercice supplémentaire
- Un glouton prouvé optimal existe Exercice supplémentaire
- Quelle proportion des systèmes de pièces à trois valeurs [a, b, 1]… Exercice supplémentaire
- Écrire premier vrai(predicat, n) Exercice supplémentaire
- La dichotomie est logarithmique Exercice supplémentaire