Quiz — Algorithmique et programmation

Question 1 : Que contient la liste `L = [k**2 for k in range(5)]` ?

• `[1, 4, 9, 16, 25]`
• ✓ `[0, 1, 4, 9, 16]`
• `[0, 1, 4, 9, 16, 25]`
• `[2, 4, 6, 8, 10]`

Explication : **Méthode 4 (générer une liste en compréhension)** : l'expression `k**2` est calculée pour chaque `k` de l'itérable. Par la **Propriété 1**, `range(5)` parcourt $0, 1, 2, 3, 4$ (la borne 5 est exclue), d'où `[0, 1, 4, 9, 16]` : option B. Les deux pièges classiques sont d'oublier que `range` commence à 0 et qu'il exclut sa borne supérieure.

Question 2 : On exécute : `L = [3, 8, 1]` puis `L.append(5)` puis `L.pop(0)`. Que vaut `L` ensuite ?

• `[3, 8, 1, 5]`
• `[8, 1]`
• ✓ `[8, 1, 5]`
• `[3, 8, 5]`

Explication : **Propriété 3 (opérations sur les listes)** : `L.append(5)` ajoute 5 en fin de liste, d'où `[3, 8, 1, 5]`. Puis `L.pop(0)` retire l'élément d'indice 0, c'est-à-dire la valeur 3 — et non la valeur 0. Il reste donc `[8, 1, 5]` : option C.

Question 3 : Quelle valeur renvoie la fonction ci-dessous pour `L = [4, 7, 2, 9]` ? Elle initialise `m` à `L[0]`, puis pour chaque `x` de `L`, si `x > m` elle affecte `x` à `m`, et enfin renvoie `m`.

• ✓ `9`
• `4`
• `2`
• `22`

Explication : **Méthode 2 (rechercher dans une liste)** : c'est le patron de la recherche du maximum. La variable `m` conserve le plus grand élément rencontré : elle vaut 4, puis 7 (car `7 > 4`), reste 7 (car `2 < 7`), puis devient 9. La fonction renvoie donc 9, le maximum de la liste : option A. La valeur 22 serait la somme des éléments, c'est-à-dire le résultat du patron d'accumulation (**Méthode 1**).

Question 4 : Que vaut `s` après l'exécution de `s = 0` puis `for i in range(1, 6): s = s + i` ?

• `21`
• `10`
• `6`
• ✓ `15`

Explication : **Méthode 1 (parcourir et accumuler)** : `s` est un accumulateur initialisé à 0 avant la boucle. Par la **Propriété 1**, `range(1, 6)` parcourt $1, 2, 3, 4, 5$ (6 est exclu), donc $s = 1 + 2 + 3 + 4 + 5 = 15$ : option D. Avec `range(1, 7)` on obtiendrait $21$.

Question 5 : Que renvoie la fonction ci-dessous pour `p = 0.5` ? Elle initialise `n = 0` et `q = 1`, puis tant que `q > 0.01` elle multiplie `q` par `1 - p` et augmente `n` de 1 ; enfin elle renvoie `n`.

• `6`
• ✓ `7`
• `100`
• `2`

Explication : **Méthode 5 (recherche de seuil avec `while`)** : après $n$ tours, `q` vaut $(1-p)^n = 0{,}5^n$, et la boucle continue tant que `q > 0.01` (**Propriété 2**). Or $0{,}5^6 \approx 0{,}0156 > 0{,}01$ et $0{,}5^7 \approx 0{,}0078 \leq 0{,}01$ : la boucle s'arrête après le 7e tour. La fonction renvoie 7, le plus petit $n$ tel que $(1-p)^n \leq 0{,}01$ (problème de seuil) : option B.

Question 6 : Quelle liste en compréhension construit les entiers de 1 à 20 divisibles par 3 ?

• ✓ `[k for k in range(1, 21) if k % 3 == 0]`
• `[k % 3 for k in range(1, 21)]`
• `[3 * k for k in range(1, 21)]`
• `[k for k in range(1, 20) if k / 3 == 0]`

