Sélection et itération

AP Informatique A · Sujet 2

Leçon vidéo pour ce sujet Ouvrir la page vidéo

2.1

Sélection et répétition dans les algorithmes

Programme

Objectif d'apprentissage 2.1.A : Représenter des modèles et algorithmes impliquant sélection et répétition trouvés dans la vie quotidienne en langage écrit ou diagrammes.

2.1.A.1 Les briques de base des algorithmes comprennent la séquence, la sélection et la répétition.
2.1.A.2 Les algorithmes peuvent contenir une sélection, par prise de décision, et une répétition, via des boucles.
2.1.A.3 La sélection se produit lorsque le choix de la façon dont l'exécution d'un algorithme va procéder est basé sur une décision vraie ou fausse.
2.1.A.4 La répétition est quand un processus se répète jusqu'à ce qu'un résultat souhaité soit atteint.
2.1.A.5 L'ordre dans lequel la séquence, la sélection et la répétition sont utilisées contribue au résultat de l'algorithme.

Source : Description du cours et de l'examen AP College Board

Un organigramme avec losange de décision : la sélection choisit quel chemin l'algorithme suit

Les algorithmes sont constitués de trois structures de contrôle 控制结构 : séquence (étapes dans l'ordre), sélection 选择 (choisir un chemin), et itération 迭代 (répéter des étapes). Ce sujet couvre la sélection et l'itération – les outils qui permettent à un programme de prendre des décisions et de boucler.

Les trois structures de contrôle : séquence, sélection et itération

Vocabulaire Entrainer

Anglais	Chinois	Pinyin
control structures/kənˈtrəʊl ˈstrʌktʃəz/	控制结构	kòng zhì jié gòu
selection/sɪˈlekʃn/	选择	xuǎn zé
iteration/ˌɪtəˈreɪʃn/	迭代	dié dài
boolean expression/ˈbuːlɪən ekˈspreʃn/	布尔表达式	bù ěr biǎo dá shì
relational operators/rɪˈleɪʃənl ˈɒpəreɪtəz/	关系运算符	guān xì yùn suàn fú
if statement/ɪf ˈsteɪtmənt/	条件语句	tiáo jiàn yǔ jù
Logical operators/ˈlɒdʒɪkl ˈɒpəreɪtəz/	逻辑运算符	luó jí yùn suàn fú
short-circuit evaluation/ʃɔːt ˈsɜːkɪt ɪˌvæljuːˈeɪʃn/	短路求值	duǎn lù qiú zhí
De Morgan's laws/də ˈmɔːɡənz lɔːz/	德摩根定律	dé mó gēn dìng lǜ
while loop/waɪl luːp/	循环	xún huán
infinite loop/ˈɪnfɪnət luːp/	无限循环	wú xiàn xún huán

2.2

Expressions booléennes

Programme

Objectif d'apprentissage 2.2.A : Développer du code pour créer des expressions booléennes avec des opérateurs relationnels et déterminer le résultat de ces expressions.

2.2.A.1 Les valeurs peuvent être comparées en utilisant les opérateurs relationnels == et != pour déterminer si les valeurs sont identiques. Avec les types primitifs, cela compare les valeurs primitives réelles. Avec les types de référence, cela compare les références d'objet.
2.2.A.2 Les valeurs numériques peuvent être comparées à l'aide des opérateurs relationnels <, >, <= et >= pour déterminer la relation entre les valeurs.
2.2.A.3 Une expression impliquant des opérateurs relationnels évalue une valeur booléenne.

Source : Description du cours et de l'examen AP College Board

Portes logiques et demi-additionneur

Une expression booléenne 布尔表达式 évalue à true ou false, en utilisant des opérateurs relationnels 关系运算符 : == (égal), != (différent), <, >, <=, >=. Notez que == compare les valeurs primitives mais les références d'objets pour les objets, donc utilisez .equals pour les Strings.

Les trois familles d'opérateurs : arithmétiques, relationnels et logiques

Explorer

Explorer la table de vérité AND

Une expression booléenne évalue à true ou false. AND est vrai uniquement lorsque les deux opérandes sont vrais ; basculez les entrées pour voir les quatre cas.

2.3

La instruction if

Programme

Objectif d'apprentissage 2.3.A : Développer du code pour représenter des processus logiques de branchement en utilisant des instructions de sélection et déterminer le résultat de ces processus.

2.3.A.1 Les instructions de sélection modifient l'exécution séquentielle des instructions.
2.3.A.2 Une instruction if est un type d'instruction de sélection qui affecte le flux de contrôle en exécutant différents segments de code en fonction de la valeur d'une expression booléenne.
2.3.A.3 Une sélection à un seul chemin (instruction if) est utilisée lorsqu'il y a un segment de code à exécuter sous une certaine condition. Dans ce cas, le corps n'est exécuté que lorsque l'expression booléenne est true.
2.3.A.4 Une sélection à deux chemins (instruction if-else) est utilisée lorsqu'il y a deux segments de code — l'un à exécuter lorsque l'expression booléenne est true et un autre segment pour le cas où l'expression booléenne est false. Dans ce cas, le corps de la⟩if⟩ est exécuté lorsque l'expression booléenne est true, et le corps de la⟩else⟩ est exécuté lorsque l'expression booléenne est false.

Source : Description du cours et de l'examen AP College Board

Une instruction if 条件语句 exécute un bloc seulement lorsque sa condition est vraie ; un else optionnel donne une alternative :

if (score >= 60) {
    System.out.println("Pass");
} else {
    System.out.println("Fail");
}

Feux tricolores : la sélection choisit quelle branche s'exécute, tout comme les instructions if choisissent les chemins de code

Explorer

Voir quelle branche un if choisit

Une instruction si exécute son corps uniquement lorsque la condition est vraie, sinon elle saute vers else. Faites glisser le score à travers les limites et observez la note changer.

2.4

Instructions if imbriquées

Programme

Objectif d'apprentissage 2.4.A : Développer du code pour représenter des processus logiques de branchement imbriqués et déterminer le résultat de ces processus.

2.4.A.1 Les instructions if imbriquées consistent en des instructions if, if-else ou if-else-if situées dans des instructions if, if-else ou if-else-if.
2.4.A.2 L'expression booléenne de l'instruction if imbriquée intérieure n'est évaluée que si l'expression booléenne de l'instruction if extérieure évalue à true.
2.4.A.3 Une sélection multi-chemin (if-else-if) est utilisée lorsqu'il existe une série d'expressions avec des segments de code différents pour chaque condition. La sélection multi-chemin se fait de sorte qu'aucun plus d'un segment de code n'est exécuté basé sur la première expression qui évalue à true. Si aucune expression n'évalue à true et qu'il y a une instruction else finale, alors le corps de la⟩else⟩ est exécuté.

Source : Description du cours et de l'examen AP College Board

Placer un if à l'intérieur d'un autre, ou enchaîner avec else if, teste plusieurs cas dans l'ordre. Seule la première branche correspondante s'exécute :

if (g >= 90) grade = 'A';
else if (g >= 80) grade = 'B';
else grade = 'C';

2.5

Expressions booléennes composées

Programme

Objectif d'apprentissage 2.5.A : Développer du code pour représenter des expressions booléennes composées et déterminer le résultat de ces expressions.

2.5.A.1 Les opérateurs logiques ! (non), && (et), et || (ou) sont utilisés avec des expressions booléennes. L'expression !a évalue à true si a est false et évalue à false sinon. L'expression a && b évalue à true si les deux a et b sont true et évalue à false sinon. L'expression a || b évalue à true si a est true, b est true, ou les deux, et évalue à false sinon. L'ordre de priorité pour l'évaluation des opérateurs logiques est ! (non), && (et), puis || (ou). Une expression impliquant des opérateurs logiques évalue à une valeur booléenne.
2.5.A.2 L'évaluation en court-circuit se produit lorsque le résultat d'une opération logique utilisant && ou || peut être déterminé en évaluant uniquement la première expression booléenne. Dans ce cas, la seconde expression booléenne n'est pas évaluée.

Source : Description du cours et de l'examen AP College Board

Évaluation court-circuit

Les opérateurs logiques 逻辑运算符 combinent des conditions : && (et – les deux vrais), || (ou – au moins un vrai), ! (non – inverser). Java utilise l'évaluation court-circuit 短路求值 : && s'arrête si le côté gauche est faux, et || s'arrête si le côté gauche est vrai – utile pour protéger contre les erreurs, par ex. if (n != 0 && total / n > 5).

2.6

Comparaison d'expressions booléennes

Programme

Objectif d'apprentissage 2.6.A : Comparer des expressions booléennes équivalentes.

2.6.A.1 Deux expressions booléennes sont équivalentes si elles évaluent à la même valeur dans tous les cas. Des tables de vérité peuvent être utilisées pour prouver que des expressions booléennes sont équivalentes.
2.6.A.2 La loi de De Morgan peut être appliquée aux expressions booléennes pour créer des expressions booléennes équivalentes. Selon la loi de De Morgan, l'expression booléenne !(a && b) est équivalente à !a || !b et l'expression booléenne !(a || b) est équivalente à !a && !b.

Objectif d'apprentissage 2.6.B : Développer du code pour comparer des références d'objets à l'aide d'expressions booléennes et déterminer le résultat de ces expressions.

2.6.B.1 Deux variables différentes peuvent contenir des références vers le même objet. Les références d'objet peuvent être comparées à l'aide de == et !=.
2.6.B.2 Une référence d'objet peut être comparée avec null, en utilisant == ou !=, pour déterminer si la référence pointe réellement vers un objet.
2.6.B.3 Les classes définissent souvent leur propre méthode equals, qui peut être utilisée pour spécifier les critères d'équivalence pour deux objets de la classe. L'équivalence de deux objets est généralement déterminée à l'aide d'attributs provenant des deux objets.
- Instruction d'exclusion : Redéfinir la méthode equals sort du champ d'application du cours et de l'examen AP Computer Science A.

Source : Description du cours et de l'examen AP College Board

Les lois de De Morgan 德摩根定律 réécrivent les négations : !(a && b) est égal à !a || !b, et !(a || b) est égal à !a && !b. Deux expressions booléennes sont équivalentes si elles donnent le même résultat pour chaque entrée – une table de vérité le prouve. Simplifier des conditions de cette manière est une tâche d'examen courante.

2.7

Boucles while

Programme

Objectif d'apprentissage 2.7.A : Identifier quand un processus itératif est nécessaire pour atteindre un résultat souhaité.

2.7.A.1 L'itération est une forme de répétition. Les instructions d'itération modifient le flux de contrôle en répétant un segment de code zéro ou plusieurs fois tant que l'expression booléenne contrôlant la boucle évalue à true.
2.7.A.2 Une boucle infinie se produit lorsque l'expression booléenne dans une instruction itérative évalue toujours à true.
2.7.A.3 Le corps de la boucle d'une instruction itérative ne s'exécutera pas si l'expression booléenne évalue initialement à false.
2.7.A.4 Les erreurs off by one surviennent lorsque l'instruction d'itération parcourt la boucle une fois de trop ou une fois de moins.

Objectif d'apprentissage 2.7.B : Développer du code pour représenter des processus itératifs en utilisant des boucles while et déterminer le résultat de ces processus.

2.7.B.1 Une boucle while est un type d'instruction itérative. Dans les boucles while, l'expression booléenne est évaluée avant chaque itération du corps de la boucle, y compris la première. Lorsque l'expression évalue à true, le corps de la boucle est exécuté. Cela continue jusqu'à ce que l'expression booléenne évalue à false, moment où l'itération se termine.

Source : Description du cours et de l'examen AP College Board

Une boucle while 循环 répète tant que sa condition reste vraie, en testant avant chaque passage. Vous devez changer quelque chose à l'intérieur pour que la boucle s'arrête eventually, sinon elle devient une boucle infinie 无限循环 :

Les trois types de boucles diffèrent par l'endroit où la condition est testée

int i = 0;
while (i < 5) {
    System.out.println(i);
    i++;
}

Explorer

Tracer une boucle while

Une boucle while répète tant que sa condition reste vraie, mettant à jour ses variables à chaque passage. Parcourez pour voir la somme des carrés se constituer.

2.8

Boucles for

Programme

Objectif d'apprentissage 2.8.A : Développer du code pour représenter des processus itératifs à l'aide de boucles for et déterminer le résultat de ces processus.

2.8.A.1 Une boucle for est un type d'instruction itérative. Il y a trois parties dans l'en-tête d'une boucle for : l'initialisation, l'expression booléenne et la mise à jour.
2.8.A.2 Dans une boucle for, l'instruction d'initialisation n'est exécutée qu'une seule fois avant la première évaluation de l'expression booléenne. La variable initialisée est appelée variable de contrôle de boucle. L'expression booléenne est évaluée immédiatement après l'initialisation de la variable de contrôle de boucle, puis après chaque exécution de l'instruction d'incrémentation jusqu'à ce qu'elle soit false. À chaque itération, la mise à jour est exécutée après l'exécution complète du corps de la boucle et avant que l'expression booléenne ne soit évaluée à nouveau.
2.8.A.3 Une boucle for peut être réécrite sous la forme d'une boucle while équivalente (et vice versa).

Source : Description du cours et de l'examen AP College Board

Une boucle for regroupe l'initialisation, la condition et la mise à jour en une seule ligne – idéale quand vous connaissez le compteur :

for (int i = 0; i < n; i++) {
    // runs n times, i = 0..n-1
}

Un for et un while équivalent font le même travail ; soyez capable de convertir entre eux.

Une chaîne de montage : les boucles répètent un processus pour chaque élément, comme for et while

Explorer

Tracer une boucle for

Une boucle for s'exécute un nombre fixe de fois, son compteur parcourant une plage. Observez le compteur et le total en cours avancer d'un passage à la fois.

2.9

Construire des algorithmes complets de sélection et d'itération

Programme

Objectif d'apprentissage 2.9.A : Développer du code pour des algorithmes standards et originaux (sans structures de données) et déterminer le résultat de ces algorithmes.

2.9.A.1 Il existe des algorithmes standards pour :
- identifier si un entier est ou non divisible par un autre entier
- identifier les chiffres individuels d'un entier
- déterminer la fréquence à laquelle un critère spécifique est rempli
- déterminer une valeur minimale ou maximale
- calculer une somme ou une moyenne

Source : Description du cours et de l'examen AP College Board

Combinez des boucles et des conditions pour résoudre des problèmes réels – compter, sommer, trouver un maximum, ou tester une propriété :

int max = arr[0];
for (int k = 1; k < arr.length; k++) {
    if (arr[k] > max) max = arr[k];
}

Deux motifs entiers que l'examen teste directement utilisent % et /. Pour lire les chiffres d'un entier un par un, prenez répétément n % 10 (le dernier chiffre) puis n = n / 10 (supprimez-le). Pour tester la divisibilité, n % d == 0 signifie que n est divisible uniformément par d. Combinez-les avec un compteur pour trouver la fréquence à laquelle certains critères sont satisfaits.

Des motifs standards comme un total cumulé, un compteur ou un flag 标志 (un booléen qui enregistre si quelque chose s'est produit) reviennent tout au long du cours.

Vocabulaire Entrainer

Anglais	Chinois	Pinyin
flag/flæɡ/	标志	biāo zhì
nested loop/ˈnestɪd luːp/	嵌套循环	qiàn tào xún huán
Run-time analysis/rʌn taɪm əˈnæləsɪs/	运行时间分析	yùn xíng shí jiān fēn xī

2.10

Algorithmes sur les chaînes

Programme

Objectif d'apprentissage 2.10.A : Développer du code pour des algorithmes standards et originaux impliquant des chaînes et déterminer le résultat de ces algorithmes.

2.10.A.1 Il existe des algorithmes de chaînes standards pour :
- trouver si une ou plusieurs sous-chaînes ont une propriété particulière
- déterminer le nombre de sous-chaînes répondant à des critères spécifiques
- créer une nouvelle chaîne avec les caractères inversés

Source : Description du cours et de l'examen AP College Board

Parcourez une chaîne par indice pour traiter chaque caractère :

for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    // count vowels, reverse, check for a substring, ...
}

Tâches typiques : compter les occurrences, construire une copie inversée ou filtrée, ou tester si une chaîne en contient une autre.

2.11

Itération imbriquée

Programme

Objectif d'apprentissage 2.11.A : Développer du code pour représenter des processus itératifs imbriqués et déterminer le résultat de ces processus.

2.11.A.1 Les instructions d'itération imbriquées sont des instructions d'itération apparaissant dans le corps d'une autre instruction d'itération. Lorsqu'une boucle est imbriquée dans une autre boucle, la boucle interne doit terminer toutes ses itérations avant que la boucle externe puisse continuer à son prochaine itération.

Source : Description du cours et de l'examen AP College Board

Une boucle imbriquée 嵌套循环 place une boucle à l'intérieur d'une autre ; la boucle intérieure se termine complètement pour chaque passage de la boucle extérieure. Si la boucle extérieure tourne $n$ fois et l'intérieure $m$ fois, le corps s'exécute $n\times m$ fois – base pour traiter des grilles et comparer toutes les paires.

2.12

Analyse informelle du temps d'exécution

Programme

Objectif d'apprentissage 2.12.A : Calculer les comptes d'exécution d'instructions et comparer informellement le temps d'exécution des statements itératifs.

2.12.A.1 Un compte d'exécution d'instruction indique le nombre de fois qu'une instruction est exécutée par le programme. Les comptes d'exécution d'instructions sont souvent calculés informellement par traçage et analyse des instructions itératives.

Source : Description du cours et de l'examen AP College Board

Taux de croissance Big-O

L'analyse du temps d'exécution 运行时间分析 compte combien d'étapes de base un algorithme effectue alors que la taille de l'entrée $n$ croît. Comptez les exécutions de l'instruction la plus interne : une boucle unique sur $n$ éléments est linéaire ($n$ étapes) ; deux boucles imbriquées sur $n$ sont quadratiques ($n^2$). Ce comptage informel permet de comparer l'efficacité de deux algorithmes.

Comment le temps d'exécution augmente avec le nombre d'éléments n

Compétence pour l'examen : pour une boucle imbriquée, savoir énoncer combien de fois la statement intérieure s'exécute en fonction des bornes des boucles – une question à choix multiples fréquente.

Exemple résolu. Combien d'étoiles cela imprime-t-il ?

for (int i = 0; i < 4; i++)
    for (int j = 0; j < i; j++)
        System.out.print("*");

La boucle intérieure s'exécute i fois pour chaque i extérieure : 0 + 1 + 2 + 3 = 6 étoiles. Quand la borne intérieure est la variable extérieure, le total est la somme triangulaire $0+1+\dots+(n-1)=\dfrac{n(n-1)}{2}$ – ici $\dfrac{4\times3}{2}=6$ – et non la totale $n^2=16$ d'une boucle imbriquée rectangulaire.

Explorer

Comparer comment les algorithmes évoluent

Le temps d'exécution décrit comment le nombre d'étapes croît avec la taille de l'entrée $n$. Augmentez $n$ et observez une complexité linéaire $O(n)$ devancer largement une complexité quadratique $O(n^2)$.

2.12

Conseils d'examen

Bien définir les conditions aux limites : utiliser < vs <= délibérément, et surveiller la première et la dernière itération de chaque boucle (l'erreur off-by-one est classique).
Construire des conditions composées avec &&, ||, ! et se souvenir de l'évaluation court-circuit (mettre la vérification de null en premier).
Tracer les boucles imbriquées en comptant combien de fois le corps intérieur s'exécute au total.
Choisir la bonne structure – if/else if pour les plages, une boucle pour la répétition – et éviter une boucle infinie en actualisant la variable de boucle.
Appliquer les lois de De Morgan lorsque vous simplifiez ou néguez une condition booléenne.

Leçons interactives sur ce sujet

Traversez-le étape par étape, avec des exercices à vérification instantanée.

Épreuves Passées

Plus de sujets dans AP Informatique A

Collections de données