Université Clermont Auvergne Portail Maths Info, LAS Maths-Info, PASS Info
Algorithmique et Programmation en Python - Semestre 1
Algorithmique et Programmation en Python
TD5 : Les listes au sens de Python
Exercice 1 : Les classiques
On se propose ici de réécrire un certain nombre de fonctions classiques de manipulation de listes, disponibles par
défaut en Python mais pas dans d’autres langages comme le C par exemple. On s’interdira donc d’utiliser les
fonctions Python prédéfinies, mentionnées en remarque à la suite de chaque question. En revanche, vous pouvez
(devez) utiliser len pour accéder à la taille de la liste.
Remarque : avant d’avoir vu les boucles for, il est possible de faire tous ces exercices en utilisant des boucles while.
1. Affichage d’une liste Écrire une fonction affiche qui prend en argument une liste et un argument optionnel
separateur (valant par défaut un espace) et qui affiche le contenu de la liste, chaque élément étant séparé
du précédent par le séparateur demandé. Pour simplifier, on écrira également ce séparateur après le dernier
élément.
2. Test d’appartenance Écrire une fonction appartient qui prend en paramètre une liste de nombres et un
nombre, et qui teste si ce nombre appartient bien à la liste. Cette fonction renvoie donc un booléen.
Remarque : Python permet de faire ce test avec le mot-clé in.
3. Indice d’apparition Écrire une fonction indice qui prend en paramètre une liste de nombres et un nombre,
et qui renvoie l’indice de la première position de ce nombre dans cette liste, ou renvoie -1 si le nombre n’y
apparaît pas.
Remarque : Python a une fonction index().
4. Comptage d’élément Écrire une fonction nb_occ qui prend en paramètre une liste de nombres et un
nombre et qui compte combien de fois ce nombre apparaît dans la liste. La fonction renvoie ce compteur.
Remarque : Python dispose d’une fonction count prédéfinie.
5. Recherche de minimum Écrire une fonction minimum qui prend en paramètre une liste de nombres et qui
renvoie son élément minimum, ou None si la liste est vide.
6. Recherche de maximum Écrire une fonction maximum qui prend en paramètre une liste de nombres et qui
renvoie l’indice de son plus grand élément, ou None si la liste est vide.
Remarque : les fonctions correspondantes en Python s’appellent min et max.
7. Calcul de somme Écrire une fonction somme qui prend en paramètre une liste de nombres et renvoie la
somme de ces nombres.
Remarque : la fonction sum est l’équivalent pré-existant.
8. Calcul de moyenne Écrire une fonction moyenne qui prend en paramètre une liste de nombres et renvoie
la moyenne de ces nombres.
Remarque : Le module statistics contient une fonction mean qui calcule la moyenne.
Exercice 2 : Compter et remplacer les multiples
1. Écrire une fonction nb_multiples qui reçoit en paramètre une liste d’entiers li et un entier x, qui compte
combien d’éléments de li sont multiples de x, et qui renvoie la valeur de ce compteur. Par exemple pour x = 3
et li = [3, 2, 5, 9] la fonction renvoie 2. Pour la même liste mais x = 4, la fonction renvoie 0.
2. Écrire une fonction remplace_multiples qui reçoit en paramètre une liste d’entiers li et un entier x, qui
remplace tous les multiples de x dans li par x. Votre liste doit donc être modifiée par effet de bord. La
fonction ne renvoie rien.
Exercice 3 : Générer des listes d’entiers
1. Écrire une fonction puissances qui reçoit en paramètre un entier n, et qui renvoie la liste des puissances de 2,
de la puissance 0 à la puissance n incluse. Par exemple pour n = 5, la fonction renvoie la liste [1, 2, 4, 8, 16, 32].
2. Écrire une fonction diviseurs qui prend en argument un entier supposé strictement positif et renvoie la liste
de ses diviseurs.
UCA - Licence N1 / LAS / PASS - UE Info. - Python 1
Exercice 4 : Création de listes
1. Écrire une fonction saisie_listes qui ne prend pas d’argument et qui demande à l’utilisateur de taper des
entiers (jusqu’à obtenir 0), ajoute les entiers strictement positifs pairs à une liste, les entiers positifs impairs à
une autre liste, et ne fait rien des entiers négatifs. Elle renverra ces deux listes. Le programme affiche ensuite
les 2 listes.
2. Ecrire ensuite un programme principal qui fait appel à cette fonction pour demande à l’utilisateur de taper
des entiers, puis qui affiche le contenu des deux listes (la liste des pairs et la liste des impairs). Par exemple
si l’utilisateur tape 1,-5,7,8,13,-4,0 alors le programme affiche :
pairs: [8]
impairs: [1, 7, 13]
On remarque que les nombres négatifs et le 0 ne sont pas affichés.
Exercice 5 : Code à trous
Complétez le code suivant pour qu’il corresponde à ce que l’on obtiendrait dans un interpréteur Python.
>> Multiple3 = [3, 6, 9, 15, 21]
>> Multiple3[2]
________________________
>> Multiple3[____]
21
>> Multiple3.____________________
>> Multiple3
[3, 6, 9, 15, 21, 24]
>> Multiple3 = [3, 6, 9, 15, 21, 24, 27]
>> [Link]( ___, 12)
>> [Link]( ___, 18)
>> Multiple3
[3, 6, 9, 12, 15, 18, 21, 24, 27]
>> Multiple3.___________([30,33])
>> Multiple3
[3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33]
>> Multiple3.__________________
>> Multiple3
[3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36]
>> EhEh = ["tra", "la", "la", "la", "lère"])
>> EhEh.__________
>> EhEh
["tra", "la", "la", "la"]
>> EhEh.__________
>> EhEh
["tra", "la", "la"]
Exercice 6 : Jeu de dé et statistiques
1. Écrire une fonction une_partie qui prend en paramètre un entier n, lance n fois un dé à 6 faces, stocke les
n résultats dans une liste d’entiers, et la renvoie.
Remarque : Rappelez-vous de la fonction randint du module random qui prend en argument deux entiers a
et b et renvoie un entier tiré au hasard entre a et b (bornes incluses).
2. Écrire une fonction compteurs_faces qui prend en paramètre une liste de n tirages, et calcule et renvoie une
liste de 6 compteurs indiquant le nombre d’apparitions de chaque face dans cette liste. On s’appliquera à ne
parcourir qu’une seule fois la liste de tirages, et donc on s’abstiendra d’utiliser count.
3. Écrire une fonction stats_partie qui prend en paramètre une liste de n tirages, et affiche pour chaque face
le pourcentage de tirages qui l’ont obtenue. (Par exemple : 1 - 17.2% ; 2 - 15.5% ; etc). On utilisera la
fonction compteurs_faces.
4. Écrire une fonction face_gagnante qui prend en paramètre une liste de n tirages, et renvoie la face qui est
apparue le plus souvent sur cette partie (la plus grande si égalité). On utilisera la fonction compteurs_faces.
5. Écrire un programme principal qui demande à l’utilisateur le nombre de tirages par partie (n), le nombre
UCA - Licence N1 / LAS / PASS - UE Info. - Python 2
de parties à jouer (p) ; qui joue p parties de n tirages ; qui affiche pour chaque partie la face gagnante ; qui
affiche pour chaque face combien de parties elle a gagné.
Exercice 7 : Comptage alphabétique (force brute vs subtile)
1. Écrire une fonction compte_carac qui prend en paramètre une liste de caractères et une lettre, compte
combien de fois cette lettre apparaît dans la liste (que ce soit en minuscule ou en majuscule), et renvoie le
résultat.
2. Écrire une fonction compte_alphab qui prend en paramètre une liste de caractères, compte toutes les lettres
de l’alphabet avec la fonction précédente, et renvoie la liste des 26 compteurs.
3. Question : combien de fois a-t-on parcouru la liste de caractères ?
4. Écrire une nouvelle fonction compte_alphab2 qui compte toutes les lettres de l’alphabet en un seul parcours
de la liste de caractères, et renvoie la liste des 26 compteurs.
5. Bonus avec des dictionnaires (que l’on verra dans un prochain chapitre) : écrire une fonction compte_alphab_dico
pour compter tous les caractères qui apparaissent dans un texte ; il peut y avoir des caractères non alpha-
bétiques, et surtout on ne sait pas à l’avance quels caractères apparaissent ou pas. Cette fonction renvoie
un dictionnaire dont les clés sont les caractères du texte, et dont les valeurs associées sont les compteurs
correspondants.
Exercice 8 : Manipulation de listes de caractères
1. Écrire une fonction tailles(liste) qui prend en argument une liste des chaînes de caractères et renvoie la liste
des tailles de chaque élément de la liste.
2. Écrire une fonction lire(n) qui reçoit en paramètre un entier n, lit au clavier n chaînes de caractères, les
stocke dans une liste, et renvoie cette liste. Un exemple d’exécution avec n=5 :
Tapez un mot : train
Tapez un mot : cheval
Tapez un mot : voiture
Tapez un mot : avion
Tapez un mot : accordeon
['train','cheval','voiture','avion','accordeon']
3. Écrire une fonction affiche(liste) qui reçoit en paramètre une liste de chaînes, calcule la liste de leurs tailles,
affiche chaque chaîne et sa taille, puis la moyenne des tailles. Cette fonction ne renvoie rien. Par exemple
avec la liste précédente :
Taille du mot train : 5
Taille du mot cheval: 6
Taille du mot voiture: 7
Taille du mot avion: 5
Taille du mot accordeon: 9
Taille moyenne: 6.4
4. Compléter la fonction précédente pour afficher aussi les mots plus longs que la taille moyenne, sur une seule
ligne.
Mots plus longs que la moyenne: voiture ; accordeon ;
5. Écrire une fonction nbocc(mot,carac) qui compte et renvoie le nombre d’occurrences (le nombre d’appari-
tions) d’un caractère donné dans une chaîne donnée.
6. Utiliser la fonction nbocc pour écrire une fonction compteCarac(liste,car) qui prend en paramètre une liste
de chaînes et un caractère, affiche les mots contenant ce caractère et le nombre total d’occurrences de ce
caractère dans tous les mots. Si ce caractère n’est présent dans aucun mot, la fonction affiche un message
d’erreur à la place. Cette fonction ne renvoie rien. Deux exemples d’exécution (avec la liste précédente de 5
mots et la lettre ’o’ puis ’w’) :
Mots contenants le caractère o :
voiture
avion
accordéon
Le caractère o apparaît 4 fois.
Erreur la lettre w n’est présente dans aucun des mots
UCA - Licence N1 / LAS / PASS - UE Info. - Python 3
7. Utiliser la fonction nbocc pour trouver le mot d’une liste (reçue en paramètre) où un caractère donné (en
paramètre) apparaît le plus de fois. En cas d’égalité, favoriser le mot le plus court contenant autant de fois
ce caractère. Renvoyer ce mot. Version avancée : renvoyer ce mot et le nombre d’occurrences du caractère
dedans.
8. Écrire un programme principal qui utilise les fonctions ci-dessus et : lit au clavier le nombre de mots de la
liste, puis les mots ; les affiche avec leur taille ; puis lit un caractère, le compte dans les mots, et affiche le mot
qui contient le plus de fois ce caractère.
9. Comment modifier ce programme pour proposer à l’utilisateur de rejouer la dernière étape (même liste,
nouveau caractère à compter) jusqu’à ce qu’il refuse ?
Pour des raisons écologiques, l’impression papier de cette fiche TD s’arrête à la page 4. Vous trouverez la suite
dans la version PDF sur Moodle.
Exercice 9 : Jeu de démineur (listes de listes)
Dans cet exercice on veut coder un jeu de démineur (avec un affichage uniquement textuel). Même si cet exercice
est d’abord abordé en TD, il vous est conseillé de le tester ensuite sur machine. La grille de démineur (à N lignes
et M colonnes) sera représentée par une liste de listes de valeurs. Chaque liste de M éléments contient toutes les
valeurs d’une ligne donnée de la grille. La liste de N éléments contient donc les N lignes de la grille. Il s’agit ici
de la grille solution, c’est-à-dire la grille contenant la position des mines. Il est par ailleurs nécessaire de stocker
aussi une autre grille, indiquant quelles cases ont déjà été dévoilées par le joueur. On choisit pour cela d’utiliser
une liste de listes de booléens. La valeur True dans une case signifie que le joueur a déjà dévoilé cette case, alors
que la valeur False signifie que cette case n’a pas encore été dévoilée.
1. Écrire une fonction creerGrille qui : reçoit en paramètres les entiers N et M, et un paramètre optionnel v
(par défaut 0) représentant la valeur d’initialisation de toutes les cellules ; crée une grille de démineur à N
lignes et M colonnes (donc une liste de N listes de M entiers), ne contenant que des valeurs v (0 par défaut,
ou autre si spécifiée) ; et renvoie cette liste. Par exemple pour N=5 et M=7 on obtient la liste suivante :
[[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0]]
2. Écrire une fonction placerMines qui : reçoit en paramètre une grille de démineur et un entier X ; modifie
cette liste pour y placer X mines (valeur 1) à des positions au hasard ; ne renvoie rien. Par exemple si on
demande de placer 7 mines dans la liste précédente, on obtient :
[[0, 0, 1, 0, 0, 0, 0], [0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0]]
3. Écrire une fonction afficheSolution qui : reçoit en paramètre une liste positionsMines (grille d’entiers
indiquant les positions des mines), et affiche cette grille sous la forme d’un rectangle de caractères représentant
la solution du démineur, c’est-à-dire dévoilant les positions des mines. On choisit d’afficher avec un ’-’ (tiret)
les cases non minées (valeur 0), et avec une ’*’ (étoile) les cases minées (valeur 1). Par exemple la liste
précédente sera affichée sous la forme suivante (à gauche avant placement des mines, à droite après) :
------- --*----
------- --***--
------- ------*
------- *----*-
------- -------
4. Écrire une fonction testMine qui : prend en paramètre la grille des positions des mines, et 2 coordonnées
i (numéro de ligne entre 0 et N-1) et j (numéro de colonne entre 0 et M-1) supposées correctes (on n’a pas
besoin de les tester) ; vérifie s’il y a une mine sur la case indiquée par ces coordonnées ; et renvoie un booléen
indiquant le résultat. Par exemple :
testMine(0,2) renvoie True
testMine(1,1) renvoie False
5. Écrire une fonction compteMinesVoisines qui : prend en paramètre la grille des positions des mines, et 2
coordonnées i et j supposées correctes ; compte le nombre de mines sur les cases voisines (attention aux effets
de bord, certaines cases ont moins de voisines que d’autres ! 3 voisines dans les coins, 5 voisines sur les bords,
8 voisines au centre) ; renvoie ce compteur. On pourra utiliser une fonction auxilliaire qui calcule et renvoie
la liste des cellules voisines d’une cellule donnée.
UCA - Licence N1 / LAS / PASS - UE Info. - Python 4
6. Écrire une fonction afficheJeu qui : reçoit en paramètre une liste positionsMines (grille d’entiers indiquant
les positions des mines), et une liste casesDevoilees (grille de booléens indiquant les cases dévoilées) ; affiche
la grille de jeu sous la forme d’un rectangle de caractères représentant la grille telle que le joueur la voit pendant
la partie (il ne voit pas les positions des mines). On choisit d’afficher avec un ’ ?’ (point d’interrogation) les
cases non encore découvertes ; avec un ’*’ une case découverte minée (se produit quand le joueur perd) ;
sur les cases découvertes non minées, on affichera un entier indiquant le nombre de mines sur les cellules
voisines (compté avec la fonction précédente). Par exemple affichage avec seulement 2 cases découvertes dans
les coins :
0??????
???????
???????
???????
??????1
7. Écrire une fonction getCoords qui : reçoit en paramètre la grille indiquant les cases déjà dévoilées, et les
dimensions N et M ; qui demande à l’utilisateur des coordonnées i et j et les filtre jusqu’à ce qu’elles soient
correctes (comprises dans les bornes autorisées et correspondant à une case non encore dévoilée) ; puis qui
renvoie ces coordonnées une fois correctes. Attention : on ne redemande que la coordonnée incorrecte s’il
n’y en a qu’une. Exemples d’interactions :
A toi de jouer !
Ligne? 10
Ligne < 5 svp ? 18
Ligne < 5 svp ? 4
Colonne? 10
Colonne < 7 svp ? 7
Colonne < 7 svp ? 6
A toi de jouer !
Ligne? 3
Colonne? 4
Case deja devoilee, recommence
Ligne? 3
Colonne? 5
8. Écrire un programme principal qui :
— Initialise une grille
— Demande à l’utilisateur le nombre X de mines à placer et le filtre, puis place les X mines
— Initialise la grille de booléens indiquant les cases dévoilées (pour l’instant aucune)
— Affiche la grille de jeu
— Demande à l’utilisateur un coup (filtre jusqu’à avoir des coordonnées correctes) et dévoile la case cor-
respondante dans la grille de booléens
— Vérifie s’il a perdu (touché une mine) : dans ce cas s’arrête et affiche la grille de jeu (y compris la mine
touchée), puis la solution. Par exemple :
Perdu, touche une mine !
0??????
01*????
???????
???????
???????
La solution etait :
-------
--*-***
-------
---**--
------*
— Sinon affiche la grille de jeu, en remplaçant donc le ? de la nouvelle cellule dévoilée par le nombre de
mines sur ses cases voisines
UCA - Licence N1 / LAS / PASS - UE Info. - Python 5
— Recommence avec un nouveau coup
— S’arrête dès que le joueur perd (en touchant une mine), ou une fois qu’il a dévoilé toutes les cases sauf
les mines (dans ce cas il a gagné). Par exemple :
Coup numero 28
A toi de jouer !
Ligne? 4
Colonne? 6
1?22110
23?2?10
?224320
221??10
?112210
Tu as gagne en 28 coups, bravo !
— Attention : ce programme principal doit utiliser les fonctions déjà codées ci-dessus.
9. Bonus : quand le joueur choisit une case à découvrir qui n’est entourée d’aucune mine, découvrir automati-
quement récursivement toutes les cases voisines qui n’ont pas de mines (c-à-d qu’on peut dévoiler automati-
quement toutes les voisines d’une case dont on sait qu’elle a 0 mines sur ses voisines, et ainsi de suite pour
les autres cases découvertes ainsi qui ont aussi 0 mines voisines).
Exercice 10 : Insertion par recherche dichotomique
Étant donnée une liste d’entiers triée dans l’ordre croissant, on souhaite insérer un nouvel élément à la bonne
position pour garder la liste triée.
1. Écrire une fonction insert_intuitif(liste_triee, e) qui prend en argument une liste d’entiers supposée déjà
triée et un entier, et qui insère le nouvel élément par la méthode qui vous semble la plus intuitive. Attention
la fonction ne renvoie rien mais modifie la liste qui lui est passée en argument.
2. Si on note n la longueur de la liste, quel est le nombre maximum d’itérations utilisées dans insert_intuitif
pour réaliser l’insertion ?
On voudrait utiliser une méthode dichotomique pour insérer un entier e dans une liste triée. L’idée est de
comparer e avec un élément de la liste qu’on appelle le pivot, idéalement situé au milieu. Si e est plus grand que le
pivot alors il doit être inséré après, sinon il doit être inséré avant. On recommence ensuite la même opération avec
la moitié de liste concernée.
Illustrons cela par un exemple. Dans la liste [2, 12, 17, 25, 33, 35, 44, 54, 77, 91] on souhaite insérer 49. Pour chaque
itération on délimite par d et f la portion de la liste où l’on sait que 49 doit être inséré. p représente le pivot.
2 12 17 25 33 35 44 54 77 91
d p f
2 12 17 25 33 35 44 54 77 91
d p f
2 12 17 25 33 35 44 54 77 91
d p f
2 12 17 25 33 35 44 54 77 91
d p f
2 12 17 25 33 35 44 54 77 91
d f
On voit que 49 doit être inséré entre 44 et 54.
3. Écrire une fonction insert_dicho(liste_triee, e) qui implémente cette méthode.
4. Supposons que la longueur de la liste est une puissance de 2, notée n = 2k . Quel est le nombre d’itérations
utilisées dans insert_dicho pour réaliser l’insertion ? Quelle est la méthode la plus rapide ?
UCA - Licence N1 / LAS / PASS - UE Info. - Python 6