Explication : **Méthode 4 (générer une liste en compréhension)** : le filtre s'écrit après `if`, avec l'opérateur `%` (reste de la division euclidienne). `[k for k in range(1, 21) if k % 3 == 0]` garde les entiers de 1 à 20 (borne 21 exclue, **Propriété 1**) dont le reste par 3 est nul : `[3, 6, 9, 12, 15, 18]`, option A. La troisième option produirait les multiples de 3 jusqu'à 60, et la dernière confond `/` (division) avec `%`.

Question 7 : Que renvoie la fonction ci-dessous pour `L = [2, 5, 8, 12, 16, 23, 38]` et `x = 12` ? Elle parcourt les indices `i` de `0` à `len(L) - 1` et renvoie `i` dès que `L[i] == x` ; si la boucle se termine, elle renvoie `-1`.

• `12`
• `4`
• `-1`
• ✓ `3`

Explication : **Méthode 2 (rechercher la position d'un élément)** : la fonction parcourt les indices et renvoie le premier `i` tel que `L[i] == x` ; `return` sort immédiatement de la fonction (**Propriété 2**). Par la **Propriété 1**, les indices commencent à 0 : 2 est à l'indice 0, 5 à l'indice 1, 8 à l'indice 2 et 12 à l'indice 3. La fonction renvoie donc 3 : option D. Le `-1` n'est renvoyé que si `x` est absent de la liste.

Question 8 : Combien de fois la boucle interne s'exécute-t-elle au total dans le programme : `for i in range(4): for j in range(i + 1, 4): print(i, j)` ?

• `16`
• `12`
• ✓ `6`
• `4`

Explication : **Méthode 6 (boucles imbriquées)** : pour chaque `i`, la boucle interne parcourt `range(i + 1, 4)`, c'est-à-dire les `j > i`. Pour `i = 0` : 3 tours ; `i = 1` : 2 tours ; `i = 2` : 1 tour ; `i = 3` : aucun. Total : $3 + 2 + 1 + 0 = 6 = \binom{4}{2}$, le nombre de paires $(i, j)$ avec $i < j$ : option C. Répondre 16 reviendrait à compter $4 \times 4$ couples sans la contrainte $j > i$.

Question 9 : On simule une épreuve de Bernoulli de paramètre `p` avec `random()`, qui renvoie un réel aléatoire de $[0\,;\,1[$. Quelle instruction convient ?

• `if random() == p: succes = 1`
• ✓ `if random() < p: succes = 1`
• `if random() > 1: succes = 1`
• `succes = random() * p`

Explication : **Propriété 4 (simulation d'une épreuve de Bernoulli)** : `random()` renvoie un réel uniforme de $[0\,;\,1[$, donc la probabilité qu'il tombe dans $[0\,;\,p[$, c'est-à-dire que `random() < p` soit vrai, vaut exactement $p$ (la longueur de l'intervalle). C'est le test utilisé dans la **Méthode 7 (simulation modulaire)** : option B. Le test d'égalité `random() == p` a une probabilité pratiquement nulle d'être vrai, et `random() > 1` est toujours faux.

Question 10 : Que renvoie la fonction ci-dessous pour `n = 4` ? Elle part de `ligne = [1]` et, `n` fois, construit une nouvelle liste commençant par 1, contenant les sommes `ligne[k] + ligne[k+1]` pour `k` de `0` à `len(ligne) - 2`, et finissant par 1 ; cette nouvelle liste remplace `ligne`. Elle renvoie `ligne`.

• ✓ `[1, 4, 6, 4, 1]`
• `[1, 3, 3, 1]`
• `[1, 2, 1]`
• `[4, 6, 4]`

Explication : **Méthode 9 (ligne du triangle de Pascal)** : chaque tour construit la ligne suivante du triangle grâce à la relation de Pascal, en additionnant les termes voisins et en encadrant par des 1. Les lignes successives sont `[1]`, `[1, 1]`, `[1, 2, 1]`, `[1, 3, 3, 1]` puis, après le 4e tour, `[1, 4, 6, 4, 1]` : option A. On obtient les coefficients binomiaux $\binom{4}{k}$ pour $k$ de 0 à 4.