Algorithmique, listes et Python Première : 6 exercices corrigés

Indices, parcours et filtrage sont testés sur des listes de formes différentes. Une recherche dichotomique, une génération de termes et une compréhension de liste obligent à justifier les bornes, l'ordre et les éventuelles répétitions.

Les définitions et méthodes utilisées sont réunies dans le cours de Algorithmique, listes et Python. La génération de listes s'applique directement aux les suites numériques.

Bases de Algorithmique, listes et Python : Parcourir une liste

Exercice 1 : Parcourir une liste

Facile

Le code for i in range(len(L) + 1): s += L[i] doit additionner une liste L.

  1. Repérer l'erreur.
  2. Corriger la boucle.
  3. Donner une seconde écriture plus directe.
Indication
Le dernier indice d'une liste de longueur nn est n−1n-1.
Voir le corrigé
  1. range(len(L)+1) produit l'indice len(L), situé hors de la liste. Le programme déclenche donc une erreur.
  2. La boucle corrigée est for i in range(len(L)): s += L[i].
  3. Sans avoir besoin des indices, on écrit plus directement for valeur in L: s += valeur.

Exercice 2 : Écarts entre termes consécutifs

Moyen

On donne L = [3, 8, -2, 5, 5, 11]. On veut construire la liste des différences entre deux termes consécutifs.

  1. Déterminer les indices de départ valides.
  2. Écrire une fonction Python qui renvoie la liste des différences.
  3. Donner la liste obtenue avec L.
  4. Compter les hausses, les baisses et les paliers.
Indication
La dernière différence utilise les éléments d'indices len(L)-2 et len(L)-1.
Voir le corrigé
  1. Pour former Li+1−LiL_{i+1}-L_i, il faut 0≤i≤len⁡(L)−20\leq i\leq\operatorname{len}(L)-2. En Python, cela correspond à range(len(L)-1).
  2. Une écriture concise est def ecarts(L): return [L[i+1] - L[i] for i in range(len(L)-1)].
  3. Avec L = [3, 8, -2, 5, 5, 11], la fonction renvoie [5, -10, 7, 0, 6].
  4. Les différences contiennent trois valeurs positives, une valeur négative et un zéro : il y a trois hausses, une baisse et un palier.

Choisir une méthode : Générer les premiers termes d'une suite et chercher un maximum

Exercice 3 : Générer les premiers termes d’une suite et chercher un maximum

Moyen

Pour un=3n2−2n+1u_n=3n^2-2n+1, on veut la liste des termes de u0u_0 à u10u_{10}, puis le plus grand terme.

  1. Écrire la compréhension de liste demandée.
  2. Justifier les bornes et le nombre de valeurs obtenues.
  3. Déterminer la valeur maximale de la liste.
  4. Expliquer comment retrouver son rang sans ignorer une éventuelle égalité.
Indication
Préciser le type de l'entrée, la liste attendue et le résultat retourné.
Voir le corrigé
  1. La compréhension est [3*n**2 - 2*n + 1 for n in range(11)].
  2. range(11) produit les indices 0 à 10 inclusivement. La liste contient 11 valeurs, ce qui contrôle la borne.
  3. La fonction max appliquée à la liste donne la valeur maximale.
  4. Pour connaître son rang, on cherche ensuite l'indice correspondant avec prudence en cas d'égalité.

Exercice 4 : Dichotomie dans une liste triée

Difficile

On cherche une valeur x dans une liste triée sans parcourir tous les éléments.

  1. Décrire les indices gauche, droite et milieu.
  2. Écrire la condition de boucle.
  3. Expliquer la mise à jour selon la comparaison.
  4. Donner la complexité qualitative par rapport au parcours complet.
Indication
À chaque étape, éliminer la moitié qui ne peut pas contenir x.
Voir le corrigé
  1. On initialise gauche = 0, droite = len(L) - 1, puis milieu = (gauche + droite) // 2 à chaque tour.
  2. La boucle continue tant que gauche <= droite et que la valeur n'a pas été trouvée.
  3. Si L[milieu] < x, on pose gauche = milieu + 1. Si L[milieu] > x, on pose droite = milieu - 1.
  4. Chaque étape élimine environ la moitié des candidats : le nombre d'étapes croît logarithmiquement, alors qu'un parcours complet est linéaire.

Approfondir Algorithmique, listes et Python : Relier compréhension de liste et ensemble défini par une propriété

Exercice 5 : Filtrer puis moyenner une liste

Moyen

On donne L = [12, 7, 15, 9, 18, 4]. On veut la moyenne des valeurs supérieures ou égales à 10.

  1. Construire la liste filtrée.
  2. Calculer sa moyenne.
  3. Prévoir le cas où aucune valeur ne satisfait la condition.
Indication
Séparer le filtrage du calcul de moyenne rend le code plus facile à contrôler.
Voir le corrigé
  1. F = [x for x in L if x >= 10] donne [12, 15, 18].
  2. La moyenne vaut 12+15+183=15\frac{12+15+18}{3}=15.
  3. Avant de diviser, il faut tester if len(F) == 0 afin d'éviter une division par zéro et de choisir un résultat explicite.

Exercice 6 : Relier compréhension de liste et ensemble défini par une propriété

Difficile

On exécute [n*n for n in range(-2, 3)] et l'on compare le résultat à l'ensemble des carrés d'entiers compris entre −2-2 et 2.

  1. Donner la liste produite par la compréhension.
  2. Donner l'ensemble des valeurs obtenues.
  3. Expliquer la différence entre les deux objets.
Indication
Une liste conserve l'ordre de parcours et les répétitions, contrairement à un ensemble.
Voir le corrigé
  1. La compréhension produit la liste [4, 1, 0, 1, 4].
  2. L'ensemble des valeurs est {0;1;4}\{0;1;4\}.
  3. La liste garde l'ordre des indices et contient deux fois 4 et deux fois 1. L'ensemble ne conserve ni cet ordre ni les doublons.
Partager