Résumé
Cette leçon ouvre la quatrième unité du cours, consacrée aux structures de contrôle. Elle explique à quoi sert l’unité : enseigner à gouverner l’ordre dans lequel s’exécutent les instructions d’un programme, avec des décisions et avec des boucles, et à raisonner sur leur correction, c’est-à-dire à s’assurer que chaque cas est traité, que chaque boucle fait ce qu’elle doit et qu’elle se termine ; elle présente ses quatre leçons et le fil qui les relie ; elle rappelle ce que l’unité tient pour acquis, surtout les conditions composées de l’unité 3 ; elle formule le problème que l’unité résout, celui d’un programme qui calcule le plus grand commun diviseur avec un nombre fixe d’étapes et qui, selon les données, répond faux ou s’arrête sur une division par zéro ; elle anticipe l’invariant comme l’outil avec lequel l’unité justifiera ses boucles ; 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 suite des contenus de l’unité et expliquer ce que chaque leçon apporte à la suivante.
- Rappeler les conditions composées de l’unité 3 (les connecteurs, l’évaluation en court-circuit et la négation par les lois de De Morgan) et les revoir si nécessaire.
- Anticiper, sur un exemple, l’invariant comme outil de raisonnement : une relation entre les variables qu’une répétition conserve et qui, à la fin, donne le résultat.
- Reconnaître ce que l’on attend de savoir faire à la fin de l’unité, et le distinguer de ce qui s’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 : la négation d’une condition composée, l’évaluation en court-circuit, la trace d’une répétition de la leçon 1.1 et la limite d’un int. Les sept suivantes touchent, dans l’ordre des leçons, aux idées centrales de l’unité, et plusieurs d’entre elles partent des mathématiques scolaires : le plus grand commun diviseur, la notation de sommation, la terminaison d’un procédé. 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édentesQuelle est la négation de la condition
1 <= n && n <= 10?Elle nie chaque partie, mais conserve la conjonction : elle oublie De Morgan. De plus, aucun nombre n’est à la fois inférieur à 1 et supérieur à 10, de sorte que cette condition est toujours fausse.Elle change bien le connecteur, mais nie mal les relations : elle exclut en trop les frontières 1 et 10, qui satisfont la condition d’origine.Elle ne nie que la première partie.Par De Morgan, la négation d’une conjonction est la disjonction des négations, et la négation de1 <= nestn < 1, nonn <= 1. L’unité en a besoin dans chaque décision enchaînée, parce que la brancheelsetraite exactement la négation des conditions précédentes, et dans chaque boucle, parce qu’à la sortie la négation de sa condition est vraie.À revoir : Relations et logique
Question 2Des unités précédentesAvec
int d{0};etint n{5};, que se passe-t-il quand on évalued != 0 && n / d > 2?Elle ignore le court-circuit : la division n’est jamais calculée.Une conjonction dont un opérande est faux ne peut en aucun cas être vraie.L’expression est correcte ; le compilateur ne connaît pas la valeur dedà l’exécution.Le premier opérande est faux, et l’évaluation en court-circuit n’évalue pas le second : la garde à gauche protège la division. L’unité transforme cette garde en décisions explicites et en conditions de boucle qui protègent leur corps.À revoir : Relations et logique
Question 3Des unités précédentesLa division par soustractions successives de la leçon 1.1 commence avec et , et répète « tant que , soustraire de et ajouter 1 à ». Avec et , combien de fois le corps de la répétition s’exécute-t-il ?
Elle compte les évaluations de la condition, qui sont une de plus que les itérations.Elle arrête la répétition avec : elle lit comme .Elle confond le nombre d’itérations avec la valeur initiale de .La trace donne : le corps s’exécute quatre fois, et la condition est évaluée cinq fois, parce que la dernière évaluation est celle qui échoue. La leçon 4.2 écrit cette répétition en C++ et transforme la trace en tableau de suivi.À revoir : Du problème à l’algorithme
Question 4Des unités précédentesAvec un
intde 32 bits, que garantit la norme sur la valeur de46341 * 46341?Elle ignore la plage du type : ce nombre ne tient pas dans unint.Elle croit que le dépassement s’arrête au bord ; la norme ne promet rien.Le type du résultat est fixé par les opérandes, qui sont desint, et non par la valeur du résultat.Le maximum est . L’unité rencontre ce produit là où on ne le cherche pas : la conditiond * d <= nd’une boucle qui essaie des diviseurs, qui déborde justement quand est proche du maximum.À revoir : Les entiers et leur représentation
Question 5Un programme contient la chaîne de décisions
if (score >= 50), qui écrit « Réussi » ;else if (score >= 90), qui écrit « Excellent » ; etelse, qui écrit « Échoué ». Qu’écrit-il avecscoreégal à 95 ?Elle croit que la condition la plus exigeante l’emporte ; c’est la première qui est satisfaite qui l’emporte.Elle croit que toutes les branches vraies s’exécutent ; dans une chaîne, une seule s’exécute.C’est une réponse honnête : la leçon 4.1 l’explique, et l’évaluation de sortie reviendra sur les frontières d’une chaîne.Dans une chaîne, on exécute la première branche dont la condition est vraie, et . La branche « Excellent » ne s’exécute jamais : son cas réel est et , qui est vide. La leçon 4.1 apprend à lire le cas réel de chaque branche et à ordonner les conditions.À revoir : Décisions
Question 6Laquelle des expressions suivantes désigne la somme ?
Elle ajoute fois le nombre , c’est-à-dire : elle confond le terme avec la borne supérieure.Elle calcule : elle décale les bornes et perd le dernier terme, l’erreur de décalage d’une unité des boucles.La borne supérieure ne peut pas être l’indice lui-même : l’expression n’a pas de sens.L’indice parcourt les entiers de 1 à , et chaque terme est lui-même. Une boucleforqui accumule est la traduction directe de cette notation : la variable de contrôle est l’indice, ses bornes sont celles de la somme, et le corps ajoute le terme.À revoir : Boucles
Question 7Avec
int total{0};, qu’écritstd::println("{}", total);aprèsfor (int i{0}; i < 5; ++i) { total += i; }?Elle croit queiarrive à 5 : elle lit<comme<=.Elle confond l’accumulateur avec le compteur : cinq est le nombre d’itérations, non la somme.C’est une réponse honnête : la leçon 4.2 enseigne la forme duforet la manière de compter ses itérations.La variableiprend les valeurs 0, 1, 2, 3 et 4, et ; aveciégal à 5, la condition échoue et le corps ne s’exécute pas. C’est la somme de la question précédente avec les bornes 0 et 4.À revoir : Boucles
Question 8Dans la division par soustractions successives (, ; tant que , devient et devient ), quelle relation entre les variables est vraie chaque fois qu’on évalue la condition ?
Elle n’est vraie qu’à la sortie : tant qu’on répète, la condition assure le contraire.Elle n’est vraie qu’à la fin ; avant, est strictement inférieur au quotient.C’est une réponse honnête : la leçon 4.3 apprend à trouver et à vérifier cette relation, et l’évaluation de sortie reposera la question.Elle est vraie au début, parce que ; et si elle est vraie avant une itération, elle l’est après, parce que . À la sortie s’ajoute la négation de la condition, , et les deux ensemble donnent le résultat. Une telle relation s’appelle un invariant, et la leçon 4.3 en fait la méthode pour concevoir des boucles et les justifier.À revoir : Concevoir des boucles correctes
Question 9Un procédé part d’un entier quelconque (strictement positif, nul ou strictement négatif) et répète « tant que , soustraire 2 de ». Se termine-t-il pour tout ?
Cela arrive avec la condition ; avec , la répétition s’arrête dès que vaut 0 ou .Avec strictement négatif, la condition est fausse dès le début, et le corps ne s’exécute pas.La conclusion est correcte, mais la raison ne l’est pas : être entier ne suffit pas ; il faut que la quantité soit un entier naturel tant qu’on répète et qu’elle décroisse.La quantité est un entier naturel tant qu’on répète (la condition l’assure) et décroît strictement : c’est un variant, l’outil de la leçon 1.1 que la leçon 4.3 utilise dans chaque boucle. Avec « tant que », la réponse changerait : un impair saute le zéro.À revoir : Concevoir des boucles correctes
Question 10Quel est le plus grand commun diviseur de 84 et 36 ?
C’est un diviseur commun, mais pas le plus grand.C’est un diviseur commun, mais pas le plus grand : il manque le facteur 3, qu’ils partagent aussi.C’est le plus petit commun multiple, non le plus grand commun diviseur.Les diviseurs communs sont 1, 2, 3, 4, 6 et 12. L’algorithme d’Euclide l’obtient sans chercher de diviseurs : et , de sorte que . La leçon 4.4 l’écrit sous forme de boucle et démontre pourquoi il fonctionne.À revoir : Algorithmes numériques
Question 11Pour décider si 101 est premier en essayant des diviseurs, jusqu’à quel diviseur suffit-il d’aller ?
Elle utilise la moitié : c’est correct, mais cinq fois plus long que nécessaire.Elle essaie tous les candidats : c’est correct, mais cela ne tire pas parti de ce que les diviseurs vont par paires.C’est une réponse honnête : la leçon 4.4 le démontre.Si 101 avait un diviseur avec , en serait aussi un, et l’un des deux serait au plus . Il suffit d’essayer de 2 à 10 : aucun ne divise 101, qui est premier. La leçon 4.4 démontre la règle et l’écrit sans racines ni produits qui débordent.À revoir : Algorithmes numériques
Chargement du contenu…