Español
English
Português
中文 (中国)
العربية
हिन्दी
Русский
Deutsch
Ελληνικά
Italiano
日本語
한국어
LatineRésumé
Cette leçon ouvre la sixième unité du cours, consacrée aux données composées. Elle explique à quoi sert l’unité : enseigner à représenter des collections de données (séquences de taille fixe et de taille variable, tableaux à deux dimensions et enregistrements) et à les traiter avec les algorithmes de base, écrits à la main et tirés de la bibliothèque, en estimant ce qu’ils coûtent ; elle présente ses six leçons et le fil qui les relie ; elle rappelle ce que l’unité tient pour acquis, surtout les boucles avec invariant et le passage par référence constante ; elle formule le problème que l’unité résout, celui d’un programme qui doit conserver des données dont il ne connaît pas la quantité et qui, écrit avec des variables isolées, tait en silence celles qui sont en trop ; elle anticipe le coût comme seconde mesure d’un algorithme, à côté de sa correction ; et elle montre où elle mène, dans les unités suivantes et dans le cours Programmation en C++ II.
Objectifs d’apprentissage
- Décrire la séquence des contenus de l’unité et expliquer ce que chaque leçon apporte à la suivante.
- Rappeler les boucles, leurs invariants et le passage de paramètres (par valeur, par référence et par référence constante), et les revoir si nécessaire.
- Anticiper, sur un exemple, le coût d’un algorithme comme seconde mesure de sa qualité, à côté de sa correction.
- Reconnaître ce qu’on est censé savoir faire à la fin de l’unité, et le distinguer de ce qu’on apprendra dans les unités suivantes.
Évaluation d’entrée
Avant de parcourir l’unité, il convient de mesurer le point de départ. Cette évaluation est une autoévaluation : elle n’est pas notée, et son seul but est d’orienter l’étude. Les quatre premières questions vérifient ce que l’unité tient pour acquis : l’invariant de la boucle qui cherche un maximum, le mode de passage d’un paramètre volumineux, le nombre d’itérations de deux boucles imbriquées et l’arithmétique non signée. Les six suivantes touchent, dans l’ordre des leçons, aux idées centrales de l’unité : les indices valides d’une séquence, la création d’un vecteur, le nombre de fois qu’une taille peut être divisée par deux, la recherche dans des données triées, le double indice d’un tableau à deux dimensions et le danger de ranger dans des collections séparées les données d’une même entité. Personne n’est tenu de les réussir déjà, et pour certaines d’entre elles « je ne le sais pas encore » est une réponse honnête : chaque réponse, juste ou non, explique le point et nomme la leçon qui le traite. Les mêmes compétences sont mesurées de nouveau à la fin, dans la leçon de synthèse.
Avant de commencer l’unité, mesurez votre point de départ. C’est une autoévaluation brève : elle n’est pas notée et son résultat n’est conservé que dans votre navigateur.
Question 1Des unités précédentesLe fragment
int largest{0}; int t{}; while (std::cin >> t) { if (t > largest) { largest = t; } }doit laisser danslargestla plus élevée des températures lues. Avec quelle entrée échoue-t-il ?La première itération compare la donnée à 0 et la garde si elle est strictement positive : avec une seule donnée strictement positive, le résultat est correct. Il convient de suivre la trace avant de répondre.Avec>une donnée égale au maximum ne le remplace pas, mais le maximum est le même nombre : la répétition ne change pas le résultat.Elle trahit qu’on n’a pas confronté l’initialisation à l’invariant : une boucle correcte exige que l’invariant soit vrai avant la première itération.L’invariant voulu, «largestest le maximum de ce qui a été lu jusqu’ici », n’est pas vrai au début, car avant d’avoir rien lu il n’y a pas de maximum, et le 0 initial l’emporte sur toute donnée strictement négative. On corrige en initialisant avec la première donnée, après avoir vérifié qu’elle existe. La leçon Vecteurs fait de même sur une séquence conservée, et la bibliothèque l’exprime avecstd::ranges::max, dont la précondition est que la séquence ne soit pas vide.À revoir : Concevoir des boucles correctes
Question 2Des unités précédentesUne fonction calcule combien de voyelles contient un texte d’un million de caractères, rangé dans un
std::string, et ne le modifie pas. Comment convient-il de déclarer son paramètre ?Le passage par valeur copie le million de caractères à chaque appel : c’est correct, mais on paie un coût qui n’apporte rien.Cette déclaration ne copie pas, mais elle permet de modifier le texte sans nécessité et n’accepte ni un littéral ni un temporaire : la réponse confond « ne pas copier » et « permettre de modifier ».Le mode de passage fait partie de l’interface : le passage par valeur promet à la fonction une copie à elle, et le programme doit la faire.La référence constante lit le texte sans le copier et sans permission de le modifier, et elle admet en outre un temporaire. Dans l’unité 6, ce choix devient la règle : une fonction qui lit un vecteur d’un million de données le reçoit commeconst std::vector<int>&, et la copie inutile devient l’erreur de coût la plus fréquente.À revoir : Paramètres et portée
Question 3Des unités précédentesCombien de fois
++countest-il exécuté dansfor (int i{0}; i < 6; ++i) { for (int j{0}; j < i; ++j) { ++count; } }?Bonne réponse :
La boucle intérieure fait 0 itération avec , une avec , et ainsi de suite jusqu’à 5 avec : au total , soit . La leçon Le coût d’un algorithme généralise le compte : deux boucles qui parcourent toutes les paires de données font itérations, et ce nombre décide si un algorithme convient pour un million de données.À revoir : Boucles
Question 4Des unités précédentesQu’écrit
std::println("{}", 0u - 1);sur un système oùunsigned inta 32 bits ?Elle croit qu’un type non signé admet des valeurs négatives.Elle croit que la soustraction s’arrête à la plus petite valeur du type ; l’arithmétique non signée fait le tour, elle ne sature pas.Elle confond un avertissement possible avec une erreur : l’expression est valide et sa valeur est définie.L’arithmétique non signée est modulaire : soustraire 1 de 0 fait le tour jusqu’à la plus grande valeur du type, . L’unité 6 mesure les tailles avecstd::size_t, qui est lui aussi non signé, de sorte quev.size() - 1avec un vecteur vide ne donne pas , mais un nombre énorme ; la leçon Tableaux de taille fixe met en garde contre cette soustraction, et la leçon Vecteurs montre la boucle qui, à cause d’elle, sort des limites.À revoir : Les entiers et leur représentation
Question 5Dans une séquence de éléments numérotés comme en C++, quels indices désignent un élément ?
Elle numérote à partir de un, comme dans la langue courante ; en C++,a[n]est déjà hors de la séquence.C’est l’erreur de décalage d’une unité la plus fréquente : elle compte indices pour éléments.C’est une réponse honnête : la leçon 6.1 l’explique, avec la raison pour laquelle on compte à partir de zéro.L’indice de C++ compte à partir de zéro, parce qu’il est le décalage depuis le premier élément : le premier esta[0]et le derniera[n - 1]. Accéder avec[]à un indice hors de cet intervalle est un comportement indéfini, et la leçon Tableaux de taille fixe enseigne à démontrer, par l’invariant de la boucle, que chaque accès est valide.À revoir : Tableaux de taille fixe
Question 6Que contient
vaprèsstd::vector<int> v(3, 7);?Elle lit les parenthèses comme si c’étaient des accolades.Elle inverse le rôle des deux nombres.C’est une réponse honnête : la leçon 6.2 présente le vecteur et ses façons de le créer.Avec des parenthèses, le premier nombre est la quantité et le second la valeur de chaque élément ; avec des accolades,std::vector<int> v{3, 7};est la liste des éléments, le 3 et le 7. Le vecteur est le premier type du cours où les accolades et les parenthèses disent des choses différentes, et la leçon Vecteurs le montre avec un programme.À revoir : Vecteurs
Question 7Combien d’itérations fait
for (int m{1024}; m > 1; m /= 2) { ... }?Bonne réponse :
Les valeurs demau début de chaque itération sont 1024, 512, 256, 128, 64, 32, 16, 8, 4 et 2 : dix itérations, parce que , et dix est . Un algorithme qui réduit son problème de moitié à chaque étape fait de l’ordre de étapes, et la leçon Le coût d’un algorithme le dit logarithmique : avec un milliard de données, une trentaine lui suffisent.À revoir : Le coût d’un algorithme
Question 8Un annuaire contient un million de noms dans l’ordre alphabétique. Pour en trouver un, on l’ouvre au milieu, on écarte la moitié où le nom ne peut pas être, et on recommence avec l’autre. Combien de fois, au plus, faut-il l’ouvrir ?
C’est le compte de la recherche qui examine les noms un par un : sans tirer parti de l’ordre, on parcourt en moyenne la moitié de l’annuaire.C’est la racine carrée d’un million : elle confond diviser la tranche par deux et la diviser en blocs.Elle utilise le logarithme décimal : chaque ouverture écarte la moitié, non les neuf dixièmes.Chaque ouverture réduit de moitié la tranche où le nom peut se trouver, et dépasse le million : après vingt divisions par deux, il reste un seul nom. C’est la recherche dichotomique de la leçon Rechercher et trier, qui ne fonctionne que si les données sont triées et qui se justifie par un invariant.À revoir : Rechercher et trier
Question 9Avec
std::vector<std::vector<int>> t{{1, 2, 3}, {4, 5, 6}};, que valentt[1][0]ett.size()?Elle lit le premier indice comme la colonne et compte les colonnes au lieu des lignes.Elle croit quesize()compte toutes les cases du tableau à deux dimensions.C’est une réponse honnête : la leçon 6.5 présente les tableaux à deux dimensions comme des vecteurs de vecteurs.Un tableau à deux dimensions est une séquence de lignes :t[1]est la deuxième ligne,{4, 5, 6}, ett[1][0]son premier élément.t.size()compte les lignes, non les cases. La leçon Tableaux à deux dimensions fixe la convention « d’abord la ligne, ensuite la colonne ».À revoir : Tableaux à deux dimensions
Question 10Un programme range les noms d’un groupe dans un vecteur et leurs notes dans un autre, de sorte que la note
grades[i]est celle denames[i]. S’il ne trie que le vecteur des notes, que se passe-t-il ?Pour le compilateur, les deux vecteurs sont indépendants : la relation n’existe que dans l’esprit de qui a écrit le programme.L’algorithme reçoit un seul vecteur et ignore l’existence de l’autre.Tout accès est valide et tout résultat est défini : le défaut est de logique, et c’est pourquoi aucun des deux détecteurs du cours ne le signale (celui des erreurs de mémoire, AddressSanitizer, et celui du comportement indéfini, UndefinedBehaviorSanitizer).La correspondance entre les deux vecteurs est une convention qui n’est écrite dans aucun type, et en trier un seul la rompt en silence. La leçon Enregistrements regroupe le nom et la note de chaque personne en une seule valeur, de sorte qu’en triant ils se déplacent ensemble.À revoir : Enregistrements
Chargement du contenu…