Livre Python1 Print
Livre Python1 Print
TOME 1
ARNAUD BODIN
A L G O R I T H M E S E T P R O G R A M M AT I O N
Exo7
Python au lycée – tome 1
C’est parti !
Tout le monde utilise un ordinateur, mais c’est une autre chose de le piloter ! Tu vas apprendre ici
les bases de la programmation. L’objectif de ce livre est double : approfondir les mathématiques à
travers l’informatique et maîtriser la programmation en s’aidant des mathématiques.
Python
Choisir un langage de programmation pour débuter est délicat. Il faut un langage avec une prise
en main facile, bien documenté, avec une grande communauté d’utilisateurs. Python possède
toutes ces qualités et davantage encore. Il est moderne, puissant et très utilisé, y compris par les
programmeurs professionnels.
Malgré toutes ces qualités, débuter la programmation (avec Python ou un autre langage) est
difficile. Le mieux est d’avoir déjà une expérience du code, à l’aide de Scratch par exemple. Il reste
quand même une grande marche à gravir et ce livre est là pour t’accompagner.
Objectif
Bien maîtriser Python te permettra d’apprendre facilement les autres langages. Surtout le langage
n’est pas le plus important, l’essentiel ce sont les algorithmes. Les algorithmes sont comme des
recettes de cuisine, il faut suivre pas à pas les instructions et ce qui compte, c’est le résultat final et
non le langage avec lequel a été écrite la recette. Ce livre n’est donc ni un manuel complet de Python,
ni un cours d’informatique, il ne s’agit pas non plus d’utiliser Python comme une super-calculatrice.
Le but est de découvrir des algorithmes, d’apprendre la programmation pas à pas à travers des
activités mathématiques/informatiques. Cela te permettra de mettre en pratique des mathématiques
avec ici la volonté de se limiter aux connaissances acquises au niveau seconde.
Vous pouvez récupérer l’intégralité des codes Python des activités ainsi que tous les fichiers
sources sur la page GitHub d’Exo7 : « GitHub : Python au lycée ».
Les vidéos des cours avec des explications pas à pas et la présentation des projets sont disponibles
depuis la chaîne Youtube : « Youtube : Python au lycée ».
Sommaire
I Mise en route 1
1 Premiers pas 3
II Fondamentaux 23
4 Fonctions 33
7 Listes I 63
9 Fichiers 85
11 Binaire I 101
12 Listes II 109
13 Binaire II 117
IV Projets 121
14 Probabilités – Paradoxe de Parrondo 123
15 Chercher et remplacer 127
16 Calculatrice polonaise – Piles 133
17 Visualiseur de texte – Markdown 147
18 L-système 157
19 Images dynamiques 167
20 Jeu de la vie 175
21 Graphes et combinatoire de Ramsey 183
22 Bitcoin 195
23 Constructions aléatoires 207
V Guides 217
24 Guide de survie Python 219
25 Principales fonctions 231
26 Notes et références 251
Index
Résumé des activités
Premiers pas
Lance-toi dans la programmation ! Dans cette toute première activité, tu vas apprendre à manipuler des
nombres, des variables et tu vas coder tes premières boucles avec Python.
Fonctions
Écrire une fonction, c’est la façon la plus simple de regrouper du code pour une tâche bien particulière,
dans le but de l’exécuter une ou plusieurs fois par la suite.
Listes I
Une liste est une façon de regrouper des éléments en un seul objet. Après avoir défini une liste, on peut
récupérer un par un chaque élément de la liste, mais aussi en ajouter de nouveaux. . .
Fichiers
Tu vas apprendre à lire et à écrire des données dans des fichiers.
Binaire I
Les ordinateurs transforment toutes les données en nombres et manipulent uniquement ces nombres.
Ces nombres sont stockés sous la forme de listes de 0 et de 1. C’est l’écriture binaire des nombres ! Pour
mieux comprendre l’écriture binaire, tu vas d’abord mieux comprendre l’écriture décimale.
Listes II
Les listes sont tellement utiles qu’il faut savoir les manipuler de façon simple et efficace. C’est le but de
cette fiche !
Binaire II
On continue notre exploration du monde des 0 et des 1.
Chercher et remplacer
Chercher et remplacer sont deux tâches très fréquentes. Savoir les utiliser et comprendre comment elles
fonctionnent te permettra d’être plus efficace.
L-système
Les L-systèmes offrent une façon très simple de coder des phénomènes complexes. À partir d’un mot
initial et d’opérations de remplacement, on arrive à des mots compliqués. Lorsque l’on « dessine » ces
mots, on obtient de superbes figures fractales. Le « L » vient du botaniste A. Lindenmayer qui a inventé
les L-systèmes afin de modéliser les plantes.
Images dynamiques
Nous allons déformer des images. En répétant ces déformations, les images deviennent brouillées. Mais
par miracle au bout d’un certain nombre de répétitions l’image de départ réapparaît !
Jeu de la vie
Le jeu de la vie est un modèle simple de l’évolution d’une population de cellules qui naissent et meurent
au cours du temps. Le « jeu » consiste à trouver des configurations initiales qui donnent des évolutions
intéressantes : certains groupes de cellules disparaissent, d’autres se stabilisent, certains se déplacent. . .
Bitcoin
Le bitcoin est une monnaie dématérialisée et décentralisée. Elle repose sur deux principes informatiques :
la cryptographie à clé publique et la preuve de travail. Pour comprendre ce second principe, tu vas créer
un modèle simple de bitcoin.
Constructions aléatoires
Tu vas programmer deux méthodes pour construire des figures qui ressemblent à des algues ou des
coraux. Chaque figure est formée de petits blocs lancés au hasard et qui se collent les uns aux autres.
P R E M I È R E PA R T I E
MISE EN ROUTE
Chapitre
Premiers pas
1
Lance-toi dans la programmation ! Dans cette toute première activité, tu vas apprendre à
manipuler des nombres, des variables et tu vas coder tes premières boucles avec Python.
1. Combien y a-t-il de secondes en un siècle ? (Ne tiens pas compte des années bissextiles.)
4 PREMIERS PAS
2. Jusqu’où faut-il compléter les pointillés pour obtenir un nombre plus grand qu’un milliard ?
(1 + 2) × (3 + 4) × (5 + 6) × (7 + 8) × · · ·
3. Quels sont les trois derniers chiffres de
123456789 × 123456789 × · · · ?
| {z }
7 occurrences de 123456789
4. 7 est le premier entier tel que son inverse a une écriture décimale périodique de longueur
6:
1
= 0. 142857
| {z } 142857
| {z } 142857
| {z } . . .
7
Trouve le premier entier dont l’inverse a une écriture décimale périodique de longueur 7 :
1
= 0.00 abcde f g abcde f g . . .
??? | {z } | {z }
Indication. L’entier est plus grand que 230 !
5. Trouve l’unique entier :
• qui donne un quotient de 107 lorsque l’on effectue sa division (euclidienne) par 11,
• et qui donne un quotient de 90 lorsque l’on effectue sa division (euclidienne) par 13,
• et qui donne un reste égal à 6 modulo 7 !
Cours 3 (Variables).
Variable. Une variable est un nom associé à un emplacement de la mémoire. C’est comme une
boîte que l’on identifie par une étiquette. La commande « a = 3 » signifie que j’ai une variable
« a » associée à la valeur 3.
Voici un premier exemple :
a = 3 # Une variable
b = 5 # Une autre variable
Commentaires. Tout texte qui suit le caractère dièse « # » n’est pas exécuté par Python mais
sert à expliquer le programme. C’est une bonne habitude de commenter abondamment ton code.
Noms. Il est très important de donner un nom clair et précis aux variables. Par exemple, avec
les noms bien choisis tu devrais savoir ce que calcule le code suivant :
base = 8
hauteur = 3
aire = base * hauteur / 2
print(aire)
print(Aire) # !! Erreur !!
Attention ! Python distingue les majuscules des minuscules. Donc mavariable, Mavariable
et MAVARIABLE sont des variables différentes.
Réaffectation. Imaginons que tu veuilles tenir tes comptes journaliers. Tu pars d’une somme
S0 = 1000, le lendemain tu gagnes 100, donc maintenant S1 = S0 + 100 ; le jour d’après tu
rajoutes 200, donc S2 = S1 + 200 ; puis tu perds 50, donc au troisième jour S3 = S2 − 50. Avec
Python tu peux n’utiliser qu’une seule variable S pour toutes ces opérations.
S = 1000
S = S + 100
S = S + 200
S = S - 50
print(S)
Il faut comprendre l’instruction « S = S + 100 » comme ceci : « je prends le contenu de la
boîte S, je rajoute 100, je remets tout dans la même boîte ».
Activité 2 (Variables).
Objectifs : utiliser des variables !
1. (a) Définis des variables, puis calcule l’aire d’un trapèze. Ton programme doit afficher
"L'aire vaut ..." en utilisant print("L'aire vaut",aire).
b=4
h=3
B=7
(b) Définis des variables pour calculer le volume d’une boîte (un parallélépipède rectangle)
dont les dimensions sont 10, 8, 3.
6 PREMIERS PAS
(c) Définis une variable PI qui vaut 3.14. Définis un rayon R = 10. Écris la formule de l’aire
du disque de rayon R.
2. Remets les lignes dans l’ordre de sorte qu’à la fin x ait la valeur 46.
(1) y = y - 1
(2) y = 2*x
(3) x = x + 3*y
(4) x = 7
3. Tu places la somme de 1000 euros sur un compte d’épargne. Chaque année les intérêts
sur l’argent placé rapportent 10% (le capital est donc multiplié par 1.10). Écris le code qui
permet de calculer le capital pour les trois premières années.
4. Je définis deux variables par a = 9 et b = 11. Je souhaite échanger le contenu de a et b.
Quelles instructions conviennent de sorte qu’à la fin a vaut 11 et b vaut 9 ?
c = a
c = b c = a
a = b a = c
a = b a = b
b = a c = b
b = c b = c
b = c
x = sqrt(2)
print(x)
print(x**2)
p
La première ligne importe toutes les fonctions du module math, la seconde calcule x = 2
PREMIERS PAS 7
angle = pi/2
print(angle)
print(sin(angle))
• Décimal vers entier.
Dans le module math il y aussi des fonctions pour arrondir un nombre décimal :
— round() arrondit à l’entier le plus proche : round(5.6) renvoie 6, round(1.5) renvoie
2.
— floor() renvoie l’entier inférieur ou égal : floor(5.6) renvoie 5.
— ceil() renvoie l’entier supérieur ou égal : ceil(5.6) renvoie 6.
1. La fonction Python pour le pgcd est gcd(a,b) (sans le « p », pour greatest common divisor).
Calcule le pgcd de a = 10 403 et b = 10 506. Déduis-en le ppcm de a et b. La fonction ppcm
n’existe pas, tu dois utiliser la formule :
a×b
ppcm(a, b) = .
pgcd(a, b)
2. Trouve par tâtonnement un nombre réel x qui vérifie toutes les conditions suivantes (plu-
sieurs solutions sont possibles) :
• abs(x**2 - 15) est inférieur à 0.5
• round(2*x) renvoie 8
• floor(3*x) renvoie 11
• ceil(4*x) renvoie 16
Indication. abs() désigne la fonction valeur absolue.
3. Tu connais la formule de trigonométrie
cos2 θ + sin2 θ = 1.
Vérifie que pour θ = π7 (ou d’autres valeurs) cette formule est numériquement vraie. (Ce
n’est pas une preuve de la formule, car Python ne fait que des calculs approchés du sinus
et du cosinus).
8 PREMIERS PAS
Note bien que ce qui délimite le bloc d’instructions à répéter, c’est l’indentation, c’est-à-dire
les espaces placées en début de ligne qui décalent les lignes vers la droite. Toutes les lignes
d’un bloc doivent avoir exactement la même indentation. Dans ce livre, nous choisissons une
indentation de 4 espaces.
N’oublie pas les deux points en fin de la ligne de la déclaration du for !
• Exemple de boucle « pour ».
Voici une boucle qui affiche les premiers carrés.
for i in range(10):
print(i*i)
La seconde ligne est décalée et constitue le bloc à répéter. La variable i prend la valeur 0 et
l’instruction affiche 02 ; puis i prend la valeur 1, et l’instruction affiche 12 ; puis 22 , 32 . . .
Au final ce programme affiche :
0, 1, 4, 9, 16, 25, 36, 49, 64, 81.
Attention : la dernière valeur prise par i est bien 9 (et pas 10).
• Parcourir une liste quelconque.
La boucle « pour » permet de parcourir n’importe quelle liste. Voici une boucle qui affiche le
cube des premiers nombres premiers.
for p in [2,3,5,7,11,13]:
print(p**3)
• Sommes des entiers.
Voici un programme qui calcule
0 + 1 + 2 + 3 + · · · + 18 + 19.
PREMIERS PAS 9
somme = 0
for i in range(20):
somme = somme + i
print(somme)
Comprends bien ce code : une variable somme est initialisée à 0. On va tour à tour lui ajouter
0, puis 1, puis 2. . . On peut mieux comprendre cette boucle en complétant un tableau :
Initialisation : somme= 0
i somme
0 0
1 1
2 3
3 6
4 10
... ...
18 171
19 190
Affichage : 190
• range().
— Avec range(n) on parcourt les entiers de 0 à n − 1. Par exemple range(10)
correspond à la liste [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].
Attention ! la liste s’arrête bien à n − 1 et pas à n. Ce qu’il faut retenir c’est que la
liste contient bien n éléments (car elle commence à 0).
— Si tu veux afficher la liste des éléments parcourus, il faut utiliser la commande :
list(range(10))
— Avec range(a,b) on parcourt les éléments de a à b−1. Par exemple range(10,20)
correspond à la liste [10, 11, 12, 13, 14, 15, 16, 17, 18, 19].
— Avec range(a,b,pas) on parcourt les éléments a, a +pas, a +2pas. . . Par exemple
range(10,20,2) correspond à la liste [10, 12, 14, 16, 18].
• Imbrication de boucles.
Il est possible d’imbriquer des boucles, c’est-à-dire que dans le bloc d’une boucle, on utilise
une nouvelle boucle.
for x in [10,20,30,40,50]:
for y in [3,7]:
print(x+y)
Dans ce petit programme x vaut d’abord 10, y prend la valeur 3 puis la valeur 7 (le programme
affiche donc 13, puis 17). Ensuite x = 20, et y vaut de nouveau 3 puis 7 (le programme
10 PREMIERS PAS
Indications. Commence par définir une variable produit initialisée à la valeur 1. Utilise
range(a,b,2) pour obtenir un entier sur deux.
3. Affiche les tables de multiplication entre 1 et 10. Voici un exemple de ligne à afficher :
7 x 9 = 63
Utilise une commande d’affichage du style : print(a,"x",b,"=",a*b).
Chapitre
Tortue (Scratch
avec Python)
2
Le module turtle permet de tracer facilement des dessins en Python. Il s’agit de commander
une tortue à l’aide d’instructions simples comme « avancer », « tourner ». . . C’est le même
principe qu’avec Scratch, avec toutefois des différences : tu ne déplaces plus des blocs, mais
tu écris les instructions ; et en plus les instructions sont en anglais !
forward(100) # On avance
left(90) # 90 degrés à gauche
forward(50)
width(5) # Epaisseur du trait
forward(100)
color('red')
right(90)
forward(200)
exitonclick()
14 TORTUE (SCRATCH AVEC PYTHON)
Voici une liste des principales commandes, accessibles après avoir écrit :
from turtle import *
• forward(longueur) avance d’un certain nombre de pas
• backward(longueur) recule
• right(angle) tourne vers la droite (sans avancer) selon un angle donné en degrés
• left(angle) tourne vers la gauche
• setheading(direction) s’oriente dans une direction (0 = droite, 90 = haut, −90 = bas,
180 = gauche)
• goto(x,y) se déplace jusqu’au point (x, y)
• setx(newx) change la valeur de l’abscisse
• sety(newy) change la valeur de l’ordonnée
• down() abaisse le stylo
• up() relève le stylo
• width(epaisseur) change l’épaisseur du trait
• color(couleur) change la couleur : "red", "green", "blue", "orange", "purple". . .
• position() renvoie la position (x, y) de la tortue
• heading() renvoie la direction angle vers laquelle pointe la tortue
• towards(x,y) renvoie l’angle entre l’horizontale et le segment commençant à la tortue et
finissant au point (x, y)
• exitonclick() termine le programme dès que l’on clique
Les coordonnées de l’écran par défaut vont de −475 à +475 pour les x et de −400 à +400 pour
les y ; (0, 0) est au centre de l’écran.
300
200
100
(0, 0)
−400 −300 −200 −100 100 200 300 400 x
−100
−200
−300
TORTUE (SCRATCH AVEC PYTHON) 15
Activité 2 (Figures).
1. Pentagone. Trace un premier pentagone (en bleu). Tu dois répéter 5 fois : avancer de 100
pas, tourner de 72 degrés.
Indication. Pour construire une boucle utilise
for i in range(5):
(même si tu n’utilises pas ensuite la variable i).
2. Pentagone (bis). Définis une variable longueur qui vaut 200 et une variable angle qui
vaut 72 degrés. Trace un second pentagone (en rouge) en avançant cette fois de longueur
et en tournant de angle.
3. Dodécagone. Trace un polygone à 12 côtés (en violet).
Indication. Pour tracer un polygone à n côtés, il faut tourner d’un angle de 360/n degrés.
4. Spirale. Trace une spirale (en vert).
Indication. Construis une boucle, dans laquelle tu tournes toujours du même angle, mais
par contre tu avances d’une longueur qui augmente à chaque étape.
16 TORTUE (SCRATCH AVEC PYTHON)
Voici comment tracer le second dessin. Analyse l’imbrication des boucles et trace les dessins
suivants.
TORTUE (SCRATCH AVEC PYTHON) 17
for i in range(3):
color("blue")
forward(256)
left(120)
for i in range(3):
color("red")
forward(128)
left(120)
3 2
4 1
5 0
6 9
7 8
Par exemple :
• le point 3 est relié au point 6, car 2 × 3 = 6 ;
• le point 4 est relié au point 8, car 2 × 4 = 8 ;
• le point 7 est relié au point 4, car 2 × 7 = 14 = 4 (mod 10).
18 TORTUE (SCRATCH AVEC PYTHON)
Indications.
Pour les calculs modulo n, utilise l’expression (2*k) % n.
Voici comment obtenir les coordonnées des sommets. Cela se fait avec les fonctions sinus et
cosinus (disponibles à partir du module math). Les coordonnées (x i , yi ) du sommet numéro i,
peuvent être calculées par la formule :
2iπ 2iπ
x i = r cos et yi = r sin
n n
Ces sommets seront situés sur le cercle de rayon r, centré en (0, 0). Tu devras choisir r assez
grand (par exemple r = 200).
(x 1 , y1 )
(x i , yi ) 2iπ
yi = r sin n
(x 0 , y0 )
2iπ (0, 0) x
x i = r cos n
(x n−1 , yn−1 )
TORTUE (SCRATCH AVEC PYTHON) 19
[Link]('red')
[Link]('blue')
[Link](100)
[Link](90)
[Link](100)
Programme quatre tortues qui courent les unes après les autres :
tortue 4 tortue 3
tortue 1 tortue 2
position1 = [Link]()
position2 = [Link]()
angle1 = [Link](position2)
[Link](angle1)
• Tu places les tortues aux quatre coins d’un carré, par exemple en (−200, −200), (200, −200),
(200, 200) et (−200, 200).
• Tu récupères la position de la première tortue par position1 = [Link]().
Idem pour les autres tortues.
• Tu calcules l’angle entre la tortue 1 et la tortue 2 par la commande angle1 =
[Link](position2).
• Tu orientes la tortue 1 selon cet angle : [Link](angle1).
• Tu avances la tortue 1 de 10 pas.
Améliore ton programme en traçant à chaque fois un segment entre la tortue poursuivante et la
tortue poursuivie.
TORTUE (SCRATCH AVEC PYTHON) 21
D E U X I È M E PA R T I E
F O N D A M E N TA U X
Chapitre
3
Si ... alors ...
L’ordinateur peut réagir en fonction d’une situation. Si une condition est remplie il agit d’une
certaine façon, sinon il fait autre chose.
une condition
deux points
if condition :
instruction_1 bloc d’instructions indenté
instruction_2 sera exécuté uniquement
... si la condition est vérifiée
instructions suivantes
suite du programme
Voici un exemple, qui avertit un conducteur si une variable vitesse est trop grande.
On peut aussi exécuter des instructions si la condition n’est pas remplie à l’aide du mot « else ».
26 SI ... ALORS ...
if condition :
instruction bloc exécuté
instruction si la condition est vérifiée
...
else:
instruction bloc exécuté
... si la condition n’est pas vérifiée
instructions suivantes
Encore une fois c’est l’indentation qui délimite les différents blocs d’instructions. Voici un exemple
qui affiche le signe d’un nombre x.
if x >= 0:
print("Le nombre est positif.")
else:
print("Le nombre est négatif.")
Explications.
• La commande input() met en pause l’exécution du programme et attend de l’utilisateur
un texte (qu’il termine en appuyant sur la touche « Entrée »).
• Cette commande renvoie une chaîne de caractères.
• Si on veut un entier, il faut convertir la chaîne. Par exemple, ici age_chaine peut valoir
"17" (ce n’est pas un nombre mais une suite de caractères), alors que int(age_chaine)
vaut maintenant l’entier 17.
SI ... ALORS ... 27
• L’opération inverse est aussi possible, str() convertit un nombre en une chaîne. Par exemple
str(17) renvoie la chaîne "17" ; si age = 17, alors str(age) renvoie également "17".
• Définis une variable a, à laquelle tu affectes une valeur au hasard entre 1 et 12.
• Même chose pour une variable b.
• Affiche à l’écran la question : « Combien vaut le produit a × b ? » (Remplace a et b par leur
valeur !)
• Récupère la réponse de l’utilisateur et transforme-la en un entier.
• Si la réponse est correcte affiche « Bravo ! », sinon affiche « Perdu ! La bonne réponse était. . . ».
Test d’égalité. Pour tester si deux nombres x et y sont égaux, l’instruction est :
if x == y:
Le test d’égalité s’écrit bien avec le double signe égal « == ». Par exemple « x == 3 » renvoie
« vrai » si x vaut 3 et « faux » sinon.
Attention ! La commande « x = 3 » n’a rien à voir, cette instruction stocke 3 dans la variable
x.
Objectifs : piloter la tortue par un mot, chaque caractère correspondant à une instruction.
Tu donnes un mot à la tortue Python, par exemple AgAdaagAdaA, dans lequel chaque caractère
(lus de gauche à droite) correspond à une instruction que la tortue doit exécuter.
• A : avance de 100 en traçant,
• a : avance de 100 sans tracer,
28 SI ... ALORS ...
Indications. Voici comment parcourir les lettres d’un mot et tester si une lettre est le caractère
A:
for c in mot:
if c == "A":
instructions...
Cours 4 (Booléens).
• Un booléen est une donnée qui vaut soit la valeur « vrai », soit la valeur « faux ». En Python
les valeurs sont True et False (avec une majuscule).
• On obtient un booléen par exemple comme résultat de la comparaison de deux nombres. Par
exemple 7 < 4 vaut False (car 7 n’est pas plus petit que 4). Vérifie que print(7 < 4)
affiche False.
Voici les principales comparaisons :
— Test d’égalité : a == b
— Test inférieur strict : a < b
— Test inférieur large : a <= b
— Test supérieur : a > b ou a >= b
— Test non égalité : a != b
Par exemple 6*7 == 42 vaut True.
•
SI ... ALORS ... 29
Objectifs : trouver des nombres dont les chiffres vérifient certaines propriétés.
1. Le programme suivant affiche tous les entiers de 0 à 99. Comprends ce programme. Que
représentent les variables u et d ?
for d in range(10):
for u in range(10):
n = 10*d + u
print(n)
2. Trouve tous les entiers compris entre 0 et 999 qui vérifient toutes les propriétés suivantes :
• l’entier se termine par 3,
• la somme des chiffres est supérieure ou égale à 15,
• le chiffre des dizaines est pair.
3. Modifie ton programme précédent pour compter et afficher le nombre d’entiers vérifiant les
propriétés.
Activité 4 (Triangles).
Objectifs : déterminer les propriétés d’un triangle à partir des trois longueurs des côtés.
On se donne trois longueurs a, b et c. Tu vas déterminer les propriétés du triangle dont les
longueurs seraient a, b, c.
30 SI ... ALORS ...
a
b
Définis trois variables a, b et c avec des valeurs entières et a 6 b 6 c (ou bien demande à
l’utilisateur trois valeurs).
1. Ordre. Demande à Python de tester si les longueurs vérifient bien a 6 b 6 c. Affiche une
phrase pour la réponse.
2. Existence. Il existe un triangle correspondant à ces longueurs si et seulement si :
a + b > c.
Demande à Python de tester si c’est le cas et affiche la réponse.
3. Triangle rectangle. Demande à Python de tester si le triangle est un triangle rectangle.
(Pense au théorème de Pythagore.)
4. Triangle équilatéral. Teste si le triangle est équilatéral.
5. Triangle isocèle. Teste si le triangle est isocèle.
6. Angles aigus. Teste si tous les angles sont aigus (c’est-à-dire inférieurs ou égaux à 90
degrés).
Indications.
• La loi des cosinus permet de calculer un angle en fonction des longueurs :
a
b
γ
β
α c
−a2 + b2 + c 2 a2 − b2 + c 2 a2 + b2 − c 2
cos α = , cos β = , cos γ = .
2bc 2ac 2ab
• Pour tester si l’angle α est aigu il suffit de vérifier cos α > 0 (au final on ne calcule jamais
α, mais juste cos α).
4
Fonctions
Écrire une fonction, c’est la façon la plus simple de regrouper du code pour une tâche bien
particulière, dans le but de l’exécuter une ou plusieurs fois par la suite.
def affiche_carres():
def dit_bonjour():
for i in range(20):
print("Bonjour le monde !")
print(i**2)
return
return
Les instructions sont regroupées dans un bloc indenté. Le mot return (optionnel) indique la
fin de la fonction. Ces instructions ne sont exécutées que si j’appelle la fonction. Par exemple,
chaque fois que j’exécute la commande dit_bonjour(), Python affiche la phrase « Bonjour
le monde ! ». Chaque fois que j’exécute la commande affiche_carres(), Python affiche
0, 1, 4, 9, 16, . . ., c’est-à-dire les nombres i 2 pour i = 0, . . . , 19.
def affiche_mois(numero):
if numero == 1:
print("Nous sommes en janvier.")
if numero == 2:
print("Nous sommes en février.")
if numero == 3:
print("Nous sommes en mars.")
# etc.
return
Lorsqu’elle est appelée cette fonction affiche le nom du mois en fonction du nombre fourni en
entrée. Par exemple affiche_mois(3) va afficher "Nous sommes en mars.".
def calcule_cube(a):
cube = a * a * a # ou bien a**3
return cube
Cette fonction calcule le cube d’un nombre, par exemple calcule_cube(2) n’affiche rien mais
renvoie la valeur 8. Cette valeur peut être utilisée ailleurs dans le programme. Par exemple, que
font les instructions suivantes ?
x = 3
y = 4
z = calcule_cube(x) + calcule_cube(y)
print(z)
# Définition de la fonction
def ma_fonction (param) :
instruction_1
instruction_2
... un paramètre
return resultat
renvoie un résultat
# Appel de la fonction
x = 7
val = ma_fonction (x)
argument
appel de la fonction
résultat renvoyé
def somme_produit(a,b):
"""Calcule la somme et le produit de deux nombres"""
s = a + b
p = a * b
return s, p
La dernière ligne appelle la fonction avec les arguments 6 (pour le paramètre a) et 7 (pour le
paramètre b). Cette fonction renvoie deux valeurs, la première est affectée à som (qui vaut donc
ici 13) et la seconde à pro (qui vaut donc 42).
un ou plusieurs paramètres
Retenons donc :
• Il peut y avoir plusieurs paramètres en entrée.
• Il peut y avoir plusieurs résultats en sortie.
• Très important ! Il ne faut pas confondre afficher et renvoyer une valeur. L’affichage (par
la commande print()) affiche juste quelque chose à l’écran. La plupart des fonctions
n’affichent rien, mais renvoient une valeur (ou plusieurs). C’est beaucoup plus utile car cette
valeur peut être utilisée ailleurs dans le programme.
• Dès que le programme rencontre l’instruction return, la fonction s’arrête et renvoie le
résultat. Il peut y avoir plusieurs fois l’instruction return dans une fonction mais une seule
sera exécutée. On peut aussi ne pas mettre d’instruction return si la fonction ne renvoie
rien.
• Dans les instructions d’une fonction, on peut bien sûr faire appel à d’autres fonctions !
• Il est important de bien commenter tes programmes. Pour documenter une fonction, tu
peux décrire ce qu’elle fait en commençant par un docstring, c’est-à-dire une description (en
français) entourée par trois guillemets :
""" Ma fonction fait ceci et cela. """
à placer juste après l’entête.
• Lorsque l’on définit une fonction, les variables qui apparaissent entre les parenthèses sont
appelées les paramètres ; par contre, lorsque l’on appelle la fonction, les valeurs entre les
parenthèses sont appelées les arguments. Il y a bien sûr une correspondance entre les deux.
1. Trinômes.
(a) Écris une fonction trinome_1(x) qui dépend d’un paramètre x et qui renvoie la valeur
du trinôme 3x 2 − 7x + 4. Par exemple trinome_1(7) renvoie 102.
(b) Écris une fonction trinome_2(a,b,c,x) qui dépend de quatre paramètres a, b, c et x
et qui renvoie la valeur du trinôme ax 2 + bx + c. Par exemple trinome_2(2,-1,0,6)
renvoie 66.
2. Devises.
Prends soin de donner un nom intelligible à tes fonctions ainsi qu’aux variables. N’oublie pas
de documenter chaque fonction en ajoutant un petit texte explicatif entre triples guillemets
au tout début de ta fonction.
3. Volumes.
Construis des fonctions qui calculent et renvoient des volumes :
• le volume d’un cube en fonction de la longueur d’un côté,
• le volume d’une boule en fonction de son rayon,
• le volume d’un cylindre en fonction du rayon de sa base et de sa hauteur,
• le volume d’une boîte parallélépipède rectangle en fonction de ses trois dimensions.
Pour la valeur de π, tu prendras soit la valeur approchée 3.14, soit la valeur approchée
fournie par la constante pi du module math.
4. Périmètres et aires.
(a) Écris une fonction dont l’usage est perimetre_aire_rectangle(a,b) et qui renvoie
en sortie le périmètre et l’aire d’un rectangle de dimensions a et b.
(b) Même question avec perimetre_aire_disque(r) pour le périmètre et l’aire d’un
disque de rayon r.
(c) Utilise ta fonction précédente pour conjecturer à partir de quel rayon, l’aire d’un disque
est plus grande que le périmètre de ce disque.
Indication. Si tu veux balayer les rayons en incrémentant la valeur de 0.1 à chaque fois,
tu peux construire une boucle ainsi :
for rayon in range(0,30):
puis faire un appel à la fonction par perimetre_aire_disque(rayon/10).
Activité 3 (Tortue).
Objectifs : définir quelques fonctions qui dessinent des figures géométriques. Créer une
fonction est similaire à créer un bloc avec Scratch.
1. Programme une fonction triangle() qui dessine un triangle (en rouge, chaque côté
mesurant 200).
2. Programme une fonction carre() qui dessine un carré (en vert, chaque côté mesurant
200). Utilise une boucle « pour » afin de ne pas avoir à réécrire les mêmes instructions
plusieurs fois.
FONCTIONS 39
3. Programme une fonction hexagone(longueur) qui trace un hexagone (en bleu) d’une
longueur de côté donnée (l’angle pour tourner est de 60 degrés).
4. Programme une fonction polygone(n,longueur) qui trace un polygone régulier à n
côtés et d’une longueur de côté donnée (l’angle pour tourner est alors de 360/n degrés).
1. (a) Voici la réduction pour le prix d’un billet de train en fonction de l’âge du voyageur :
• réduction de 50% pour les moins de 10 ans ;
• réduction de 30% pour les 10 à 18 ans ;
• réduction de 20% pour les 60 ans et plus.
Écris une fonction reduction() qui renvoie la réduction en fonction de l’âge et dont
les propriétés sont rappelées dans le cadre ci-dessous :
reduction()
Usage : reduction(age)
Entrée : un entier correspondant à l’âge
Sortie : un entier correspondant à la réduction
Exemples :
• reduction(17) renvoie 30.
• reduction(23) renvoie 0.
(b) Déduis-en une fonction montant() qui calcule le montant à payer en fonction du tarif
normal et de l’âge du voyageur.
montant()
Usage : montant(tarif_normal,age)
Entrée : un nombre tarif_normal correspondant au prix sans
réduction et age (un entier)
Sortie : un nombre correspondant au montant à payer après réduction
Remarque : utilise la fonction reduction()
Exemple : montant(100,17) renvoie 70.
Une famille achète des billets pour différents trajets, voici le tarif normal de chaque
trajet et les âges des voyageurs :
• tarif normal 30 euros, enfant de 9 ans ;
• tarif normal 20 euros, pour chacun des jumeaux de 16 ans ;
• tarif normal 35 euros, pour chacun des parents de 40 ans.
40 FONCTIONS
(a) Programme une fonction calcul_est_exact() qui décide si la réponse donnée à une
multiplication est juste ou pas.
calcul_est_exact()
Usage : calcul_est_exact(a,b,reponse)
Entrée : trois entiers, reponse étant la réponse proposée au calcul
de a × b.
Sortie : « vrai » ou « faux », selon que la réponse est correcte ou pas
Exemples :
• calcul_est_exact(6,7,35) renvoie False.
• calcul_est_exact(6,7,42) renvoie True.
(b) Programme une fonction qui affiche une multiplication, demande une réponse et affiche
une petite phrase de conclusion. Tout cela en français ou en anglais !
test_multiplication()
Usage : test_multiplication(a,b,lang)
Entrée : deux entiers, la langue choisie (parmi "francais" ou
"anglais")
Sortie : rien
Remarque : utilise la fonction calcul_est_exact()
Exemple : test_multiplication(6,7,"anglais") demande,
en anglais, la réponse au calcul 6 × 7 et répond si c’est correct ou pas.
Bonus. Améliore ton programme afin que l’ordinateur propose tout seul des opérations
aléatoires au joueur. (Utilise la fonction randint() du module random.)
1. (a) Construis une fonction valeur_absolue(x) qui renvoie la valeur absolue d’un nombre
(sans utiliser la fonction abs() de Python !).
p
(b) Construis une fonction racine_du_carre(x) qui correspond au calcul de x 2 .
(c) On dit que deux fonctions (d’une variable) f et g sont expérimentalement égales si
f (i) = g(i) pour i = −100, −99, . . . , 0, 1, 2, . . . , 100. Vérifie par ordinateur que les deux
FONCTIONS 41
def ma_fonction(x):
x = x + 1
return x
x = 7
print(ma_fonction(x))
print(x)
— La variable x est initialisée à 7.
— L’appel de la fonction ma_fonction(x) est donc la même chose que ma_fonction(7)
et renvoie logiquement 8.
— Que vaut la variable x à la fin ? La variable x est inchangée et vaut toujours 7 ! Même
s’il y a eu entre temps une instruction x = x + 1. Cette instruction a changé le x à
l’intérieur de la fonction, mais pas le x en dehors de la fonction.
• Les variables définies à l’intérieur d’une fonction sont appelées variables locales. Elles
n’existent pas en dehors de la fonction.
• S’il existe une variable dans une fonction qui porte le même nom qu’une variable dans le
programme (comme le x dans l’exemple ci-dessus), c’est comme si il y avait deux variables
distinctes ; la variable locale n’existant que dans la fonction.
Pour bien comprendre la portée des variables, tu peux colorier les variables globales d’une
fonction en rouge, et les variables locales avec une couleur par fonction. Le petit programme
suivant définit une fonction qui ajoute un et une autre qui calcule le double.
variable globale
x = 7
def plus_un( x ):
x = x +1
variable locale
return x
def double( x ):
x = 2 * x
autre variable locale
return x
print( x )
print(plus_un( x ))
print(double( x ))
print( x )
Il est tout de même possible de forcer la main à Python et de modifier une variable globale
dans une fonction à l’aide du mot clé global. Voir la fiche « Calculatrice polonaise – Pile ».
Chapitre
Arithmétique –
Boucle tant que – I
5
Les activités de cette fiche sont centrées sur l’arithmétique : division euclidienne, nombres
premiers. . . C’est l’occasion d’utiliser intensivement la boucle « tant que ».
Cours 1 (Arithmétique).
On rappelle ce qu’est la division euclidienne. Voici la division de a par b, a est un entier positif,
b est un entier strictement positif (avec un exemple de 100 divisé par 7) :
a b 100 7
r q 2 14
reste quotient
Avec Python :
• a // b renvoie le quotient,
• a % b renvoie le reste.
1. Programme une fonction quotient_reste(a,b) qui fait les tâches suivantes à partir de
deux entiers a > 0 et b > 0 :
• Elle affiche le quotient q de la division euclidienne de a par b,
• elle affiche le reste r de cette division,
• elle affiche True si le reste r est bien positif et strictement inférieur à b, et False sinon,
• elle affiche True si on a bien l’égalité a = bq + r, et False sinon.
Voici par exemple ce que doit afficher l’appel quotient_reste(100,7) :
Division de a = 100 par b = 7
Le quotient vaut q = 14
Le reste vaut r = 2
Vérification reste 0 <= r < b ? True
Vérification égalité a = bq + r ? True
Remarque. il faut que tu vérifies sans tricher que l’on a bien 0 6 r < b et a = bq + r, mais
bien sûr cela doit toujours être vrai !
2. Programme une fonction est_pair(n) qui teste si l’entier n est pair ou pas. La fonction
renvoie True ou False.
Indications
• Première possibilité : calculer n % 2 et discuter selon les cas.
• Seconde possibilité : calculer n % 10 (qui renvoie le chiffre des unités) et discuter.
• Les plus malins arriveront à écrire la fonction sur deux lignes seulement (une pour
def... et l’autre pour return...)
3. Programme une fonction est_divisible(a,b) qui teste si b divise a. La fonction renvoie
True ou False.
une condition
deux points
while condition :
instruction_1 bloc d’instructions indenté
instruction_2 sera exécuté tant que
... la condition est vérifiée
instructions suivantes
suite du programme
ARITHMÉTIQUE – B OUCLE TANT QUE – I 45
Exemple.
Voici un programme qui affiche le compte à rebours
n = 10
10, 9, 8, . . . 3, 2, 1, 0. Tant que la condition n > 0 est
while n >= 0:
vraie, on diminue n de 1. La dernière valeur affichée
print(n)
est n = 0, car ensuite n = −1 et la condition « n > 0 »
n = n - 1
devient fausse donc la boucle s’arrête.
On résume ceci sous la forme d’un tableau :
Entrée : n = 10
n « n > 0 » ? nouvelle valeur de n
10 oui 9
9 oui 8
... ... ...
1 oui 0
0 oui −1
−1 non
Affichage : 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
Exemple.
Ce bout de code cherche la première puissance de n = 100
2 plus grande qu’un entier n donné. La boucle fait p = 1
prendre à p les valeurs 2, 4, 8, 16,. . . Elle s’arrête while p < n:
dès que la puissance de 2 est supérieure ou égale à p = 2 * p
n, donc ici ce programme affiche 128. print(p)
Entrées : n = 100, p = 1
p « p < n » ? nouvelle valeur de p
1 oui 2
2 oui 4
4 oui 8
8 oui 16
16 oui 32
32 oui 64
64 oui 128
128 non
Affichage : 128
46 ARITHMÉTIQUE – B OUCLE TANT QUE –I
Exemple.
Pour cette dernière boucle on a déjà programmé
une fonction est_pair(n) qui renvoie True si
n = 56
l’entier n est pair et False sinon. La boucle fait
while est_pair(n) == True:
donc ceci : tant que l’entier n est pair, n devient
n = n // 2
n/2. Cela revient à supprimer tous les facteurs 2
print(n)
de l’entier n. Comme ici n = 56 = 2 × 2 × 2 × 7, ce
programme affiche 7.
Entrée : n = 56
n « n est pair » ? nouvelle valeur de n
56 oui 28
28 oui 14
14 oui 7
7 non
Affichage : 7
Pour ce dernier exemple il est beaucoup plus naturel de démarrer la boucle par
while est_pair(n):
En effet est_pair(n) est déjà une valeur « vrai » ou faux ». On se rapproche d’une phrase
« tant que n est pair... »
Méthode.
• On rappelle que d divise n si et seulement si n % d vaut 0.
• La mauvaise idée est d’utiliser une boucle « pour d variant de 2 à n ». En effet, si par
exemple on sait que 7 est diviseur de 91 cela ne sert à rien de tester si 8, 9, 10 . . . sont
aussi des diviseurs car on a déjà trouvé le plus petit.
• La bonne idée est d’utiliser une boucle « tant que » ! Le principe est : « tant que je n’ai pas
ARITHMÉTIQUE – B OUCLE TANT QUE – I 47
obtenu mon diviseur, je continue de chercher ». (Et donc, dès que je l’ai trouvé, j’arrête
de chercher.)
• En pratique voici les grandes lignes :
— Commence avec d = 2.
— Tant que d ne divise pas n alors, passe au candidat suivant (d devient d + 1).
— À la fin d est le plus petit diviseur de n (dans le pire des cas d = n).
2. Nombres premiers (1).
Modifie légèrement ta fonction plus_petit_diviseur(n) pour écrire une première
fonction est_premier_1(n) qui renvoie « vrai » (True) si n est un nombre premier et
« faux » (False) sinon.
Par exemple est_premier_1(13) renvoie True, est_premier_1(14) renvoie False.
3. Nombres de Fermat.
Pierre de Fermat (∼1605–1665) pensait que tous les entiers Fn = 2(2 ) + 1 étaient des
n
On va améliorer notre fonction qui teste si un nombre est premier ou pas, cela nous permettra
de tester plus vite plein de nombres ou bien des nombres très grands.
4. Nombres premiers (2).
Améliore ta fonction en une fonction est_premier_2(n) qui ne teste pas tous les diviseurs
p
d jusqu’à n, mais seulement jusqu’à n.
Explications.
• Par exemple pour tester si 101 est un nombre premier, il suffit de voir s’il admet des
diviseurs parmi 2, 3, . . . , 10. Le gain est appréciable !
• Cette amélioration est due à la proposition suivante : si un entier n’est pas premier alors
p
il admet un diviseurs d qui vérifie 2 6 d 6 n.
p
• Au lieu de tester si d 6 n, il est plus facile de tester d 2 6 n !
5. Nombres premiers (3).
Améliore ta fonction en une fonction est_premier_3(n) à l’aide de l’idée suivante. On
teste si d = 2 divise n, mais à partir de d = 3, il suffit de tester les diviseurs impairs (on
teste d, puis d + 2. . . ).
• Par exemple pour tester si n = 419 est un nombre premier, on teste d’abord si d = 2
divise n, puis d = 3 et ensuite d = 5, d = 7. . .
• Cela permet de faire environ deux fois moins de tests !
• Explications : si un nombre pair d divise n, alors on sait déjà que 2 divise n.
6. Temps de calcul.
48 ARITHMÉTIQUE – B OUCLE TANT QUE –I
Compare les temps de calcul de tes différentes fonctions est_premier() en répétant par
exemple un million de fois l’appel est_premier(97). Voir le cours ci-dessous pour savoir
comment faire.
import timeit
print([Link]("ma_fonction_1(1000)",
setup="from __main__ import ma_fonction_1",
number=100000))
print([Link]("ma_fonction_2(1000)",
setup="from __main__ import ma_fonction_2",
number=100000))
Résultats.
Le résultat dépend de l’ordinateur, mais permet la comparaison des temps d’exécution des deux
fonctions.
• La mesure pour la première fonction (appelée 100 000 fois) renvoie 5 secondes. L’algorithme
n’est pas très malin. On teste si 7 × 1 = n, puis on teste 7 × 2 = n, 7 × 3 = n. . .
ARITHMÉTIQUE – B OUCLE TANT QUE – I 49
• La mesure pour la seconde fonction renvoie 0.01 seconde ! On teste si le reste de n divisé
par 7 est 0. La seconde méthode est donc 500 fois plus rapide que la première.
Explications.
• On appelle le module timeit.
• La fonction [Link]() renvoie le temps d’exécution en seconde. Elle prend comme
paramètres :
— une chaîne pour l’appel de la fonction à tester (ici est-ce que 1000 est divisible par 7),
— un argument setup="..." qui indique où trouver cette fonction,
— le nombre de fois qu’il faut répéter l’appel à la fonction (ici number=100000).
• faut que le nombre de répétitions soit assez grand pour éviter les incertitudes.
Il
Lettre a v i o n
Rang 0 1 2 3 4
Note qu’il y a 5 lettres dans le mot "avion" et qu’on y accède par les indices en commençant
par 0. Les indices sont donc ici 0, 1, 2, 3 et 4 pour la dernière lettre. De façon plus générale, si
mot est une chaîne, les caractères s’obtiennent par mot[i] pour i variant de 0 à len(mot)-1.
Cours 3 (Sous-chaînes).
On peut extraire plusieurs caractères d’une chaîne à l’aide de la syntaxe mot[i:j] qui renvoie
une chaîne formée des caractères numéro i à j − 1 (attention le caractère numéro j n’est pas
inclus !).
Par exemple si mot = "vendredi" alors :
• mot[0:4] renvoie la sous-chaîne "vend" formée des caractères de rang 0, 1, 2 et 3 (mais
pas 4),
• mot[3:6] renvoie "dre" correspondant aux rangs 3, 4 et 5.
Lettre v e n d r e d i
Rang 0 1 2 3 4 5 6 7
Objectifs : écrire petit à petit un programme qui renvoie le pluriel d’un mot donné.
1. Pour une chaîne mot, par exemple "chat", affiche le pluriel de ce mot en rajoutant un "s".
2. Pour un mot, par exemple "souris", affiche la dernière lettre de cette chaîne (ici "s").
Améliore ton programme de la première question, en testant si la dernière lettre est déjà un
"s" :
• si c’est le cas, il n’y a rien à faire pour le pluriel,
• sinon il faut ajouter un "s".
3. Teste si un mot se termine par "al". Si c’est le cas, affiche le pluriel en "aux" (le pluriel
de "cheval" est "chevaux"). (Ne tiens pas compte des exceptions.)
4. Rassemble tout ton travail des trois premières questions dans une fonction
met_au_pluriel(). La fonction n’affiche rien, mais renvoie le mot au pluriel.
CHAÎNES DE CARACTÈRES – ANALYSE D’UN TEXTE 53
met_au_pluriel()
Usage : met_au_pluriel(mot)
Entrée : un mot (une chaîne de caractères)
Sortie : le pluriel du mot
Exemples :
• met_au_pluriel("chat") renvoie "chats"
• met_au_pluriel("souris") renvoie "souris"
• met_au_pluriel("cheval") renvoie "chevaux"
affiche_conjugaison()
Usage : affiche_conjugaison(verbe)
Entrée : un verbe du premier groupe (une chaîne de caractères se
terminant par "er")
Sortie : pas de résultat mais l’affichage de la conjugaison du verbe
au présent
Exemple :
• affiche_conjugaison("chanter"), affiche "je
chante, tu chantes,..."
• affiche_conjugaison("choisir"), affiche
"Ce n'est pas un verbe du premier groupe."
distance_hamming()
Usage : distance_hamming(mot1,mot2)
Entrée : deux mots (des chaînes de caractères)
Sortie : la distance de Hamming (un entier)
Exemple : distance_hamming("LAPIN","SATIN") renvoie 2
2. Latin-cochon.
On transforme un mot commençant par une consonne selon la recette suivante :
• on déplace la première lettre à la fin du mot ;
• on rajoute le suffixe UM.
Par exemple VITRE devient ITREVUM ; BLANCHE devient LANCHEBUM ; CARAMEL de-
vient ARAMELCUM. Les mots commençant par une voyelle ne changent pas. Écris une
fonction latin_cochon() qui transforme un mot selon ce procédé.
latin_cochon()
Usage : latin_cochon(mot)
Entrée : un mot (une chaîne de caractères)
Sortie : le mot transformé en latin-cochon, s’il commence par une
consonne.
Exemple : latin_cochon("BONJOUR") renvoie "ONJOURBUM"
3. Verlan.
Écris une fonction verlan() qui renvoie un mot à l’envers : SALUT devient TULAS.
CHAÎNES DE CARACTÈRES – ANALYSE D’UN TEXTE 55
verlan()
Usage : verlan(mot)
Entrée : un mot (une chaîne de caractères)
Sortie : le mot à l’envers
4. Palindrome.
Déduis-en une fonction qui teste si un mot est un palindrome ou pas. Un palindrome est
un mot qui s’écrit indifféremment de gauche à droite ou de droite à gauche ; par exemple
RADAR est un palindrome.
est_un_palindrome()
Usage : est_un_palindrome(mot)
Entrée : un mot (une chaîne de caractères)
Sortie : « vrai » si le mot est un palindrome, « faux » sinon.
Activité 3 (ADN).
Une molécule d’ADN est formée d’environ six milliards de nucléotides. L’ordinateur est
donc un outil indispensable pour l’analyse de l’ADN. Dans un brin d’ADN il y a seulement
quatre types de nucléotides qui sont notés A, C, T ou G. Une séquence d’ADN est donc un
long mot de la forme : TAATTACAGACCTGAA...
1. Écris une fonction presence_de_A() qui teste si une séquence contient le nucléotide A.
presence_de_A()
Usage : presence_de_A(sequence)
Entrée : une séquence d’ADN (une chaîne de caractères parmi A, C,
T, G)
Sortie : « vrai » si la séquence contient « A », « faux » sinon.
2. Écris une fonction position_de_AT() qui teste si une séquence contient le nucléotide A
suivi du nucléotide T et renvoie la position de la première occurrence trouvée.
56 CHAÎNES DE CARACTÈRES – ANALYSE D’UN TEXTE
position_de_AT()
Usage : position_de_AT(sequence)
Entrée : une séquence d’ADN (une chaîne de caractères parmi A, C,
T, G)
Sortie : la position de la première séquence « AT » trouvée (commence
à 0) ; None si n’apparaît pas
Exemple :
• position_de_AT("CTTATGCT") renvoie 3
• position_de_AT("GATATAT") renvoie 1
• position_de_AT("GACCGTA") renvoie None
Indication. None est affecté à une variable pour signifier l’absence de valeur.
3. Écris une fonction position() qui teste si une séquence contient un code donné et renvoie
la position de la première occurrence.
position()
Usage : position(code,sequence)
Entrée : un code et une séquence d’ADN
Sortie : la position du début du code trouvé ; None si n’apparaît pas
Exemple : position("CCG","CTCCGTT") renvoie 2
4. Un crime a été commis dans le château d’Adéno. Tu as récupéré deux brins d’ADN, provenant
de deux positions éloignées de l’ADN du coupable. Il y a quatre suspects, dont tu as séquencé
l’ADN. Sauras-tu trouver qui est le coupable ?
Premier code du coupable : CATA
Second code du coupable : ATGC
ADN du colonel Moutarde :
CCTGGAGGGTGGCCCCACCGGCCGAGACAGCGAGCATATGCAGGAAGCGGCAGGAATAAGGAAAAGCAGC
ADN de Mlle Rose :
CTCCTGATGCTCCTCGCTTGGTGGTTTGAGTGGACCTCCCAGGCCAGTGCCGGGCCCCTCATAGGAGAGG
ADN de Mme Pervenche :
AAGCTCGGGAGGTGGCCAGGCGGCAGGAAGGCGCACCCCCCCAGTACTCCGCGCGCCGGGACAGAATGCC
ADN de M. Leblanc :
CTGCAGGAACTTCTTCTGGAAGTACTTCTCCTCCTGCAAATAAAACCTCACCCATGAATGCTCACGCAAG
la lettre majuscule « A » est codé par 65, la lettre minuscule « h » est codée par 104, le symbole
« # » par 35.
Voici la table des premiers caractères. Les numéros 0 à 32 ne sont pas des caractères imprimables.
Cependant le numéro 32 est le caractère espace " ".
39 ’ 49 1 59 ; 69 E 79 O 89 Y 99 c 109 m 119 w
1. La fonction chr() est une fonction Python qui renvoie le caractère associé à un code.
python : chr()
Usage : chr(code)
Entrée : un code (un entier)
Sortie : un caractère
Exemple :
• chr(65) renvoie "A"
• chr(123) renvoie "{"
2. La fonction ord() est une fonction Python correspondant à l’opération inverse : elle renvoie
le code associé à un caractère.
58 CHAÎNES DE CARACTÈRES – ANALYSE D’UN TEXTE
python : ord()
Usage : ord(carac)
Entrée : un caractère (une chaîne de longueur 1)
Sortie : un entier
Exemple :
• ord("A") renvoie 65
• ord("*") renvoie 42
Activité 4 (Majuscules/minuscules).
lettre_majuscule()
Usage : lettre_majuscule(carac)
Entrée : un caractère minuscule parmi "a",...,"z"
Sortie : la même lettre en majuscule
Exemple : lettre_majuscule("t") renvoie "T"
5. Écris une fonction majuscules() qui à partir d’une phrase écrite en minuscules renvoie la
même phrase écrite en majuscules. Les caractères qui ne sont pas des lettres minuscules
restent inchangés.
majuscules()
Usage : majuscules(phrase)
Entrée : une phrase
Sortie : la même phrase en majuscules
Exemple : majuscules("Bonjour le monde !") renvoie
"BONJOUR LE MONDE !"
CHAÎNES DE CARACTÈRES – ANALYSE D’UN TEXTE 59
formate_prenom_nom()
Usage : formate_prenom_nom(personne)
Entrée : le prénom et le nom d’une personne (sans accent, séparés
par une espace)
Sortie : le nom complet au format "Prenom NOM"
Exemple :
• formate_prenom_nom("harry Potter") renvoie "Harry
POTTER"
• formate_prenom_nom("LORD Voldemort") renvoie
"Lord VOLDEMORT"
Activité 5.
Objectifs : déterminer la langue d’un texte à partir de l’analyse des fréquences des lettres.
occurrences_lettre()
Usage : occurrences_lettre(lettre,phrase)
Entrée : une lettre et une phrase en majuscules (une chaîne de
caractères)
Sortie : le nombre d’occurrences de la lettre (un entier)
Exemple : occurrences_lettre("E","ESPRIT ES TU LA")
renvoie 2
2. Écris une fonction nombre_lettres() qui compte le nombre total de lettres qui appa-
raissent dans une phrase (en majuscules et sans accents). Ne pas compter les espaces, ni la
ponctuation.
60 CHAÎNES DE CARACTÈRES – ANALYSE D’UN TEXTE
nombre_lettres()
Usage : nombre_lettres(phrase)
Entrée : une phrase en majuscules (une chaîne de caractères)
Sortie : le nombre total de lettres de « A » à « Z » (un entier)
3. La fréquence d’apparition d’une lettre dans un texte ou une phrase est le pourcentage
donné selon la formule :
nombre d’occurrences de la lettre
fréquence d’apparition d’une lettre = × 100.
nombre total de lettres
pourcentage_lettre()
Usage : pourcentage_lettre(lettre,phrase)
Entrée : une lettre et une phrase en majuscules (une chaîne de
caractères)
Sortie : la fréquence d’apparition de la lettre (un nombre inférieur à
100)
Exemple : pourcentage_lettre("E","ESPRIT ES TU LA")
renvoie 16.66. . .
Utilise cette fonction pour afficher proprement la fréquence d’apparition de toutes les lettres
d’une phrase.
4. Voici la fréquence d’apparition des lettres selon la langue utilisée (source :
[Link]/wiki/Letter_frequency). Par exemple, la lettre la plus courante en français
est le « e » avec une fréquence de plus de 16%. Le « w » représente environ 2% des lettres
en anglais et en allemand, mais n’apparaît presque pas en français et en espagnol. Ces
fréquences varient aussi en fonction du texte analysé.
CHAÎNES DE CARACTÈRES – ANALYSE D’UN TEXTE 61
D’après toi, dans quelles langues ont été écrits les quatre textes suivants (les lettres de
chaque mot ont été mélangées).
TMAIER BERACUO RSU NU REBRA PRCEEH EIANTT NE ONS EBC NU GAOFREM EIMATR RERNAD
APR L RDUOE LAHECLE UIL TTNI A EUP SREP EC LGNGAEA TE RBONUJO ERMNOUSI DU
UBRACEO QUE OVSU EEST LIJO UQE OUVS EM MSZELBE BAEU ASNS MIERNT IS RVETO AGRAME
ES PRARPTOE A OEVTR AMGUPLE VUOS SEET EL PNIHXE DSE OSHET ED CSE BIOS A ESC MSOT
LE OUBRCEA NE ES ESTN ASP DE IEJO TE OUPR ERRNOTM AS BELEL XOVI IL OREVU NU RGLEA
ECB ILESSA EBOMTR AS PIOER EL NRDAER S EN ISIAST TE ITD MNO NOB EUSRMNOI NRPEEAZP
QEU UTOT EUTLRFTA IVT XUA SPNEDE DE UECIL UQI L TECEOU TECET NEOCL VATU BNEI UN
GMAEORF SNAS TUOED LE EOABURC OHENTXU TE NSCOFU UJRA SMIA UN EPU TRDA UQ NO
EN L Y ARRPEIDNT ULSP
WRE TREITE SO TSPA CUDHR AHNCT UND WIND SE STI RED AEVRT MTI ESEIMN IDNK RE ATH
END NEABNK WLOH IN EMD AMR ER AFTSS HIN IHSERC RE AHTL HIN MRWA EINM SHNO SAW
62 CHAÎNES DE CARACTÈRES – ANALYSE D’UN TEXTE
SRTIBG UD SO NGBA DNEI EIHSGTC ESISTH RAETV UD DEN LERNIOKG NITHC NDE LOENINKGRE
TIM OKRN UDN CHWFSEI NEIM NSOH ES STI IEN BIFTRLSEEEN DU BILESE IKDN OMKM EHG MIT
MIR RAG ECHNOS EPELSI EIPSL IHC ITM RDI HNCMA BEUTN MBLUNE DINS NA DEM TNDRAS
NMIEE UTETMR AHT CAMHN UDNGEL GDAWEN MIEN EATRV MENI VEART DUN OSTHER DU
CINTH SAW KNNOEIREGL RIM ILEES PRSTVRCIEH ISE IHGRU BEEILB RIGUH MNEI KNDI NI
RDNEUR NATBRLET STAESUL EDR WNID
DSNOACAIF ORP ANU DAEDALRI DNAAEIMTI EQU NNCOSETE EL RSTEOUL SMA AACTFAITNS
UQE LE TSVAO OINSRVUE DE US ANIGIICANOM EIORDP TOOD RTEIENS RPO LE ITOABOLRROA
ED QIUAMALI USOP A NSSRCAEAD LA TMREAAI NXTADAUEE ROP GOARLS EMESS DE
NNAMICLUIAPO Y LOVOIV A RES LE RHMEOB EOMDNEERPRD DE LOS RSOPMRIE OMTSIPE UEQ
CIIDADE LE RTDAAOZ ED LSA CELSAL Y LA NICOIOPS ED LAS UESVNA SSACA Y ES ITRMNEEOD
QEU AERFU EL UEQIN IIIRDEGAR LA NAIORTREICP DE AL RRTEIA
IMTRUESMME DNA TEH LNGIIV SI EYAS SIFH REA GJPNUIM DNA HET TTNOCO IS GHIH OH
OUYR DDADY SI IRHC DAN ROUY MA SI DOGO GKOILON OS USHH LTLIET BBYA NDOT OUY CYR
NEO OF HESET GNSRONIM YUO RE NANGO SIER PU SNIGING NAD OULLY EPADRS YUOR GINSW
DAN LYOLU KATE OT HET KSY TUB ITLL TATH MGNIRNO EREHT NATI INTGOHN ACN AHMR OYU
TWIH DADYD NDA MYMMA NSTIDGAN YB
Chapitre
7
Listes I
Une liste est une façon de regrouper des éléments en un seul objet. Après avoir défini une liste,
on peut récupérer un par un chaque élément de la liste, mais aussi en ajouter de nouveaux. . .
[2,3,5,7,11,13].
• Exemple de construction. Voici comment construire la liste qui contient les premiers carrés :
liste_carres = [] # On part d'un liste vide
for i in range(10):
liste_carres.append(i**2) # On ajoute un carré
À la fin liste_carres vaut :
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
1. Intérêts simples. On dispose d’une somme S0 . Chaque année ce placement rapporte des
intérêts en fonction de la somme initiale.
Par exemple avec une somme initiale S0 = 1000 et des intérêts simples de p = 10%. Les
intérêts sont de 100. Donc au bout d’un an, je dispose d’une somme de S1 = 1100, au bout
de deux ans S2 = 1200. . .
Programme une fonction interets_simples(S0,p,n) qui renvoie les listes des sommes
des n premières années. Par exemple interets_simples(1000,10,3) renvoie [1000,
1100, 1200, 1300].
LISTES I 65
2. Intérêts composés. Une somme S0 rapporte selon des intérêts composés. Cette fois les
intérêts sont calculés chaque année sur la base de la somme de l’année précédente, c’est-à-
dire selon la formule :
p
I n+1 = Sn ×
100
Programme une fonction interets_composes(S0,p,n) qui renvoie la liste des sommes
des n premières années. Par exemple interets_composes(1000,10,3) renvoie
[1000, 1100, 1210, 1331].
3. J’ai le choix entre un placement à intérêts simples de 10% et un placement à intérêts
composés de 7%. Quelle est la solution la plus avantageuse en fonction de la durée du
placement ?
1. Programme une fonction rotation(liste) qui décale d’un rang tous les éléments d’une
66 LISTES I
liste (le dernier élément devenant le premier). La fonction renvoie une nouvelle liste.
Par exemple rotation([1,2,3,4]) renvoie la liste [4,1,2,3].
2. Programme une fonction inverser(liste) qui inverse l’ordre des éléments d’une liste.
Par exemple inverser([1,2,3,4]) renvoie la liste [4,3,2,1].
3. Programme une fonction supprimer_rang(liste,rang) qui renvoie une liste formée
de tous les éléments, sauf celui au rang donné.
Par exemple supprimer_rang([8,7,6,5,4],2) renvoie la liste [8,7,5,4] (l’élément
6 qui était au rang 2 est supprimé).
4. Programme une fonction supprimer_element(liste,element) renvoyant une liste
qui contient tous les éléments sauf ceux égaux à l’élément spécifié.
Par exemple supprimer_element([8,7,4,6,5,4],4) renvoie la liste [8,7,6,5]
(tous les éléments égaux à 4 ont été supprimés).
Le tri à bulles est une façon simple d’ordonner une liste, ici ce sera du plus petit au plus grand
élément. Le principe est le suivant :
• On parcourt la liste en partant du début. Dès que l’on rencontre deux éléments consécutifs
dans le mauvais ordre, on les échange.
• À la fin du premier passage, le plus grand élément est à la fin et il ne bougera plus.
• On recommence du début (jusqu’à l’avant-dernier élément), cette fois les deux derniers
éléments sont bien placés.
• On continue ainsi. Il y a en tout n − 1 passages si la liste est de taille n.
LISTES I 67
9 7 avant
7 9 après
Algorithme.
• — Entrée : une liste ` de n nombres
— Sortie : la liste ordonnée du plus petit au plus grand
• Pour i allant de n − 1 à 0 :
Pour j allant de 0 à i − 1 :
Si `[ j + 1] < `[ j] alors échanger `[ j] et `[ j + 1].
• Renvoyer la liste `.
Programme l’algorithme du tri à bulles en une fonction trier(liste) qui renvoie la liste
ordonnée des éléments. Par exemple trier([13,11,7,4,6,8,12,6]) renvoie la liste
[4,6,6,7,8,11,12,13].
Indications.
• Commence par définir nouv_liste = list(liste) et travaille uniquement avec cette
nouvelle liste.
• Pour que l’indice i parcourt les indices à rebours de n − 1 à 0, tu peux utiliser la commande :
for i in range(n-1,-1,-1):
En effet range(a,b,-1) correspond à la liste décroissante des entiers i vérifiant a > i > b
(comme d’habitude la borne de droite n’est pas incluse).
Cours 5 (Tri).
Tu peux maintenant utiliser la fonction sorted() de Python qui ordonne des listes.
python : sorted()
Usage : sorted(liste)
Entrée : une liste
Sortie : la liste ordonnée des éléments
Exemple : sorted([13,11,7,4,6,8,12,6]) renvoie la liste
[4,6,6,7,8,11,12,13].
Attention ! Il existe aussi une méthode [Link]() qui fonctionne un peu différemment.
68 LISTES I
Cette commande ne renvoie rien, mais par contre la liste liste est maintenant ordonnée. On
parle de modification sur place.
Activité 4 (Arithmétique).
Algorithme.
• — Entrée : un entier n > 2.
— Sortie : la liste des nombres premiers < n.
• Initialiser liste qui contient tous les entiers de 2 à n − 1.
• Pour d allant de 2 à n − 1 :
Pour k parcourant liste :
Si d divise k et d 6= k, alors retirer l’élément k de liste
• Renvoyer liste.
Indications.
• Pars de liste = list(range(2,n)).
• Utilise [Link](k).
Explications. Voyons comment fonctionne l’algorithme avec n = 30.
• Au départ la liste est
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
LISTES I 69
liste1 = [3,5,9,8,0,3]
liste2 = [4,7,7,2,8,9]
[Link](liste1,color="red")
[Link](liste2,color="blue")
[Link]()
[Link]()
Explications.
• Le module s’appelle [Link] et on lui donne le nouveau nom plus simple de
plt.
• Attention ! Le module matplotlib n’est pas toujours installé par défaut avec Python.
70 LISTES I
• [Link](liste) trace les points d’une liste (sous la forme (i, `i )) qui sont reliés par des
segments.
• [Link]() trace une grille.
• [Link]() affiche tout.
Pour afficher des points (x i , yi ) il faut fournir la listes des abscisses puis la listes des ordonnées :
[Link](liste_x,liste_y,color="red")
Voici un exemple de graphe obtenu en affichant des points de coordonnées du type (x, y) avec
y = x 2.
liste_x = [2, 3, 5, 7, 9]
liste_y = [4, 9, 25, 49, 81]
[Link](liste_x,liste_y,color="red")
[Link]()
[Link]()
On tire un boulet de canon depuis l’origine (0, 0). L’équation de la trajectoire est donnée par la
formule :
1 1
y(x) = − g 2 x 2 + tan(α)x
2 v cos2 (α)
où
• α est l’angle du tir,
• v est la vitesse initiale,
• g est la constante de gravitation : on prendra g = 9.81.
y(x)
v
α
(0, 0) x x
N O T I O N S AVA N C É E S
Chapitre
Statistique – Visua- 8
lisation de données
C’est bien de savoir calculer le minimum, le maximum, la moyenne, les quartiles d’une série.
C’est encore mieux de les visualiser tous sur un même graphique !
Usage : sum(liste)
Entrée : une liste de nombres
Sortie : un nombre
Exemple : sum([4,8,3]) renvoie 15
python : min()
Exemple :
• min(12,7) renvoie 7
• min([10,5,9,12]) renvoie 5
Tu peux maintenant utiliser la fonction min(), et aussi bien sûr la fonction max() dans tes
programmes !
4. La variance d’une série de données (x 1 , x 2 , . . . , x n ) est définie comme la moyenne des carrés
des écarts à la moyenne. C’est-à-dire :
1
v = (x 1 − m)2 + (x 2 − m)2 + · · · + (x n − m)2
n
où m est la moyenne de (x 1 , x 2 , . . . , x n ).
Écris une fonction variance(liste) qui calcule la variance des éléments d’une liste.
Par exemple, pour la série (6, 8, 2, 10), la moyenne est m = 6.5, la variance est
1
v = (6 − 6.5)2 + (8 − 6.5)2 + (2 − 6.5)2 + (10 − 6.5)2 = 8.75.
4
5. L’écart-type d’une série (x 1 , x 2 , . . . , x n ) est la racine carrée de la variance :
p
e= v
où v est la variance. Programme une fonction ecart_type(liste). Avec l’exemple ci-
p p
dessus on trouve e = v = 8.75 = 2.95 . . .
6. Voici les températures mensuelles moyennes à Brest et à Strasbourg.
temp_brest = [6.4,6.5,8.5,9.7,11.9,14.6,15.9,16.3,15.1,12.2,9.2,7.1]
temp_strasbourg = [0.9,2.4,6.1,9.7,13.8,17.2,19.2,18.6,15.7,10.7,5.3,2.1]
Calcule la température moyenne sur l’année à Brest puis à Strasbourg. Calcule l’écart-type
des températures à Brest puis à Strasbourg. Quelles conclusions en tires-tu ?
Le code est :
# Module tkinter
from tkinter import *
# Fenêtre tkinter
root = Tk()
# Un rectangle
canvas.create_rectangle(50,50,150,100,width=2)
# Un ovale
canvas.create_oval(50,110,180,160,width=4)
# Du texte
canvas.create_text(400,75,text="Bla bla bla bla",fill="blue")
# Ouverture de la fenêtre
[Link]()
Quelques explications :
• Le module tkinter nous permet de définir des variables root et canvas qui définissent
une fenêtre graphique (ici de largeur 800 et de hauteur 600 pixels). On décrit ensuite tout
ce que l’on veut ajouter dans la fenêtre. Et enfin la fenêtre est affichée par la commande
[Link]() (tout à la fin).
78 STATISTIQUE – VISUALISATION DE DONNÉES
• Attention ! Le repère graphique de la fenêtre a son axe des ordonnées dirigé vers le bas.
L’origine (0, 0) est le coin en haut à gauche (voir la figure ci-dessous).
• Commande pour tracer un rectangle : create_rectangle(x1,y1,x2,y2) ; il suffit de
préciser les coordonnées (x 1 , y1 ), (x 2 , y2 ) de deux sommets opposés. L’option width ajuste
l’épaisseur du trait, outline définit la couleur de ce trait, fill définit la couleur de rem-
plissage.
• Une ellipse est tracée par la commande create_oval(x1,y1,x2,y2), où (x 1 , y1 ), (x 2 , y2 )
sont les coordonnées de deux sommets opposés d’un rectangle encadrant l’ellipse voulue
(voir la figure). On obtient un cercle lorsque le rectangle correspondant est un carré !
• Du texte est affiché par la commande canvas.create_text(x,y,text="Mon texte")
en précisant les coordonnées (x, y) du point à partir duquel on souhaite afficher le texte.
(0, 0) x
(x 1 , y1 )
(x 2 , y2 )
(x 1 , y1 )
(x 2 , y2 )
y
Activité 2 (Graphiques).
extent=θ
(x 1 , y1 )
start=θ0
(x 2 , y2 )
Le code est :
from tkinter import *
from random import *
root = Tk()
canvas = Canvas(root, width=400, height=200, background="white")
[Link](fill="both", expand=True)
def action_bouton():
[Link]("all") # Efface tout
couleurs = ["red","orange","yellow","green","cyan","blue","violet"]
coul = choice(couleurs) # Couleur au hasard
canvas.create_rectangle(100,50,300,150,width=5,fill=coul)
return
bouton_couleur=Button(root,text="Afficher",width=20,command=action_bouton)
bouton_couleur.pack()
bouton_quitter=Button(root,text="Quitter",width=20,command=[Link])
bouton_quitter.pack()
[Link]()
Quelques explications :
• On crée un bouton par la commande Button. L’option text personnalise le texte qui s’affiche
sur le bouton. On ajoute le bouton créé à la fenêtre par la méthode pack.
• Le plus important est l’action associée au bouton ! C’est l’option command qui reçoit
le nom de la fonction à exécuter lorsque le bouton est cliqué. Pour notre exemple
command=action_bouton, associe au clic sur le bouton un changement de couleur.
82 STATISTIQUE – VISUALISATION DE DONNÉES
1. Écris une fonction mediane(liste) qui calcule la valeur médiane des éléments d’une liste
donnée. Par définition, la moitié des valeurs est inférieure ou égale à la médiane, l’autre
moitié est supérieure ou égale à la médiane.
Rappels. On note n la longueur de la liste et on suppose que la liste est ordonnée (du plus
petit au plus grand élément).
• Cas n impair. La médiane est la valeur de la liste au rang 2 . Exemple avec liste =
n−1
[12,12,14,15,19] :
— la longueur de la liste est n = 5 (les indices vont de 0 à 4),
— l’indice du milieu est l’indice 2,
— la médiane est la valeur liste[2], c’est donc 14.
n
• Cas n pair. La médiane est la moyenne entre la valeur de la liste au rang 2 − 1 et au
rang 2n . Exemple avec liste = [10,14,19,20] :
— la longueur de la liste est n = 4 (les indices vont de 0 à 3),
— les indices du milieu sont 1 et 2,
— la médiane est la moyenne entre liste[1] et liste[2], c’est donc 14+19 2 = 16.5.
2. Les résultats d’une classe sont collectés sous la forme suivante d’un effectif par note :
effectif_notes = [0,0,0,0,0,1,0,2,0,1,5,1,2,3,2,4,1,2,0,1,0]
Le rang i va de 0 à 20. Et la valeur au rang i indique le nombre d’élèves ayant eu la note i.
Par exemple ici, 1 élève a eu la note 5, 2 élèves ont eu la note 7,. . . , 5 élèves ont obtenus 10,
. . . Écris une fonction notes_vers_liste(effectif_notes) qui prend en entrée un
effectif de notes et renvoie la liste des notes. Pour notre exemple la fonction doit renvoyer
[5,7,7,9,10,10,10,10,10,10,...].
Déduis-en une fonction qui calcule la médiane des notes d’une classe à partir d’un effectif
par note.
3. Écris une fonction calcule_quartiles(liste) qui calcule les quartiles Q 1 , Q 2 , Q 3 des
éléments d’une liste donnée. Les quartiles répartissent les valeurs en : un quart en-dessous
de Q 1 , un quart entre Q 1 et Q 2 , un quart entre Q 2 et Q 3 , un quart au-dessus de Q 3 . Pour le
calcul, on utilisera que :
• Q 2 est simplement la médiane de la liste entière (supposée ordonnée),
• Q 1 est la médiane de la sous-liste formée de la première moitié des valeurs,
• Q 3 est la médiane de la sous-liste formée de la seconde moitié des valeurs.
STATISTIQUE – VISUALISATION DE DONNÉES 83
Pour l’implémentation, il faut une nouvelle fois discuter selon que la longueur n de la liste est
paire ou pas.
Déduis-en une fonction qui calcule les quartiles des notes d’une classe à partir d’un effectif par
note.
Un diagramme en boîte (appelé aussi boîte à moustaches) est un graphique qui représente
les principales caractéristiques d’une série statistique : minimum, maximum, médiane et quartiles.
Le schéma de principe est le suivant :
Q1 médiane Q3
minimum maximum
1. Simule le cours de la bourse de l’indice Top 40 sur 365 jours. Au jour j = 0, l’indice vaut
1000. Ensuite l’indice d’un jour est déterminé en ajoutant une valeur au hasard (positive ou
négative) à la valeur de l’indice de la veille :
indice du jour j = indice du jour ( j − 1) + valeur au hasard
.
Pour cette valeur au hasard, tu peux essayer une formule du style :
valeur = randint(-10,12)/3
84 STATISTIQUE – VISUALISATION DE DONNÉES
Écris une fonction cours_bourse(), sans paramètre, qui renvoie une liste de 365 valeurs
de l’indice Top 40 selon cette méthode.
2. Trace point par point la courbe du cours sur une année. (Pour tracer un point, tu peux
afficher un carré de taille 1 pixel.)
3. Comme la courbe du cours journalier est très chaotique, nous souhaitons la lisser afin de la
rendre plus lisible. Pour cela nous calculons des moyennes mobiles.
La moyenne mobile à 7 jours pour le jour j, est la moyenne des 7 derniers cours. Par
exemple : la moyenne mobile (à 7 jours) pour le jour j = 7 est la moyenne des cours des
jours j = 1, 2, 3, 4, 5, 6, 7. On peut changer la durée : par exemple la moyenne mobile à 30
jours est la moyenne des 30 derniers cours.
Écris une fonction moyenne_mobile(liste,duree) qui renvoie la liste de toutes les
moyennes mobiles d’une série de données, pour une durée fixée.
4. Trace point par point sur un même graphique : la courbe du cours sur une année, la courbe
de ses moyennes mobiles à 7 jours et la courbe des ses moyennes mobiles à 30 jours. Note
que plus la durée est longue plus la courbe est « lisse ». (Bien sûr la courbe des moyennes
mobiles à 30 jours ne commence qu’à partir du trentième jour.)
Chapitre
9
Fichiers
fic = open("mon_fichier.txt","w")
[Link]("Bonjour le monde\n")
ligne = "Coucou\n"
[Link](ligne)
[Link]()
Explications.
• La commande open permet d’ouvrir un fichier. Le premier argument est le nom du fichier. Le
second argument est ici "w" pour dire que l’on veut écrire dans le fichier (write en anglais).
• On ne travaille pas avec le nom du fichier, mais avec la valeur renvoyée par la fonction open.
Ici nous avons nommé fic ce fichier-objet. C’est avec cette variable fic que l’on travaille
désormais.
• On écrit maintenant dans le fichier presque comme on afficherait une phrase à l’écran.
L’instruction est [Link]() où l’argument est une chaîne de caractères.
• Pour passer à la ligne, il faut ajouter le caractère de fin de ligne "\n".
• Il est important de fermer son fichier quand on a fini d’écrire. La commande est
[Link]().
• Les données à écrire sont des chaînes, donc pour écrire un nombre, il faut d’abord le trans-
former par str(nombre).
86 FICHIERS
fic = open("mon_fichier.txt","r")
Bonjour le monde
for ligne in fic:
print(ligne)
Coucou
[Link]()
Explications.
• La commande open est cette fois appelée avec l’argument "r" (pour read), elle ouvre le
fichier en lecture.
• On travaille de nouveau avec un fichier-objet nommé ici fic.
• Une boucle parcourt tout le fichier ligne par ligne. Ici on demande juste l’affichage de chaque
ligne.
• On ferme le fichier avec [Link]().
• Les données lues sont des chaînes, donc pour obtenir un nombre, il faut d’abord le transformer
par int(chaine) (pour un entier) ou float(chaine) (pour un nombre à virgule).
Objectifs : écrire un fichier de notes, puis le lire pour calculer les moyennes.
1. Génère au hasard un fichier de notes, nommé [Link], qui est composé de lignes ayant
la structure :
Prenom Nom note1 note2 note3
Par exemple :
Indications.
• Construis un liste
de prénoms liste_prenoms =
["Tintin","Harry","Alice",...]. Puis choisis un prénom au hasard par
la commande prenom = choice(liste_prenoms) (il faut importer le module
random).
FICHIERS 87
Indications.
• Pour chaque ligne lue du fichier [Link], tu récupères les données dans une liste
par la commande [Link]().
• Attention ! Les données lues sont des chaînes de caractères. Tu peux convertir une chaîne
"12.5" en le nombre 12.5 par la commande float(chaine).
• Pour convertir un nombre en une chaîne avec seulement deux décimales après la virgule,
tu peux utiliser la commande '{0:.2f}'.format(moyenne).
• N’oublie pas de fermer tous tes fichiers.
CURIE,Marie,1867,1.55,2
EINSTEIN,Albert,1879,1.75,1
NOBEL,Alfred,1833,1.70,0
88 FICHIERS
Indications.
• Le package matplotlib permet d’afficher facilement des graphiques, il s’appelle souvent
avec l’instruction :
import [Link] as plt
• Voici comment visualiser deux listes de données liste1 et liste2 :
[Link](liste1)
[Link](liste2)
[Link]()
[Link]()
P1
4 5
1 1 1 1
1 0 0 0
1 1 1 0
1 0 0 0
1 1 1 1
P2
4 5
255
0 0 0 0
192 192 192 192
192 255 128 128
192 255 64 64
192 0 0 0
P3
3 2
255
255 0 0 0 255 0 0 0 255
0 128 255 255 128 0 128 255 0
1. Génère un fichier image_nb.pbm qui représente une image en noir et blanc (par exemple
de taille 300 × 200) selon le motif suivant :
FICHIERS 91
B = (i + j)//3 % 256
qui donne les niveaux de rouge, vert et bleu du pixel (i, j).
4. Écris une fonction inverser_couleurs_nb(fichier) qui lit un fichier image noir et
blanc .pbm et crée un nouveau fichier dans lequel les pixels blancs sont devenus noirs et
inversement.
Exemple : à gauche l’image de départ, à droite l’image d’arrivée.
Objectifs : lire les coordonnées des villes et écrire les distances entre elles.
On lit sur ce fichier que la distance entre Lille et Marseille est de 1077 kilomètres.
Ci-dessous la carte de France qui a fourni des données (très approximatives) pour le fichier
d’entrée. L’origine est en bas à gauche, chaque côté d’un carré représente 100 km. Par
exemple, dans ce repère, Paris a pour coordonnées (500, 800).
Lille
Strasbourg
Paris
Nantes
Lyon
Bordeaux
Toulouse
(0, 0) Marseille
100 km
On approfondit notre étude des nombres avec la boucle « tant que ». Pour cette fiche tu as
besoin d’une fonction est_premier() construite dans la fiche « Arithmétique – Boucle
tant que – I ».
1. La bonne conjecture de Goldbach : Tout entier pair plus grand que 4 est la somme de deux
nombres premiers.
Par exemple 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7 (mais aussi 10 = 5 + 5), 12 = 5 + 7,. . .
Pour n = 100 il y a 6 solutions : 100 = 3 + 97 = 11 + 89 = 17 + 83 = 29 + 71 = 41 + 59 =
47 + 53.
Personne ne sait démontrer cette conjecture, mais tu vas voir qu’il y a de bonnes raisons de
penser qu’elle est vraie.
(a) Programme une fonction nombre_solutions_goldbach(n) qui pour un entier pair
n donné, trouve combien il existe de décompositions n = p + q avec p et q deux nombres
premiers et p 6 q.
Par exemple pour n = 8, il n’y a qu’une seule solution 8 = 3 + 5, par contre pour n = 10
il y a deux solutions 10 = 3 + 7 et 10 = 5 + 5.
Indications.
• Il faut donc tester tous les p compris 2 et n/2 ;
• poser q = n − p ;
• on a une solution quand p 6 q et que p et q sont tous les deux des nombres premiers.
(b) Prouve avec la machine que la conjecture de Goldbach est vérifiée pour tous les entiers
n pairs compris entre 4 et 10 000.
2. La mauvaise conjecture de Goldbach : Tout entier impair n peut s’écrire sous la forme
n = p + 2k2
96 ARITHMÉTIQUE – B OUCLE TANT QUE – II
Conjecture : Entre 1 et N , il y a plus d’entiers qui ont exactement 4 diviseurs que d’entiers qui ont
exactement 8 diviseurs.
Tu vas voir que cette conjecture a l’air vrai pour N assez petit, mais tu vas montrer que cette
conjecture est fausse en trouvant un N grand qui contredit cet énoncé.
1. Nombre de diviseurs.
Programme une fonction nombre_de_diviseurs(n) qui renvoie le nombre d’entiers
divisant n.
Par exemple : nombre_de_diviseurs(100) renvoie 9 car il y a 9 diviseurs de n = 100 :
1, 2, 4, 5, 10, 20, 25, 50, 100
Indications.
• N’oublie pas 1 et n comme diviseurs.
• Essaie d’optimiser ta fonction car tu l’utiliseras intensivement : par exemple il n’y a pas
de diviseurs strictement plus grands que 2n (à part n).
2. 4 ou 8 diviseurs.
Programme une fonction quatre_et_huit_diviseurs(Nmin,Nmax) qui renvoie deux
nombres : (1) le nombre d’entiers n avec Nmin 6 n < Nmax qui admettent exactement 4
diviseurs et (2) le nombre d’entiers n avec Nmin 6 n < Nmax qui admettent exactement 8
diviseurs.
Par exemple quatre_et_huit_diviseurs(1,100) renvoie (32, 10) car il y a 32 en-
tiers entre 1 et 99 qui admettent 4 diviseurs, mais seulement 10 entiers qui en admettent
8.
3. Preuve que la conjecture est fausse.
Expérimente que pour des « petites » valeurs de N (jusqu’à N = 10 000 par exemple) il y a
plus d’entiers ayant 4 diviseurs que 8. Mais calcule que pour N = 300 000 ce n’est plus le
cas.
Indications. Comme il y a beaucoup de calculs, tu peux les séparer en tranches (la tranche
des entiers 1 6 n < 50 000, puis 50 000 6 n < 100 000,...) puis fais la somme. Tu peux ainsi
partager tes calculs entre plusieurs ordinateurs.
ARITHMÉTIQUE – B OUCLE TANT QUE – II 97
On appelle Uk l’entier :
Uk = 1 2 1
| 1 1 .{z
.. 111
}
k occurrences de 1
formé du chiffre 1, puis du chiffre 2, puis de k fois le chiffre 1.
Par exemple U0 = 12, U1 = 121, U2 = 1211,. . .
1. Écris une fonction un_deux_un(k) qui renvoie l’entier Uk .
Indications. Tu peux remarquer qu’en partant de U0 = 12, on a la relation Uk+1 = 10 · Uk + 1.
Donc tu peux partir de u = 12 et répéter un certain nombre de fois u = 10*u + 1.
2. Vérifie à l’aide de la machine que U0 , . . . , U20 ne sont pas des nombres premiers.
On pourrait croire que c’est toujours le cas, mais ce n’est pas vrai ! L’entier U136 est un nombre
premier ! Malheureusement il est trop grand pour qu’on puisse le vérifier avec nos algorithmes.
Dans la suite on va définir ce qu’est un nombre presque premier pour pouvoir pousser plus
loin les calculs.
3. Programme une fonction est_presque_premier(n,r) qui renvoie « vrai » si l’entier n
n’admet aucun diviseur d tel que 1 < d 6 r (on suppose r < n).
Par exemple : n = 143 = 11 × 13 et r = 10, alors est_presque_premier(n,r) est « vrai »
car n n’admet aucun diviseur inférieur ou égal à 10. (Mais bien sûr, n n’est pas un nombre
premier.)
Indications. Modifie ta fonction est_premier(n) !
4. Trouve tous les entiers Uk avec 0 6 k 6 150 qui sont presque premiers pour r = 1 000 000
(c’est-à-dire qu’ils ne sont divisibles par aucun entier d avec 1 < d 6 1 000 000).
Indications. Dans la liste tu dois retrouver U136 (qui est un nombre premier) mais aussi U34
qui n’est pas premier mais dont le plus petit diviseur est 10 149 217 781.
Soit n > 0 un entier. La racine carrée entière de n est le plus grand entier r > 0 tel que r 2 6 n.
p
Une autre définition est de dire que la racine carrée entière de n est la partie entière de n.
Exemples :
• pn = 21, alors la racine carrée entière de n est 4 (car 42 6 21, mais 52 > 21). Autre façon,
21 = 4.58 . . ., on ne retient que la partie entière (l’entier à gauche de la virgule), c’est
donc 4.
• pn = 36, alors la racine carrée entière de n est 6 (car 62 6 36, mais 72 > 36). Autre façon,
36 = 6 et la racine carrée entière est bien sûr aussi 6.
98 ARITHMÉTIQUE – B OUCLE TANT QUE – II
1. Écris une première fonction qui calcule la racine carrée entière d’un entier n, en calculant
p
d’abord n, puis en prenant la partie entière.
Indications.
• Pour cette question uniquement, tu peux utiliser le module math de Python.
• Dans ce module sqrt() renvoie la racine carrée réelle.
• La fonction floor() du même module renvoie la partie entière d’un nombre.
2. Écris une deuxième fonction qui calcule la racine carrée entière d’un entier n, mais cette
fois selon la méthode suivante :
• Pars de p = 0.
• Tant que p2 6 n, incrémente la valeur de p.
Teste bien quelle doit être la valeur renvoyée (attention au décalage !).
3. Écris une troisième fonction qui calcule encore la racine carrée entière d’un entier n avec
l’algorithme décrit ci-dessous. Cet algorithme s’appelle la méthode babylonienne ou bien
méthode de Héron ou bien encore méthode de Newton !
Algorithme.
Entrée : un entier positif n
Sortie : sa racine carrée entière
• Partir avec a = 1 et b = n.
• Tant que |a − b| > 1 :
— a ← (a + b)//2 ;
— b ← n//a
• Renvoyer le minimum entre a et b : c’est la racine carrée entière de n.
Nous n’expliquons pas comment fonctionne cet algorithme, mais il faut savoir que c’est
l’une des méthodes les plus efficaces pour calculer les racines carrées. Les nombres a et b
p
fournissent, au cours de l’exécution, un encadrement de plus en plus précis de n.
Voici un tableau qui détaille un exemple de calcul pour la racine carrée entière de n = 1664.
Étape a b
i=0 a=1 b = 1664
i=1 a = 832 b=2
i=2 a = 417 b=3
i=3 a = 210 b=7
i=4 a = 108 b = 15
i=5 a = 61 b = 27
i=6 a = 44 b = 37
i=7 a = 40 b = 41
À la dernière étape, l’écart entre a et b est inférieur ou égal à 1, donc la racine carrée entière
est 40. On peut vérifier que c’est exact car : 402 = 1600 6 1664 < 412 = 1681.
ARITHMÉTIQUE – B OUCLE TANT QUE – II 99
Bonus. Compare les vitesses d’exécution des trois méthodes à l’aide de timeit(). Voir la fiche
« Fonctions ».
Exemple.
Voici différents codes pour un compte à rebours de 10 à 0.
# Compte à rebours # Mieux (avec un drapeau)
n = 10 n = 10
# Encore mieux
# Boucle infinie termine = False
n = 10
while True: while not termine:
while n >= 0:
print(n) print(n)
print(n)
n = n - 1 n = n - 1
n = n - 1
if n < 0: if n < 0:
break # Arrêt termine = True
Exemple.
Voici des programmes qui cherchent la racine carrée entière de 777, c’est-à-dire le plus grand
entier i qui vérifie i 2 6 777. Dans le script de gauche, la recherche est limitée aux entiers i
entre 0 et 99.
# Racine carrée entière # Mieux
n = 777 n = 777
for i in range(100): i = 0
if i**2 > n: while i**2 <= n:
break i = i + 1
print(i-1) print(i-1)
100 ARITHMÉTIQUE – B OUCLE TANT QUE – II
Exemple.
Voici des programmes qui calculent les racines carrés réelles des éléments d’une liste, sauf
bien sûr si le nombre est négatif. Le code de gauche s’arrête avant la fin de la liste, alors que
le code de droite gère proprement le problème.
# Racines carrées des éléments # Mieux avec try/except
# d'une liste liste = [3,7,0,10,-1,12]
liste = [3,7,0,10,-1,12] for element in liste:
for element in liste: try:
if element < 0: print(sqrt(element))
break except:
print(sqrt(element)) print("Problème avec",element)
Chapitre
11
Binaire I
Les ordinateurs transforment toutes les données en nombres et manipulent uniquement ces
nombres. Ces nombres sont stockés sous la forme de listes de 0 et de 1. C’est l’écriture binaire
des nombres ! Pour mieux comprendre l’écriture binaire, tu vas d’abord mieux comprendre
l’écriture décimale.
decimale_vers_entier()
Usage : decimale_vers_entier(liste_decimale)
Entrée : une liste de chiffres entre 0 et 9
Sortie : l’entier dont l’écriture décimale est la liste
Cours 2 (Binaire).
• Puissances de 2. On note 2k pour 2 × 2 × · · · × 2 (avec k facteurs). Par exemple, 23 =
2 × 2 × 2 = 8.
27 26 25 24 23 22 21 20
128 64 32 16 8 4 2 1
Objectifs : à partir de l’écriture binaire, retrouver l’entier (en écriture décimale usuelle).
1. Calcule les entiers dont l’écriture binaire est donnée ci-dessous. Tu peux le faire à la main
ou t’aider de Python. Par exemple [Link].1 vaut 24 + 21 + 20 = 19 ce que confirme la
commande 0b10011 qui renvoie 19.
• 1.1, 1.0.1, [Link], [Link]
• [Link].0, [Link].1, [Link].1
• [Link].0.0, [Link].1.1
• [Link].[Link]
2. Écris une fonction binaire_vers_entier(liste_binaire) qui à partir d’une liste
représentant l’écriture binaire calcule l’entier correspondant.
binaire_vers_entier()
Usage : binaire_vers_entier(liste_binaire)
Entrée : une liste de bits 0 et 1
Sortie : l’entier dont l’écriture binaire est la liste
Exemples :
• entrée [1,1,0], sortie 6
• entrée [1,1,0,1,1,1], sortie 55
• entrée [1,1,0,1,0,0,1,1,0,1,1,1], sortie 3383
Algorithme.
Entrée : liste : une liste de 0 et de 1
Sortie : le nombre binaire associé
• Initialiser une variable n à 0.
• Pour chaque élément b de liste :
— si b vaut 0, alors faire n ← 2n,
— si b vaut 1, alors faire n ← 2n + 1.
• Le résultat est la valeur de n.
1234 10
4 123
reste quotient
entier_vers_decimale()
Usage : entier_vers_decimale(n)
Entrée : un entier positif
Sortie : la liste de ses chiffres
Exemple : si l’entrée est 1234, la sortie est [1,2,3,4].
Algorithme.
Entrée : un entier n > 0
Sortie : la liste de ses chiffres
• Partir d’une liste vide.
• Tant que n n’est pas nul :
— ajouter n%10 au début de la liste,
— faire n ← n//10.
• Le résultat est la liste.
python : bin()
Usage : bin(n)
Entrée : un entier
Sortie : l’écriture binaire de n sous la forme d’une chaîne de caractères
commençant par '0b'
Exemple :
• bin(37) renvoie '0b100101'
• bin(139) renvoie '0b10001011'
Exemple.
Calcul de l’écriture binaire de 14.
• On divise 14 par 2, le quotient est 7, le reste est 0.
• On divise 7 (le quotient précédent) par 2 : le nouveau quotient est 3, le nouveau reste est
1.
• On divise 3 par 2 : quotient 1, reste 1.
• On divise 1 par 2 : quotient 0, reste 1.
• C’est terminé (le dernier quotient est nul).
• Les restes successifs sont 0, 1, 1, 1. On lit l’écriture binaire à l’envers c’est [Link].
Les divisions se font de gauche à droite, mais on lit les restes de droite à gauche.
14 2 7 2 3 2 1 2
0 7 1 3 1 1 1 0
Exemple.
Écriture binaire de 50.
50 2 25 2 12 2 6 2 3 2 1 2
0 25 1 12 0 6 0 3 1 1 1 0
Activité 4.
1. Calcule à la main l’écriture binaire des entiers suivants. Vérifie tes résultats à l’aide de la
fonction bin() de Python.
• 13, 18, 29, 31,
• 44, 48, 63, 64,
• 100, 135, 239, 1023.
2. Programme l’algorithme suivant en une fonction entier_vers_binaire().
Algorithme.
Entrée : un entier n > 0
Sortie : son écriture binaire sous la forme d’une liste
• Partir d’une liste vide.
• Tant que n n’est pas nul :
— ajouter n%2 au début de la liste,
— faire n ← n//2.
• Le résultat est la liste.
entier_vers_binaire()
Usage : entier_vers_binaire(n)
Entrée : un entier positif
Sortie : son écriture binaire sous forme d’une liste
12
Listes II
Les listes sont tellement utiles qu’il faut savoir les manipuler de façon simple et efficace. C’est
le but de cette fiche !
{0, 2, 4, 6, 8, 10}. Une autre façon est de dire que les éléments de l’ensemble doivent vérifier
une certaine propriété. Par exemple le même ensemble E peut se définir par :
E = {x ∈ N | x 6 10 et x est pair}.
Avec Python il existe un tel moyen de définir des listes. C’est une syntaxe extrêmement
puissante et efficace. Voyons des exemples :
— Partons d’une liste, par exemple maliste = [1,2,3,4,5,6,7,6,5,4,3,2,1].
— La commande liste_doubles = [ 2*x for x in maliste ] renvoie une liste
qui contient les doubles des éléments de la liste maliste. C’est donc la liste
[2,4,6,8,...].
— La commande liste_carres = [ x**2 for x in maliste ] renvoie la liste des
carrés des éléments de la liste initiale. C’est donc la liste [1,4,9,16,...].
— La commande liste_partielle = [x for x in maliste if x > 2] extrait la
liste composée des seuls éléments strictement supérieurs à 2. C’est donc la liste
[3,4,5,6,7,6,5,4,3].
• Liste de listes.
Une liste peut contenir d’autres listes, par exemple :
maliste = [ ["Harry", "Hermione", "Ron"], [101,103] ]
contient deux listes. Nous allons nous intéresser à des listes qui contiennent des listes d’entiers,
que nous appellerons des tableaux. Par exemple :
tableau = [ [2,14,5], [3,5,7], [15,19,4], [8,6,5] ]
Alors tableau[i] renvoie la sous-liste de rang i, alors que tableau[i][j] renvoie l’entier
situé au rang j dans la sous-liste de rang i. Par exemple :
— tableau[0] renvoie la liste [2,14,5],
— tableau[1] renvoie la liste [3,5,7],
— tableau[0][0] renvoie l’entier 2,
— tableau[0][1] renvoie l’entier 14,
— tableau[2][1] renvoie l’entier 19.
4. Programme une fonction non_zero(liste) qui renvoie la liste de tous les éléments non
nuls. Par exemple non_zero([1,0,2,3,0,4,5,0]) renvoie [1,2,3,4,5].
5. Programme une fonction pairs(liste) qui renvoie la liste de tous les éléments pairs. Par
exemple pairs([1,0,2,3,0,4,5,0]) renvoie [0,2,0,4,0].
On considère une liste de n entiers compris entre 1 et 99 (inclus). Par exemple la liste de n = 20
entiers :
[16,2,85,27,9,45,98,73,12,26,46,25,26,49,18,99,10,86,7,42]
qui a été obtenue au hasard par la commande :
liste_20 = [randint(1,99) for i in range(20)]
On cherche différentes manières de trouver des nombres de la liste dont la somme fait exactement
100.
1. Programme une fonction somme_deux_consecutifs_100(liste) qui teste s’il existe
deux éléments consécutifs de la liste dont la somme vaut 100. La fonction renvoie « vrai »
ou « faux » (mais elle peut aussi afficher les nombres et leur position pour vérification). Pour
l’exemple donné la fonction renvoie False.
2. Programme une fonction somme_deux_100(liste) qui teste s’il existe deux éléments de
la liste, situés à des positions différentes, dont la somme vaut 100. Pour l’exemple donné la
fonction renvoie True et peut afficher les entiers 2 et 98 (aux rangs 1 et 6 de la liste).
3. Programme une fonction somme_suite_100(liste) qui teste s’il existe des éléments
consécutifs de la liste dont la somme vaut 100. Pour l’exemple donné la fonction renvoie
True et peut afficher les entiers à suivre 25, 26, 49 (aux rangs 11, 12 et13).
4. (Facultatif.) Plus la taille de la liste est grande plus il y a de chances d’obtenir des entiers
dont la somme vaut 100. Pour chacune des trois situations précédentes, détermine à partir
de quelle taille n de la liste, la probabilité d’obtenir une somme de 100 est plus grande que
1/2.
Indications. Pour chaque cas, tu obtiens une estimation de cet entier n, en écrivant une
fonction proba(n,N) qui effectue un grand nombre N de tirages aléatoires de listes à n
éléments (avec par exemple N = 10 000). La probabilité est approchée par le nombre de
cas favorables (où la fonction renvoie vraie) divisé par le nombre total de cas (ici N ).
Activité 3 (Tableau).
Dans cette activité nous travaillons avec des tableaux carrés de taille n × n contenant des entiers.
112 LISTES II
L’élément tableau est donc une liste de n listes ayant chacune n éléments.
Par exemple (avec n = 3) :
tableau = [ [1,2,3], [4,5,6], [7,8,9] ]
représente le tableau :
1 2 3
4 5 6
7 8 9
1. Écris une fonction somme_diagonale(tableau) qui calcule la somme des éléments situés
sur la diagonale principale. La diagonale principale de l’exemple donné est constituée de 1,
5, 9, la somme vaut donc 15.
2. Écris une fonction somme_anti_diagonale(tableau) qui calcule la somme des élé-
ments situés sur l’autre diagonale. L’anti-diagonale de l’exemple donné est constituée de 3,
5, 7, la somme vaut encore 15.
3. Écris une fonction somme_tout(tableau) qui calcule la somme totale de tous les éléments.
Pour l’exemple la somme totale vaut 45.
4. Écris une fonction affiche_tableau(tableau) qui affiche proprement à l’écran un
tableau. Tu peux utiliser la commande :
print('{:>3d}'.format(tableau[i][j]), end="")
Explications.
• La commande print(chaine,end="") permet d’afficher une chaîne de caractères
sans passer à la ligne.
• La commande '{:>3d}'.format(k) affiche l’entier k sur trois cases (même s’il n’y a
qu’un chiffre à afficher).
Un carré magique est un tableau carré de taille n × n qui contient tous les entiers de 1 à n2
et qui vérifie que : la somme de chaque ligne, la somme de chaque colonne, la somme de la
diagonale principale et la somme de l’anti-diagonale ont toutes la même valeur.
Voici un exemple de carré magique de taille 3 × 3 et un de taille 4 × 4.
LISTES II 113
1 14 15 4 34
4 9 2 15
7 9 6 12 34
3 5 7 15
10 8 11 5 34
8 1 6 15
16 3 2 13 34
15 15
15 15 15 34 34
34 34 34 34
Algorithme.
• — Entrées : un carré magique C1 de taille n × n et un carré magique C2 de taille
m × m.
— Sortie : un carré magique C de taille (nm) × (nm).
• Définis le carré C3a en retirant 1 à tous les éléments de C2 . (Utilise la commande
addition_carre(carre2,-1).)
• Définis le carré C3b comme l’homothétie du carré C3a de rapport n. (Utilise la com-
mande homothetie(carre3a,n).)
• Définis le carré C3c en multipliant tous les termes du carré C3b par n2 . (Utilise la
commande multiplication_carre(carre3b,n**2).)
• Définis le carré C3d en ajoutant par bloc le carré C1 au carré C3c . (Utilise la commande
addition_bloc_carre(carre3c,carre1).)
• Renvoie le carré C3d .
13
Binaire II
Activité 1 (Palindromes).
Objectifs : trouver des palindromes en écriture binaire et en écriture décimale.
En français un palindrome est un mot (ou une phrase) qui se lit dans les deux sens, par exemple
« RADAR » ou « ENGAGE LE JEU QUE JE LE GAGNE ». Dans cette activité, un palindrome
sera une liste, qui a les mêmes éléments lorsqu’on la parcourt de gauche à droite ou de droite à
gauche.
Exemples :
• [1,0,1,0,1] est un palindrome (avec une écriture binaire),
• [2,9,4,4,9,2] est un palindrome (avec une écriture décimale).
1. Programme une fonction est_palindrome(liste) qui teste si une liste est un palindrome
ou pas.
Indications. Tu peux comparer les éléments en position i et p − 1 − i ou bien utiliser
list(reversed(liste)).
2. On cherche des entiers n tels que leur écriture binaire soit un palindrome. Par exemple
l’écriture binaire de n = 27 est le palindrome [1,1,0,1,1]. C’est le dixième entier n ayant
cette propriété.
Quel est le millième entier n > 0 dont l’écriture binaire est un palindrome ?
3. Quel est le millième entier n > 0 dont l’écriture décimale est un palindrome ?
Par exemple les décimales de n = 909 forment le palindrome [9,0,9]. C’est le centième
entier n ayant cette propriété.
4. Un entier n est un bi-palindrome si son écriture binaire et son écriture décimales sont
des palindromes. Par exemple n = 585 a une écriture décimale qui est un palindrome et
son écriture binaire [1,0,0,1,0,0,1,0,0,1] aussi. C’est le dixième entier n ayant cette
propriété.
Quel est le vingtième entier n > 0 a être un bi-palindrome ?
118 BINAIRE II
1. (a) Programme une fonction NON() qui correspond à la négation pour une liste donnée. Par
exemple NON([1,1,0,1]) renvoie [0,0,1,0].
(b) Programme une fonction OUeg() qui correspond au « OU » avec en entrée deux listes qui
ont la même longueur. Par exemple, avec liste1 = [1,0,1,0,1,0,1] et liste2
= [1,0,0,1,0,0,1], la fonction renvoie [1,0,1,1,1,0,1].
(c) Même travail avec ETeg() pour deux listes de longueurs égales.
2. Écris une fonction ajouter_zeros(liste,p) qui rajoute des zéros au début de la liste
afin d’obtenir un liste de longueur p. Exemple : si liste = [1,0,1,1] et p = 8, alors la
BINAIRE II 119
Objectifs : générer toutes les listes possibles de 0 et 1 afin de vérifier une proposition.
Algorithme.
Usage : tous_les_binaires(p)
Entrée : un entier p > 0
Sortie : la liste de toutes les listes possibles de 0 et de 1 de longueur p
• Si p = 1 renvoyer la liste [ [0], [1] ].
• Si p > 2, alors :
— obtenir toutes les listes de taille p-1 par l’appel tous_les_binaires(p-1)
— pour chaque élément de cette liste, construire deux nouveaux éléments :
— d’une part ajouter 0 en début de cet élément ;
— d’autre part ajouter 1 en début de cet élément ;
— ajouter ensuite ces deux éléments à la liste des listes de taille p.
• Renvoyer la liste des listes de taille p.
PROJETS
Chapitre
Probabilités – Para- 14
doxe de Parrondo
Tu vas programmer deux jeux simples. Lorsque tu joues à ces jeux, tu as plus de chances de
perdre que de gagner. Pourtant lorsque tu joues aux deux jeux en même temps, tu as plus de
chances de gagner que de perdre ! C’est une situation paradoxale.
— Si la pièce est truquée afin que le joueur perde tout le temps, alors au bout de N tirages,
son gain est de −N euros. L’espérance est donc −N N = −1.
— Un espérance de −0.5 signifie qu’en moyenne le joueur perd 0.5 euro par tirage. C’est
possible avec une pièce déséquilibrée qui fait gagner dans un cas sur quatre seulement.
(Vérifie le calcul !) Si le joueur joue 1000 fois, on peut estimer qu’il va perdre 500 euros
(−0.5 × 1000 = −500).
Objectifs : modéliser un premier jeu simple, qui en moyenne est perdant pour le joueur.
Jeu A. Dans ce premier jeu, on lance une pièce de monnaie légèrement déséquilibrée : le joueur
gagne un euro dans 49 cas sur 100 ; il perd un euro dans 51 cas sur 100.
1. Tirage. Écris une fonction tirage_jeu_A() qui ne dépend d’aucun argument et qui
modélise un tirage du jeu A. Pour cela :
• Tire un nombre au hasard 0 6 x < 1 à l’aide de la fonction random() du module
random.
• Renvoie +1 si x est plus petit que 0.49 ; et −1 sinon.
2. Gain. Écris une fonction gain_jeu_A(N) qui modélise N tirages du jeu A et renvoie le
gain total de ces tirages. Bien sûr, le résultat dépend des tirages, il peut varier d’une fois sur
l’autre.
3. Espérance. Écris une fonction esperance_jeu_A(N) qui renvoie une estimation de l’es-
pérance du jeu A selon la formule :
gain après N tirages
espérance ' , avec N grand.
N
4. Conclusion.
(a) Estime l’espérance en effectuant au moins un million de tirages.
(b) Que signifie le fait que l’espérance soit négative ?
(c) Déduis de la valeur de l’espérance, le gain (ou la perte) que je peux espérer en jouant
1000 fois au jeu A.
• Sous-jeu B2. Si le gain g n’est pas un multiple de 3, alors il lance un pièce avantageuse : le
joueur gagne un euro dans 74 cas sur 100 (il perd donc un euro dans 26 cas sur 100).
1. Tirage. Écris une fonction tirage_jeu_B(g) qui dépend du gain déjà acquis et modélise
un tirage du jeu B. Tu peux utiliser le test g%3 == 0 pour savoir si g est multiple de 3.
2. Gain. Écris une fonction gain_jeu_B(N) qui modélise N tirages du jeu B (en partant d’un
gain initial nul) et renvoie le gain total de ces tirages.
3. Espérance. Écris une fonction esperance_jeu_B(N) qui renvoie une estimation de l’es-
pérance du jeu B.
4. Conclusion.
(a) Estime l’espérance en effectuant au moins un million de tirages.
(b) Combien puis-je espérer gagner ou perdre en jouant 1000 fois au jeu B ?
Référence : « Paradoxe de Parrondo », Hélène Davaux, La gazette des mathématiciens, juillet 2017.
Chapitre
Chercher et remplacer
15
Chercher et remplacer sont deux tâches très fréquentes. Savoir les utiliser et comprendre
comment elles fonctionnent te permettra d’être plus efficace.
Activité 1 (Chercher).
1. L’opérateur « in ».
La façon la plus simple de savoir si une sous-chaîne est présente dans une chaîne de caractères
est d’utiliser l’opérateur « in ». Par exemple, l’expression :
"PAS" in "ETRE OU NE PAS ETRE"
vaut « vrai » car la sous-chaîne PAS est bien présente dans la phrase ETRE OU NE PAS ETRE.
Déduis-en une fonction chercher_in(chaine,sous_chaine) qui renvoie « vrai » ou
« faux », selon que la sous-chaîne est (ou non) présente dans la chaîne.
2. La méthode find().
La méthode find() s’utilise sous la forme [Link](sous_chaine) et renvoie la
position à laquelle la sous-chaîne a été trouvée.
Teste ceci sur l’exemple précédent. Que renvoie la fonction si la sous-chaîne n’est pas
trouvée ?
3. La méthode index().
La méthode index() a la même utilité, elle s’utilise sous la forme
[Link](sous_chaine) et renvoie la position à laquelle la sous-chaîne a
été trouvée.
Teste ceci sur l’exemple précédent. Que renvoie la fonction si la sous-chaîne n’est pas
trouvée ?
4. Ta fonction chercher().
Écris ta propre fonction chercher(chaine,sous_chaine) qui renvoie la position de
départ de la sous-chaîne si elle est trouvée (et renvoie None si elle ne l’est pas).
128 CHERCHER ET REMPLACER
Tu n’as pas le droit d’utiliser les fonctions Python, tu as seulement droit de tester si deux
caractères sont égaux !
Activité 2 (Remplacer).
def python_regex_chercher(chaine,exp):
trouve = search(exp,chaine)
if trouve:
return [Link](), [Link](), [Link]()
else:
return None
Programme-la et teste-la. Elle renvoie : (1) la sous-chaîne trouvée, (2) la position de début et
(3) la position de fin.
Usage : search(exp,chaine)
ou python_regex_chercher(chaine,exp)
Entrée : une chaîne de caractères chaine et une expression ration-
nelle exp
Sortie : le résultat de la recherche (la sous-chaîne trouvée, sa position
de début, celle de fin)
Exemple avec chaine = "ETRE OU NE PAS ETRE"
• avec exp = "P.S", alors python_regex_chercher(chaine,
exp) renvoie ('PAS', 11, 14).
• avec exp = "E..E", la fonction renvoie ('ETRE', 0, 4).
• avec exp = "[OT]U", la fonction renvoie ('OU', 5, 7).
• avec exp = "[MN]..P[AI]S", la fonction renvoie ('NE
PAS', 8, 14).
Exemple.
Appliquer la transformation 01 → 10 à la phrase 10110.
On lit la phrase de gauche à droite, on trouve le premier motif 01 à partir de la seconde lettre,
on le remplace par 10 :
1(01)10 7−→ 1(10)10
On peut recommencer à partir du début de la phrase obtenue, avec toujours la même trans-
formation 01 → 10 :
11(01)0 7−→ 11(10)0
Le motif 01 n’apparaît plus dans la phrase 11100 donc la transformation 01 → 10 laisse
maintenant cette phrase inchangée.
Résumons : voici l’effet de la transformation itérée 01 → 10 à la phrase 10110 :
10110 7−→ 11010 7−→ 11100
Exemple.
Appliquer la transformation 001 → 1100 à la phrase 0011.
Une première fois :
(001)1 7−→ (1100)1
Une seconde fois :
11(001) 7−→ 11(1100)
Et ensuite la transformation ne modifie plus la phrase.
Exemple.
Voyons un dernier exemple avec la transformation 01 → 1100 pour la phrase de départ
0001 :
0001 7−→ 001100 7−→ 01100100 7−→ 1100100100 7−→ · · ·
On peut itérer la transformation, pour obtenir des phrases de plus en plus longues.
1. Une itération.
En utilisant ta fonction remplacer() de l’activité 1, vérifie les exemples précédents. Vérifie
bien que tu ne remplaces qu’un motif à chaque étape (celui le plus à gauche).
Exemple : la transformation 01 → 10 appliquée à la phrase 101, se calcule par
remplacer("101","01","10") et renvoie "110".
2. Plusieurs itérations.
Programme une fonction iterations(phrase,motif,nouv_motif) qui, à partir d’une
phrase, itère la transformation. Une fois que la phrase est stabilisée, la fonction renvoie le
nombre d’itérations effectuées ainsi que la phrase obtenue. Si le nombre d’itérations n’a pas
l’air de s’arrêter (par exemple quand il dépasse 1000) alors renvoie None.
Exemple. Pour la transformation 0011 → 1100 et la phrase 000011011, les phrases obte-
nues sont :
000011011 7−→ 001100011 7−→ 110000011 7−→ 110001100 7−→ 110110000 7−→ idem
1 2 3 4
Pour cet exemple l’appel à la fonction iterations() renvoie alors 4 (le nombre de trans-
formations avant stabilisation) et "110110000" (la phrase stabilisée).
3. Le plus d’itérations possibles.
Programme une fonction iteration_maximale(p,motif,nouv_motif) qui, parmi
toutes les phrases de longueur p, cherche l’une de celles qui met le plus de temps à se
stabiliser. Cette fonction renvoie :
• le nombre maximum d’itérations,
• la première phrase qui réalise ce maximum,
• la phrase stabilisée correspondante.
Exemple : pour la transformation 01 → 100, parmi toutes les phrases de longueur
p = 4, le maximum d’itérations possibles est 7. Un tel exemple de phrase est 0111,
qui va se stabiliser (après 7 itérations donc) en 11100000000. Ainsi la commande
iteration_maximale(4,"01","100") renvoie :
7, '0111', '11100000000'
Indication. Pour générer toutes les phrases de longueur p formées de 0 et 1, tu peux consulter
la fiche « Binaire II » (activité 3).
4. Catégories de transformations.
• Transformation linéaire. Vérifie expérimentalement que la transformation 0011 →
110 est linéaire, c’est-à-dire que pour toutes les phrases de longueur p, il y aura au plus
de l’ordre de p itérations au maximum. Par exemple pour p = 10, quel est le nombre
maximum d’itérations ?
• Transformation quadratique. Vérifie expérimentalement que la transformation 01 →
10 est quadratique, c’est-à-dire que pour toutes les phrases de longueur p, il y aura au
plus de l’ordre de p2 itérations au maximum. Par exemple pour p = 10, quel est le
nombre maximum d’itérations ?
132 CHERCHER ET REMPLACER
Tu vas programmer ta propre calculatrice ! Pour cela tu vas découvrir une nouvelle notation
pour les formules et aussi découvrir ce qu’est une « pile » en informatique.
Cours 1 (Pile).
Une pile est une suite de données munie de trois opérations de base :
• empiler : on ajoute un élément au sommet de la pile,
• dépiler : on lit la valeur de l’élément au sommet de la pile et on retire cet élément de la pile,
• et enfin, on peut tester si la pile est vide.
"Car"
Sommet de la pile
"Ni"
"Or"
6 "Donc"
11 "Et"
3 "Ou"
7 "Mais"
b
depile()
J empile(J) renvoie la valeur (ici "b")
J b
A A k k
Z Z s s
U Empiler U x Dépiler x
Remarques.
• Analogie. Tu peux faire le lien avec une pile d’assiettes. On peut déposer, une à une, des
assiettes sur une pile. On peut retirer, une à une, les assiettes en commençant bien sûr par
134 CALCULATRICE POLONAISE – PILES
celle du haut. En plus, il faut considérer que sur chaque assiette est dessinée une donnée
(un nombre, un caractère, une chaîne. . . ).
• Dernier entré, premier sorti. Dans une file d’attente, le premier qui attend, est le premier
qui est servi et ressort. Ici c’est le contraire ! Une pile fonctionne selon le principe « dernier
entré, premier sorti ».
• Dans une liste, on peut accéder directement à n’importe quel élément ; dans une pile on
n’accède directement qu’à l’élément au sommet de la pile. Pour accéder aux autres éléments,
il faut dépiler plusieurs fois.
• L’avantage d’une pile est que c’est une structure de données très simple qui correspond bien
à ce qui se passe dans la mémoire d’un ordinateur.
def sur_la_lune():
global gravitation # Oui, je veux modifier cette variable globale!
gravitation = 1.625 # Nouvelle valeur pour tout le programme
...
La pile sera stockée dans une variable globale pile. Il faut commencer chaque fonction qui
modifie la pile par la commande :
global pile
1. Écris une fonction empile() qui ajoute un élément au sommet de la pile.
empile()
Usage : empile(element)
Entrée : un entier, une chaîne. . .
Sortie : rien
Action : la pile contient un élément en plus
Exemple : si au départ pile = [5,1,3] alors, après l’instruction
empile(8), la pile vaut [5,1,3,8] et si on continue avec l’instruc-
tion empile(6), la pile vaut maintenant [5,1,3,8,6].
2. Écris une fonction depile(), sans paramètre, qui retire l’élément au sommet de la pile et
renvoie sa valeur.
depile()
Usage : depile()
Entrée : rien
Sortie : l’élément du sommet de la pile
Action : la pile contient un élément de moins
3. Écris une fonction pile_est_vide(), sans paramètre, qui teste si la pile est vide ou non.
136 CALCULATRICE POLONAISE – PILES
pile_est_vide()
Usage : pile_est_vide()
Entrée : rien
Sortie : vrai ou faux
Action : ne fait rien sur la pile
Exemple :
• si pile = [13,4,9] alors l’instruction pile_est_vide()
renvoie False,
• si pile = [] alors l’instruction pile_est_vide() renvoie
True.
python : split()
Usage : [Link](separateur)
Entrée : une chaîne de caractères chaine et éventuellement un sé-
parateur separateur
Sortie : une liste de chaînes de caractères
Exemple :
• "Etre ou ne pas etre.".split() renvoie ['Etre',
'ou', 'ne', 'pas', 'etre.']
• "12.5;17.5;18".split(";") renvoie ['12.5',
'17.5', '18']
2. La fonction join() est une méthode Python qui recolle une liste de chaînes en une seule
chaîne. C’est l’opération inverse de split().
python : join()
Usage : [Link](liste)
Entrée : une liste de chaînes de caractères liste et un séparateur
separateur
Sortie : une chaîne de caractères
Exemple :
• "".join(["Etre", "ou", "ne", "pas", "etre."])
renvoie 'Etreounepasetre.' Il manque les espaces.
• " ".join(["Etre", "ou", "ne", "pas", "etre."])
renvoie 'Etre ou ne pas etre.' C’est mieux lorsque le
séparateur est une espace.
• "--".join(["Etre", "ou", "ne", "pas", "etre."])
renvoie 'Etre--ou--ne--pas--etre.'
3. La fonction isdigit() est une méthode Python qui teste si une chaîne de caractères ne
contient que des chiffres. Cela permet donc de tester si une chaîne correspond à un entier
positif. Voici des exemples : "1789".isdigit() renvoie True ; "Coucou".isdigit()
renvoie False.
Rappelons que l’on peut convertir une chaîne en un entier par la commande int(chaine).
Le petit programme suivant teste si une chaîne peut être convertie en un entier positif :
else: # Problème
print("Je ne sais pas convertir la chaîne en un entier !")
Objectifs : résoudre un problème de triage en modélisant une zone de stockage par la pile.
Un train comporte des wagons bleus qui portent un numéro et des wagons rouges qui portent
une lettre.
7 W 13 G S 5
Le chef de gare souhaite séparer les wagons : d’abord tous les bleus et ensuite tous les rouges
(l’ordre des wagons bleus n’a pas d’importance, l’ordre des wagons rouges non plus).
7 5 13 W S G
Un train trié.
Pour cela, il dispose d’une gare de sortie et d’une zone d’attente : un wagon peut soit être
directement envoyé à la gare de sortie, soit être momentanément stocké dans la zone d’attente.
7 W 13 G S 5
Zone d’attente
7 13 G S 5
W
Phase 1
Zone d’attente
7 13 5
Phase 2
S
G
W
tri_wagons()
Usage : tri_wagons(train)
Entrée : une chaîne de caractères avec des wagons bleus (nombres)
et des wagons rouges (lettres)
Sortie : les wagons bleus d’abord et les rouges ensuite
Action : utilise la pile
Exemple :
• tri_wagons("A 4 C 12") renvoie "4 12 C A"
• tri_wagons("K 8 P 17 L B R 3 10 2 N") renvoie "8
17 3 10 2 N R B L P K"
• Lorsque l’on rencontre un premier opérateur (+, ×,. . . ) on calcule l’opération avec les deux
membres juste avant cet opérateur :
2 8 +
| {z } 6 11 + ×
2+8
• On continue la lecture de l’expression (on cherche le premier opérateur et les deux termes
juste avant) :
10 | {z +
6 11 } × devient 10 17 × qui vaut 170
6+11=17
Autres exemples :
• 8 2 ÷ 3 × 7 +
8 2 ÷
| {z } 3 × 7 + devient 3 ×
4 {z
| } 7 + devient 12 7 + qui vaut 19
8÷2=4 4×3=12
• 11 9 4 3 + − ×
11 9 4 3 +
| {z } − × devient 11 | 7 −
9 {z } × devient 11 2 × qui vaut 22
4+3=7 9−7=2
Exercice. Calcule la valeur des expressions :
• 13 5 + 3 ×
• 3 5 7 × +
• 3 5 7 + ×
• 15 5 ÷ 4 12 + ×
1. Écris une fonction operation() qui calcule la somme ou le produit de deux nombres.
operation()
Usage : operation(a,b,op)
Entrée : deux nombres a et b, un caractère d’opération "+" ou "*"
Sortie : le résultat de l’opération a + b ou a * b
Exemple :
• operation(2,4,"+") renvoie 6
• operation(2,4,"*") renvoie 8
Algorithme.
• — Entrée : une expression en écriture polonaise (une chaîne de caractères).
— Sortie : la valeur de cette expression.
— Exemple : "2 3 + 4 *" (le calcul (2 + 3) × 4) donne 20.
• Partir avec une pile vide.
• Pour chaque élément de l’expression (lue de gauche à droite) :
— si l’élément est un nombre, alors ajouter ce nombre à la pile,
— si l’élément est une opération, alors :
— dépiler une fois pour obtenir un nombre b,
— dépiler une seconde fois pour obtenir un nombre a,
— calculer a + b ou a × b selon l’opération,
— ajouter ce résultat à la pile.
• À la fin, la pile ne contient qu’un seul élément, c’est le résultat du calcul.
calculatrice_polonaise()
Usage : calculatrice_polonaise(expression)
Entrée : une expression en notation polonaise (chaîne de caractères)
Sortie : le résultat du calcul
Action : utilise une pile
Exemple :
• calculatrice_polonaise("2 3 4 + +") renvoie 9
• calculatrice_polonaise("2 3 + 5 *") renvoie 25
Objectifs : déterminer si les parenthèses d’une expression sont placées de façon cohérente.
Algorithme.
Entrée : une expression en écriture habituelle (une chaîne de caractères).
Sortie : « vrai » si les parenthèses sont cohérentes, « faux » sinon.
• Partir avec une pile vide.
• Pour chaque caractère de l’expression lue de gauche à droite :
— si le caractère n’est ni "(", ni ")" alors ne rien faire !
— si le caractère est une parenthèse ouvrante "(" alors ajouter ce caractère à la pile ;
— si le caractère est une parenthèse fermante ")" :
— tester si la pile est vide, si elle vide alors renvoyer « faux » (le programme se
termine là, l’expression est mal parenthésée), si la pile n’est pas vide continuer,
— dépiler une fois, on dépile un "(".
• Si à la fin, la pile est vide alors renvoyer la valeur « vrai », sinon renvoyer « faux ».
parentheses_correctes()
Usage : parentheses_correctes(expression)
Entrée : une expression (chaîne de caractères)
Sortie : vrai ou faux selon que les parenthèses sont correctes ou pas
Action : utilise une pile
Exemple :
• parentheses_correctes("(2+3)*(4+(8/2))") renvoie
True
• parentheses_correctes("(x+y)*((7+z)") renvoie
False
2. Améliore cette fonction pour tester une expression avec des parenthèses et des crochets.
Voici une expression cohérente : [(a + b) ∗ (a − b)], voici des expressions non correctes :
[a + b), (a + b] ∗ [a − b).
Voici l’algorithme à programmer en une fonction crochets_parentheses_correctes().
144 CALCULATRICE POLONAISE – PILES
Algorithme.
Entrée : une expression en écriture habituelle (une chaîne de caractères).
Sortie : « vrai » si les parenthèses et les crochets sont cohérents, « faux » sinon.
• Partir avec une pile vide.
• Pour chaque caractère de l’expression lue de gauche à droite :
— si le caractère n’est ni "(", ni ")", ni "[", ni "]" alors ne rien faire ;
— si le caractère est une parenthèse ou un crochet ouvrant "(" ou "[", alors ajouter
ce caractère à la pile ;
— si le caractère est une parenthèse ou un crochet fermant ")" ou "]" :
— tester si la pile est vide, si elle est vide alors renvoyer « faux » (le programme se
termine là, l’expression n’est pas cohérente), si la pile n’est pas vide continuer,
— dépiler une fois, on dépile un "(" ou un "[",
— si le caractère dépilé (ouvrant) ne correspond pas au caractère lu dans l’expres-
sion, alors renvoyer « faux ». Le programme se termine là, l’expression n’est
pas cohérente ; dire que les caractères correspondent c’est avoir "(" avec ")"
et "[" avec "]".
• Si à la fin, la pile est vide alors renvoyer la valeur « vrai », sinon renvoyer « faux ».
Cette fois la pile peut contenir des parenthèses ouvrantes "(" ou biens des crochets ouvrants
"[". Chaque fois que l’on trouve une parenthèse fermante ")" dans l’expression, il faut que
le haut de la pile soit une parenthèse ouvrante "(". Chaque fois que l’on trouve un crochet
fermant "]" dans l’expression, il faut que le haut de la pile soit un crochet ouvrant "[".
Algorithme.
Entrée : une expression en écriture habituelle
Sortie : l’expression écrite en notation polonaise
• Partir avec une pile vide.
• Partir avec une chaîne vide polonaise qui à la fin contiendra le résultat.
• Pour chaque caractère de l’expression (lue de gauche à droite) :
— si le caractère est un nombre, alors ajouter ce nombre à la chaîne de sortie polonaise ;
— si le caractère est une parenthèse ouvrante "(", alors ajouter ce caractère à la pile ;
— si le caractère est l’opérateur de multiplication "*", alors ajouter ce caractère à la
pile ;
— si le caractère est l’opérateur d’addition "+", alors
tant que la pile n’est pas vide :
dépiler un élément,
si cet élément est l’opérateur de multiplication "*", alors :
ajouter cet élément à la chaîne de sortie polonaise
sinon :
empiler cet élément (on le remet sur la pile après l’avoir enlevé)
terminer immédiatement la boucle « tant que » (avec break)
enfin, ajouter l’opérateur d’addition "+" à la pile.
— si le caractère est une parenthèse fermante ")", alors
tant que la pile n’est pas vide :
dépiler un élément,
si cet élément est une parenthèse ouvrante "(", alors :
terminer immédiatement la boucle « tant que » (avec break)
sinon :
ajouter cet élément à la chaîne de sortie polonaise
• Si à la fin, la pile n’est pas vide, alors ajouter chaque élément de la pile à la chaîne de
sortie polonaise.
146 CALCULATRICE POLONAISE – PILES
ecriture_polonaise()
Usage : ecriture_polonaise(expression)
Entrée : une expression classique (avec les éléments séparés par des
espaces)
Sortie : l’expression en notation polonaise
Action : utilise la pile
Exemple :
• ecriture_polonaise("2 + 3") renvoie "2 3 +"
• ecriture_polonaise("4 * ( 2 + 3 )") renvoie "4 2
3 + *"
• ecriture_polonaise("( 2 + 3 ) * ( 4 + 8 )")
renvoie "2 3 + 4 8 + *"
Dans cet algorithme, on appelle abusivement « caractère » d’une expression chaque élément
entre deux espaces. Exemple : les caractères de "( 17 + 10 ) * 3" sont (, 17, +, 10, ), *
et 3.
Tu vois que l’addition a un traitement plus compliqué que la multiplication. C’est dû au fait que
la multiplication est prioritaire devant l’addition. Par exemple 2 + 3 × 5 signifie 2 + (3 × 5) et
pas (2 + 3) × 5. Si tu souhaites prendre en compte la soustraction et la division, il faut faire
attention à la non-commutativité (a − b n’est pas égal à b − a, a ÷ b n’est pas égal à b ÷ a).
Termine cette fiche en vérifiant que tout fonctionne correctement avec différentes expressions. Par
exemple :
• Définis une expression exp = "( 17 * ( 2 + 3 ) ) + ( 4 + ( 8 * 5 ) )"
• Demande à Python de calculer cette expression : eval(exp). Python renvoie 129.
• Convertis l’expression en écriture polonaise : ecriture_polonaise(exp) renvoie
"17 2 3 + * 4 8 5 * + +"
• Avec ta calculatrice calcule le résultat : calculatrice_polonaise("17 2 3 + * 4 8
5 * + +") renvoie 129. On obtient bien le même résultat !
Chapitre
Visualiseur de 17
texte – Markdown
Tu vas programmer un traitement de texte tout simple qui affiche proprement des paragraphes
et met en évidence les mots en gras et en italiques.
Le code est :
• On rappelle que pour le repère graphique l’axe des ordonnées est dirigé vers le bas. Pour
définir un rectangle, il suffit de préciser les coordonnées (x 1 , y1 ) et (x 2 , y2 ) de deux sommets
opposés (voir la figure ci-dessous).
• Le texte est affiché par la commande canvas.create_text(). Il faut préciser les coor-
données (x, y) du point à partir duquel on souhaite afficher le texte.
• L’option text permet de passer la chaîne de caractères à afficher.
• L’option anchor permet de préciser le point d’ancrage du texte, anchor=NW signifie que la
zone de texte est ancrée au point Nord-Ouest (NW) (voir la figure ci-dessous).
• L’option fill permet de préciser la couleur du texte.
• L’option font permet de définir la fonte (c’est-à-dire le style et la taille des caractères). Voici
des exemples de fontes, à toi de les tester :
— Font(family="Times", size=20)
— Font(family="Courier", size=16, weight="bold") en gras
— Font(family="Helvetica", size=16, slant="italic") en italique
(0, 0) x
(x 1 , y1 ) ancre Nord-Ouest
(x 2 , y2 )
1. (a) Définis une fenêtre tkinter de taille 800 × 600 par exemple.
(b) Dessine un rectangle gris (qui sera notre zone de texte) de taille largeur × hauteur
(par exemple 700 × 500).
(c) Définis plusieurs types de fontes : fonte_titre, fonte_sous_titre, fonte_gras,
font_italique, fonte_texte.
VISUALISEUR DE TEXTE – MARKDOWN 149
Cours 2 (Markdown).
Le Markdown est un langage de balisage simple qui permet d’écrire un fichier texte propre et
éventuellement de le convertir vers un autre format (html, pdf. . . ).
Voici un exemple de fichier texte avec une syntaxe Markdown avec juste en dessous son rendu
graphique.
# L'Origine des Espèces
## par Charles Darwin
** Chapitres **
La syntaxe est simple, avec un fichier texte bien lisible. Voici quelques éléments de cette syntaxe :
• un texte en gras s’obtient en entourant le texte par deux astérisques ** ;
• un texte en italique s’obtient en entourant le texte par un astérisque * ;
• la ligne d’un titre commence par dièse # ;
• la ligne d’un sous-titre commence par deux dièses ## ;
• pour les éléments d’une liste, chaque ligne commence par un symbole spécial, pour nous ce
sera le symbole « plus » +.
• Il existe aussi une syntaxe pour afficher des liens, des tableaux, du code. . .
Dans la suite nous utiliserons la syntaxe simplifiée comme elle est décrite ci-dessus.
1. Écris une fonction afficher_ligne_v1(par,posy) qui affiche un par un les mots d’un
paragraphe par (sur la ligne d’ordonnée posy).
Indications :
• Ces mots sont obtenus grâce à la commande [Link]().
• La ligne affichée commence tout à gauche, elle déborde à droite si elle trop longue.
• Après chaque mot on place une espace puis le mot suivant.
• Sur l’image ci-dessus les mots sont encadrés.
VISUALISEUR DE TEXTE – MARKDOWN 151
Indications :
• Pour savoir dans quel mode il faut afficher la ligne, il suffit de tester les premiers caractères
de la ligne. La ligne d’un titre commence par #, celle d’un sous-titre par ##, celle d’une
liste par +.
• Pour les listes, tu peux obtenir le caractère « • » par le caractère unicode u'\u2022'.
Tu peux aussi indenter les éléments de la liste pour plus de lisibilité.
• Utilise la fonction choix_fonte() de la première activité.
• Sur l’image ci-dessus, chaque ligne est produite par un appel à la fonction. Par exemple
afficher_ligne_v2("## Et ici un sous titre",100)
3. Améliore encore ta fonction en afficher_ligne_v3(par,posy) pour tenir compte des
mots en gras et en italique dans le texte.
Indications :
• Les mots en gras sont entourés par la balise **, les mots en italique par la balise *. Dans
notre syntaxe simplifiée, les balises sont séparées des mots par des espaces, par exemple :
"Mot ** en gras ** et lui en * italique *".
• Définis une variable booléenne en_gras qui est fausse au départ ; chaque fois que tu
rencontres la balise ** alors inverse la valeur de en_gras (« vrai » devient « faux »,
« faux » devient « vrai »). Tu peux utiliser l’opérateur not.
• Utilise encore la fonction choix_fonte() de la première activité.
• Sur l’image ci-dessus, chaque ligne est produite par un appel à la fonction. Par
exemple afficher_ligne_v3("+ Pommes et surtout ** poires ** et *
ananas *",100)
4. Améliore encore ta fonction en afficher_paragraphe(par,posy) qui gère l’affichage
d’un paragraphe (c’est-à-dire une chaîne de caractères qui peut être très longue) sur plusieurs
lignes.
152 VISUALISEUR DE TEXTE – MARKDOWN
Indications :
• Dès que l’on place un mot qui dépasse la longueur de la ligne (voir ceux qui sortent du
cadre sur l’image ci-dessus), alors le mot suivant est placé sur la ligne suivante.
• La fonction va donc modifier la variable posy à chaque saut de ligne. À la fin, la fonction
retourne la nouvelle valeur de posy, qui sera utile pour afficher le paragraphe suivant.
5. Termine par une fonction afficher_fichier(nom) qui visualise les paragraphes d’un
fichier texte ayant la syntaxe Markdown simplifiée.
Activité 3 (Justification).
Objectifs : comprendre comment il est possible de « justifier » un texte, c’est-à-dire de faire
en sorte que les mots soient bien alignés sur la partie gauche et la partie droite de la page.
Pour modéliser le problème nous travaillons avec une suite d’entiers qui représente les
longueurs de nos mots.
Dans cette activité :
• longueurs est une liste d’entiers (par exemple une liste de 50 entiers compris entre 5 et
15) qui représentent les longueurs des mots ;
• on fixe une constante longueur_ligne qui représente la longueur d’une ligne. Pour nos
exemples, cette longueur vaut 100.
Dans les activités précédentes, nous passions à la ligne suivante après qu’un mot ait dépassé la
fin de ligne. Nous représentons ceci par la figure suivante :
VISUALISEUR DE TEXTE – MARKDOWN 153
longueurs = [8, 11, 9, 14, 8, 8, 15, 10, 14, 11, 15, 15, 5, 12, 9, 9, 15, 10, 14, 5, 12, 8, 8, 13,
10, 11, 8, 13, 7, 5, 6, 11, 7, 7, 13, 6, 6, 9, 8, 12, 5, 8, 7, 6, 6, 15, 13, 11, 7, 12]
1. Écris une fonction coupures_simples() qui calcule les indices permettant de réaliser les
coupures correspondant à la figure ci-dessous, c’est-à-dire un alignement à gauche (sans
espaces) et sans dépasser la longueur totale de la ligne (ici de longueur 100).
154 VISUALISEUR DE TEXTE – MARKDOWN
coupures_simples()
Usage : coupures_simples(long)
Entrée : une suite de longueurs (une liste d’entiers)
Sortie : la liste des indices où effectuer une coupure
2. Modifie ton travail en une fonction coupures_espaces() qui rajoute une espace (avec
longueur_espace = 1) entre deux mots d’une même ligne (mais pas au début de ligne,
ni à la fin de la ligne). Cela correspond au dessin suivant :
Pour notre exemple, les coupures renvoyées sont [0, 8, 16, 24, 34, 45, 50].
3. Afin de pouvoir justifier le texte, tu autorises les espaces à être plus grandes que la longueur
initiale de 1. Sur chaque ligne, les espaces entre les mots sont toutes de la même longueur
(supérieure ou égale 1) de sorte que le dernier mot soit aligné à droite. D’une ligne à l’autre,
la longueur des espaces peut changer.
VISUALISEUR DE TEXTE – MARKDOWN 155
Tu as maintenant tout en main pour visualiser du texte écrit avec la syntaxe Markdown et le
justifier. Cela représente quand même encore du travail ! Tu peux aussi améliorer la prise
en charge de la syntaxe Markdown : prendre en charge le code, les listes numérotées, les
sous-listes, les mots en gras et en italique en même temps. . .
Chapitre
L-système
18
Les L-systèmes offrent une façon très simple de coder des phénomènes complexes. À partir
d’un mot initial et d’opérations de remplacement, on arrive à des mots compliqués. Lorsque
l’on « dessine » ces mots, on obtient de superbes figures fractales. Le « L » vient du botaniste
A. Lindenmayer qui a inventé les L-systèmes afin de modéliser les plantes.
Cours 1 (L-système).
Un L-système est la donnée d’un mot initial et de règles de remplacement. Voici un exemple
avec le mot de départ et une seule règle :
BgAdB A → ABA
Le k-ème itéré du L-système s’obtient en appliquant k fois la substitution au mot de départ.
Avec notre exemple :
• Première itération. Le mot de départ est BgAdB, la règle est A → ABA : on remplace le A
par ABA. On obtient le mot BgABAdB.
• Deuxième itération. On part du mot obtenu BgABAdB, on remplace les deux A par ABA : on
obtient le mot BgABABABAdB.
158 L-SYSTÈME
Objectifs : tracer le flocon de Koch à partir d’un mot obtenu par itérations.
itéré du L-système associé au mot initial depart selon la règle regle qui contient le couple
formé de la lettre et de son motif de remplacement. Par exemple, avec :
• depart = "A"
• regle = ("A","AgAdAdAgA") c’est-à-dire A → AgAdAdAgA
• pour k = 0, la fonction renvoie le mot de départ A,
• pour k = 1, la fonction renvoie AgAdAdAgA,
• pour k = 2, la fonction renvoie :
AgAdAdAgAgAgAdAdAgAdAgAdAdAgAdAgAdAdAgAgAgAdAdAgA
• pour k = 3, la fonction renvoie : AgAdAdAgAgA... un mot de 249 lettres.
3. Trace les premières images du flocon de Koch donné comme ci-dessus par :
départ : A règle : A → AgAdAdAgA
Ici les images pour k = 1 jusqu’à k = 5. Pour k = 1, le mot est AgAdAdAgA et tu peux
vérifier le tracé sur la première image.
4. Trace d’autres figures fractales à partir des L-systèmes suivants. Pour tous ces exemples le
mot de départ est "AdAdAdA" (un carré) et la règle est à choisir parmi :
• ("A","AdAgAgAAdAdAgA")
• ("A","AgAAdAAdAdAgAgAAdAdAgAgAAgAAdA")
• ("A","AAdAdAdAdAA")
• ("A","AAdAddAdA")
• ("A","AAdAdAdAdAdAgA")
• ("A","AAdAgAdAdAA")
• ("A","AdAAddAdA")
• ("A","AdAgAdAdA")
L-SYSTÈME 161
Cours 3 (Piles).
Une pile est une zone de stockage temporaire. Les détails sont dans la fiche « Calculatrice
polonaise – Piles ». Voici juste quelques rappels.
L-SYSTÈME 163
(−100, 0), 60
Sommet de la pile
(0, 0), 0
(100, 100), 0
(0, 0), 90
(0, 0), 30
Une pile
• Une pile c’est comme un pile d’assiettes ; on pose des éléments un par un au-dessus de la pile ;
on retire les éléments un par un, également à partir du dessus. C’est le principe : « dernier
arrivé, premier parti » (last in, first out).
• On modélise une pile par une liste.
• Au départ la pile est vide : pile = [].
• Empiler. On ajoute les éléments en fin de liste : [Link](element) ou bien pile
= pile + [element].
• Dépiler. On retire un élément par la commande pop() :
element = [Link]()
qui renvoie le dernier élément de la pile et le supprime de la liste.
• Sur le dessin et dans l’activité suivante, les éléments de la pile sont du type (x, y), θ qui
stockeront un état de la tortue : (x, y) est la position et θ sa direction.
2. Retour en arrière.
On autorise maintenant des crochets dans nos mots. Par exemple AgA[gAAA]A[dAA]A.
Lorsque l’on rencontre un crochet ouvrant « [ », on mémorise la position de la tortue, puis
les commandes entre crochets sont exécutées comme d’habitude, lorsque l’on trouve un
crochet fermant « ] » on repart de la position mémorisée auparavant.
Comprenons l’exemple du tracé du AgA [gAAA] A [dAA] A .
Voici comment tracer un mot contenant des crochets à l’aide d’une pile :
L-SYSTÈME 165
Images dynamiques
19
Nous allons déformer des images. En répétant ces déformations, les images deviennent
brouillées. Mais par miracle au bout d’un certain nombre de répétitions l’image de départ
réapparaît !
j =0 j =1 j 0 =0 j 0 =1
i =0 A B a b i 0 =0 A a B b
i =1 C D c d i =1
0
C c D d
Par exemple le pixel en position (1, 1) (symbolisé par la lettre D) est envoyé en position (4, 4).
Explicitons ce principe par des formules. Pour chaque couple (i, j), on calcule son image (i 0 , j 0 )
par la transformation du photomaton selon les formules suivantes :
• Si i et j sont pairs : (i 0 , j 0 ) = (i//2, j//2).
168 IMAGES DYNAMIQUES
L’image devient de plus en plus brouillée, mais au bout d’un certain nombre de répétitions de la
transformation, on retombe sur l’image de départ !
P2
5 5
255
128 192 128 192 128
224 0 228 0 224
228 228 228 228 228
224 64 64 64 224
192 192 192 192 192
étirer
A B
A a B b
a b
A B
replier
A
B
Formules. Pour 0 6 i < 2n et 0 6 j < n les éléments en position (i, j) du tableau sont conservés.
Pour 2n 6 i < n et 0 6 j < n un élément du tableau d’arrivée (i, j), correspond à un élément
n
2 − i − 1, 2n − 1 − j du tableau de départ.
Exemple. À partir du tableau étiré 2 × 8 à gauche, on obtient un tableau replié 4 × 4 à droite.
1 5 2 6
1 5 2 6 3 7 4 8 9 13 10 14
9 13 10 14 11 15 12 16 16 12 15 11
8 4 7 3
La transformation du boulanger est la succession d’un étirement et d’un repliement. Partant
d’un tableau n × n on obtient encore un tableau n × n.
Voyons un exemple de l’action de plusieurs transformations du boulanger. À gauche l’image
initiale de taille 128 × 128, puis le résultat de k = 1, 2, 3 itérations.
172 IMAGES DYNAMIQUES
1 2 3 4 1 5 2 6 1 9 5 13
5 6 7 8 9 13 10 14 16 8 12 4
9 10 11 12 16 12 15 11 3 11 7 15
13 14 15 16 8 4 7 3 14 6 10 2
4. Programme une fonction boulanger_images(nom_image,kmax) qui calcule les images
correspondant à la transformation du boulanger, avec des itérations allant de k = 1 à
k = kmax .
5. Expérimente pour différentes valeurs de la taille n, afin de voir au bout de combien d’itéra-
tions on retrouve l’image de départ.
Attention ! Il faut parfois itérer beaucoup avant de retrouver l’image de départ. Par exemple
avec n = 4, on retrouve l’image de départ au bout de k = 5 itérations, avec n = 256 c’est
k = 17. Conjecture une valeur de retour dans le cas où n est une puissance de 2. Par contre
pour n = 10, il faut k = 56 920 itérations !
Voici un exemple avec une image de taille 256 × 256, d’abord l’image initiale, puis une première
itération (k = 1) et une deuxième itération (k = 2).
IMAGES DYNAMIQUES 173
k = 3, 4, 5 :
k = 15, 16, 17 :
Cette fiche est basée sur l’article « Images brouillées, images retrouvées » par Jean-Paul Delahaye et
Philippe Mathieu (Pour la Science, 1997).
Chapitre
20
Jeu de la vie
Le jeu de la vie est un modèle simple de l’évolution d’une population de cellules qui naissent
et meurent au cours du temps. Le « jeu » consiste à trouver des configurations initiales qui
donnent des évolutions intéressantes : certains groupes de cellules disparaissent, d’autres se
stabilisent, certains se déplacent. . .
A 3 voisins Naissance
Naissance
• Pour une case contenant une cellule au jour j, ayant soit 2 ou soit 3 cellules voisines : alors
la cellule continue de vivre. Dans les autres cas la cellule meurt (avec 0 ou 1, elle meurt
d’isolement, avec plus de 4 voisins, elle meurt de surpopulation !).
A 4 voisins
A 4 voisins A 0 voisin Morts Naissances
0 0 0 0 0
1 2 3 2 1
1 1 2 1 1
1 2 3 2 1
0 0 0 0 0
Position de départ (jour j) Nombre de voisins Évolution (jour j + 1)
0 1 2 2 1 1 2 3 2 1
1 3 3 2 1 2 2 3 1 1
1 3 4 4 1 3 4 6 3 1
1 3 2 2 0 2 2 2 1 0
0 1 1 1 0 1 2 2 1 0
Jour 0 Jour 1 Jour 2
JEU DE LA VIE 177
Nous modélisons l’espace de vie des cellules par un tableau à double entrée, contenant des
entiers, 1 pour signifier la présence d’une cellule, 0 sinon. Voici en exemple la configuration
« bouche » et son tableau :
indice j
j=0 j=1 ··· j = p−1
i=0 0 0 0 0 0 0
i=1 0 0 1 1 1 0
indice i n
..
. 0 1 1 1 0 0
i = n−1 0 0 0 0 0 0
p
Cellules Tableau
1. • Initialise deux variables n (la hauteur du tableau) et p (la largeur) (par exemple à 5 et
8).
• Définis un tableau à deux dimensions rempli de zéros par la commande :
tableau = [[0 for j in range(p)] for i in range(n)]
• Par des instructions du type tableau[i][j] = 1 remplis le tableau afin de définir la
configuration du clignotant, de la bouche. . .
2. Programme l’affichage à l’écran d’un tableau donné. Par exemple, le clignotant s’affiche
ainsi :
00000000
00000000
00111000
00000000
00000000
Indication : par défaut la commande print() passe à la ligne suivante à chaque appel (il
rajoute le caractère "\n" qui est le caractère de fin de ligne). On peut lui spécifier de ne
pas le faire par l’option print("Mon texte",end="").
Activité 3 (Évolution).
00000000 00000000
00000000 00010000
00111000 évolue en 00010000
00000000 00010000
00000000 00000000
Indications. Pour définir un nouveau tableau reprend la commande :
nouveau_tableau = [[0 for j in range(p)] for i in range(n)]
puis modifie le tableau comme voulu.
Activité 4 (Itérations).
Objectifs : finir le programme graphique afin que l’utilisateur puisse définir des configu-
rations et les faire évoluer d’un simple clic.
1. Améliore la fenêtre graphique afin de faciliter la vie de l’utilisateur :
• Un bouton « évoluer » qui à chaque clic affiche l’évolution.
• Des boutons permettant d’afficher des configurations pré-définies (sur la capture d’écran
ci-dessous c’est la configuration « pentadecathlon »).
2. Perfectionne ton programme afin que l’utilisateur dessine la configuration qu’il souhaite
par des clics de la souris. Un clic sur une case éteinte l’allume, un clic sur une case allumée
l’éteint. Tu peux décomposer ce travail en trois fonctions :
• allumer_eteindre(i,j), qui commute la cellule (i, j) ;
• xy_vers_ij(x,y) qui convertit des coordonnées graphiques (x, y) en des coordonnées
entières (i, j) (utiliser la variable echelle et la division entière).
• action_clic_souris(event) pour récupérer les coordonnées (x, y) d’un clic de
souris (voir le cours ci-dessous) et commuter la case cliquée.
180 JEU DE LA VIE
# Fenêtre
root = Tk()
canvas = Canvas(root, width=800, height=600, background="white")
[Link](side=LEFT, padx=5, pady=5)
# Association clic/action
[Link]("<Button-1>", action_clic_souris)
# Lancement
[Link]()
Voici quelques explications :
• La création de la fenêtre est habituelle. Le programme se termine par le lancement avec la
JEU DE LA VIE 181
commande mainloop().
• Le premier point clé est d’associer un clic de souris à une action, c’est ce que fait la ligne
[Link]("<Button-1>", action_clic_souris)
Chaque fois que le bouton gauche de la souris est cliqué, Python exécute la fonction
action_clic_souris. (Note qu’il n’y a pas de parenthèses pour l’appel à la fonction.)
• Second point clé : la fonction action_clic_souris récupère les coordonnées du clic et
ici ensuite fait deux choses : elle affiche un petit rectangle à l’endroit du clic et affiche dans
la fenêtre du terminal les coordonnées (x, y).
• Les coordonnées x et y sont exprimées en pixels ; (0, 0) désigne le coin en haut à gauche de
la fenêtre (la zone délimitée par canvas).
Tu en trouveras plein d’autres sur internet mais surtout amuse-toi à en découvrir de nouvelles !
En particulier, trouve des configurations :
• qui restent fixes au cours du temps ;
• qui évoluent, puis deviennent fixes ;
• qui sont périodiques (les mêmes configurations reviennent en boucles) avec une période de 2,
3 ou plus ;
• qui voyagent ;
• qui propulsent des cellules ;
• dont la population augmente indéfiniment !
Chapitre
Graphes et combi-
natoire de Ramsey
21
Tu vas voir qu’un problème tout simple, qui concerne les relations entre seulement six
personnes, va demander énormément de calculs pour être résolu.
On considère n personnes. Pour deux personnes parmi elles, soit elles se connaissent (elles sont
amies), soit elles ne se connaissent pas (elles sont étrangères l’une à l’autre). Nous schématisons
cela par un graphe :
• une personne est représentée par un sommet (numéroté de 0 à n − 1) ;
• si deux personnes sont amies, on relie les sommets correspondants par une arête verte ;
• sinon (elles sont étrangères), on relie les sommets correspondants par une arête pointillée
rouge.
Le graphe ci-dessous signifie que 0 est ami avec 2 ; 1 est ami avec 3. Les autres paires ne se
connaissent pas.
184 GRAPHES ET COMBINATOIRE DE RAMSEY
3 0
2 1
Un graphe vérifie le problème de Ramsey, s’il y a parmi ses sommets, ou bien 3 amis, ou bien s’il
y a 3 étrangers.
j0 i0
i Trois étrangers
0
k Trois amis k
Voici un exemple de graphe à 5 sommets qui vérifie l’énoncé : il possède bien 3 sommets étrangers
(les sommets 0, 2 et 4), même s’il ne possède pas trois amis.
1
Un graphe avec n = 5 qui vérifie l’énoncé de Ramsey
Cours 2 (Modélisation).
Nous modélisons un graphe par un tableau à double entrée, contenant des 0 et des 1.
Premier exemple ci-dessous : les sommets 0 et 2 sont amis (car reliés par un arête verte) donc le
tableau contient un 1 en position (0, 2) et aussi en (2, 0). De même 1 et 3 sont amis, donc le
tableau contient un 1 en position (1, 3) et (3, 1). Le reste du tableau contient des 0.
GRAPHES ET COMBINATOIRE DE RAMSEY 185
indice j
i=0 0 0 1 0
i=1 0 0 0 1
indice i n
i=2 1 0 0 0
i=3 0 1 0 0
2 1
n
i=0 0 1 0 1 0
i=1 1 0 1 0 1
i=2 0 1 0 1 0
0
i=3 1 0 1 0 1
i=4 0 1 0 1 0
2
Objectifs : définir des graphes et tester si trois sommets donnés sont amis.
186 GRAPHES ET COMBINATOIRE DE RAMSEY
1. Définis le tableau des graphes des quatre exemples ci-dessus. Tu peux commencer par
initialiser le tableau par
graphe = [[0 for j in range(n)] for i in range(n)]
Puis ajoute des commandes :
graphe[i][j] = 1 et graphe[j][i] = 1
N’oublie pas que si le sommet i est relié au sommet j par une arête, alors il faut mettre un 1
en position (i, j) mais aussi en position ( j, i).
2. Définis une fonction voir_graphe(graphe) qui permet d’afficher à l’écran le tableau
d’un graphe. Ainsi le troisième exemple ci-dessus (avec n = 5) doit s’afficher ainsi :
00110
00101
11000
10001
01010
3. On fixe trois sommets i, j, k d’un graphe. Écris une fonction
contient_3_amis_fixes(graphe,i,j,k) qui teste si les sommets i, j, k sont
trois amis (la fonction renvoie « vrai » ou « faux »). Fais le même travail avec une fonction
contient_3_etrangers_fixes(graphe,i,j,k) pour savoir si ces sommets sont
étrangers.
Trouve à la main sur le quatrième exemple, trois sommets amis ou étrangers et vérifie ta
réponse à l’aide des fonctions que tu viens de définir.
Indications. Cette activité n’est pas nécessaire pour la suite, elle aide juste à visualiser les
graphes. Il faut utiliser le module tkinter et les fonctions create_line(), create_oval()
et éventuellement create_text().
Le point le plus délicat est d’obtenir les coordonnées des sommets. Tu auras besoin des fonctions
sinus et cosinus (disponibles dans le module math). Les coordonnées (x i , yi ) du sommet numéro
i d’un graphe à n éléments peuvent être calculées par les formules :
2iπ 2iπ
x i = r cos et yi = r sin .
n n
Ces sommets sont situés sur le cercle de rayon r, centré en (0, 0). Tu devras choisir r assez
grand (par exemple r = 200) et décaler le cercle pour bien l’afficher à l’écran.
(x 1 , y1 )
(x i , yi )
yi = r sin( 2iπ
n )
(x 0 , y0 )
xi = r cos( 2iπ (0, 0) x
n )
(x n−1 , yn−1 )
188 GRAPHES ET COMBINATOIRE DE RAMSEY
Exemple.
• L’écriture binaire de p = 37 est [Link].0.1. Si on veut son écriture binaire sur n = 8 bits
alors il faut rajouter deux 0 non significatifs devant : [Link].[Link].
• Ainsi le résultat de la commande decimal_vers_binaire(37,8) doit être [0, 0, 1,
0, 0, 1, 0, 1].
• La commande decimal_vers_binaire(37,10) renvoie l’écriture de 37 en binaire sur
10 bits : [0, 0, 0, 0, 1, 0, 0, 1, 0, 1].
Indications.
• Tu peux utiliser la commande bin(p) !
• La commande list(ma_chaine) renvoie la liste des caractères composant ma_chaine.
• Attention ! On veut une liste d’entiers 0 ou 1, pas des caractères '0' ou '1'. La commande
int('0') renvoie 0 et int('1') renvoie 1.
• ma_liste = ma_liste + [element] ajoute un élément en fin de liste, alors que
ma_liste = [element] + ma_liste ajoute l’élément en début de liste.
Cours 3 (Sous-ensembles).
Soit En = {0, 1, 2, . . . , n − 1} l’ensemble des entiers de 0 à n − 1. L’ensemble En contient donc n
éléments.
Par exemple E3 = {0, 1, 2}, E4 = {0, 1, 2, 3}. . .
Sous-ensembles.
Quels sont les sous-ensembles de En ? Par exemple il y a 8 sous-ensembles de E3 , ce sont :
• le sous-ensemble {0} composé du seul élément 0 ;
• le sous-ensemble {1} composé du seul élément 1 ;
• le sous-ensemble {2} composé du seul élément 2 ;
• le sous-ensemble {0, 1} composé de l’élément 0 et de l’élément 1 ;
• le sous-ensemble {0, 2} ;
• le sous-ensemble {1, 2} ;
• le sous-ensemble {0, 1, 2} composé de tous les éléments ;
• l’ensemble vide ∅ qui ne contient aucun élément !
Proposition. L’ensemble En contient 2n sous-ensembles.
Par exemple E4 = {0, 1, 2, 3} possède 24 = 16 sous-ensembles possibles. Amuse-toi à les trouver
tous ! Pour E6 il y a 26 = 64 sous-ensembles possibles.
GRAPHES ET COMBINATOIRE DE RAMSEY 189
Activité 4 (Sous-ensembles).
Objectifs : générer tous les sous-ensembles afin de tester tous les triplets de sommets. Pour
cela nous utiliserons l’écriture binaire.
Voici comment nous associons à chaque entier p vérifiant 0 6 p < 2n un sous-ensemble de
En = {0, 1, . . . , n − 1}.
Commençons par un exemple, avec n = 6 et p = 26 :
• l’écriture binaire de p = 26 sur n = 6 bits est [0,1,1,0,1,0] ;
• il y a des 1 au rang 1, 2 et 4 (en commençant au rang 0 à gauche) ;
• le sous-ensemble associé est alors {1, 2, 4}.
p = 26 0 1 1 0 1 0 {1, 2, 4}
(n = 6)
rang : 0 1 2 3 4 5
Autres exemples.
• Avec n = 8 et p = 57 dont l’écriture binaire sur 8 bits est [0,0,1,1,1,0,0,1], le sous-
ensemble associé correspond aux rangs 2, 3, 4, 7, c’est donc {2, 3, 4, 7}.
p = 57 0 0 1 1 1 0 0 1 {2, 3, 4, 7}
(n = 8)
rang : 0 1 2 3 4 5 6 7
Entier p de départ Écriture de p sur n bits Sous-ensemble associé à p
[[3, 4, 5], [2, 4, 5], [2, 3, 5], [2, 3, 4], [1, 4, 5],
[1, 3, 5], [1, 3, 4], [1, 2, 5], [1, 2, 4], [1, 2, 3],
[0, 4, 5], [0, 3, 5], [0, 3, 4], [0, 2, 5], [0, 2, 4],
[0, 2, 3], [0, 1, 5], [0, 1, 4], [0, 1, 3], [0, 1, 2]]
(n−1)n
de graphes à n sommets. Il y a N = 2 tableaux possibles. Tu peux les générer par une
méthode similaire à celle pour les sous-ensembles :
• pour chaque entier p qui vérifie 0 6 p < 2N ,
• calcule l’écriture binaire de p sur N bits,
• remplis le tableau élément par élément, avec les 0 et les 1 de l’écriture binaire.
Indications. Pour remplir un tableau à partir d’une écriture binaire liste_binaire donnée
de p, tu peux utiliser une double boucle du type :
for j in range(0,n):
for i in range(j+1,n):
b = liste_binaire.pop()
graphe[i][j] = b
graphe[j][i] = b
Voici le principe de cette boucle qui remplit la partie au-dessus de la diagonale (et aussi
la partie en-dessous par symétrie). Cette boucle prend le dernier bit de la liste et le place
sur la première case libre au-dessus de la diagonale ; puis l’avant-dernier bit est placé sur la
seconde case libre. . . ; le premier bit de la liste remplit la dernière case libre.
0 1 0 1 0
0 0 0 1 N cases au-dessus de la dia-
N cases sous la diagonale 0 1 0 gonale
(remplies par symétrie) 0 1
0
Remplissage du tableau
1. Améliore ton programme afin qu’il vérifie la conjecture pour n = 6 en moins d’une seconde.
Idées.
• Il faut générer la liste des triplets une fois pour toute au début du programme (et non à
chaque nouveau graphe).
• Il ne faut pas générer une liste de tous les graphes possibles, puis les tester dans un
second temps. Il faut en générer un puis le tester avant de passer au suivant.
• Dès que tu as trouvé 3 amis (ou 3 étrangers) c’est gagné ! Stoppe immédiatement la
boucle quitte à utiliser l’instruction break et passe au graphe suivant.
• Tu peux seulement tester les graphes qui correspondent à p entre 0 et 2N /2 (car pour
les p suivants cela revient à échanger les segments verts en rouges et inversement).
Avec ces conseils voici les temps de calcul auxquels tu peux t’attendre :
Nombre de sommets Nombre de graphes Temps de calcul approximatif
n=6 32 768 < 1 seconde
n=7 2 097 152 < 1 minute
n=8 268 435 456 < 1 heure
n=9 68 719 476 736 < 10 jours
2. Il existe un énoncé plus difficile. Il s’agit de trouver à partir de quelle taille n un graphe
contient toujours ou bien 4 amis ou bien 3 étrangers. Être 4 amis signifie que deux à deux
ils sont reliés par un segment vert, comme ci-dessous :
(a) Trouve des graphes à n = 6 (puis n = 7) sommets qui ne vérifient pas cet énoncé.
(b) En cherchant un peu avec la machine trouve des graphes à 8 sommets qui ne vérifient
pas cet énoncé.
(c) Prouve que n’importe quel graphe ayant 9 sommets contient 4 amis ou bien 3 étrangers !
Indications. Il faut tester tous les graphes correspondants aux entiers p compris entre
8×9
0 et 2N = 2 2 = 68 719 476 736. Le temps total de calcul est d’environ 20 jours ! Tu
peux partager les calculs entre plusieurs ordinateurs : un ordinateur fait les calculs pour
0 6 p 6 1 000 000, un deuxième ordinateur pour 1 000 001 6 p 6 2 000 000,. . .
• On sait prouver qu’il faut n = 18 sommets pour avoir toujours 4 amis ou 4 étrangers.
• Par contre personne dans le monde ne sait quelle est la valeur du plus petit n pour le
problème des 5 amis/5 étrangers !
Chapitre
22
Bitcoin
Le bitcoin est une monnaie dématérialisée et décentralisée. Elle repose sur deux principes
informatiques : la cryptographie à clé publique et la preuve de travail. Pour comprendre ce
second principe, tu vas créer un modèle simple de bitcoin.
Vérifie que x = 6 543 210 est solution lorsque y = 8 371 779 et p = 15 486 869. Affiche le
temps de calcul nécessaire à cette vérification. (Voir le cours plus bas.)
2. Recherche de solution (difficile). Pour trouver une solution x, il n’y a pas vraiment d’autres
choix pour nous que de tester tous les x en commençant par x = 0, x = 1. . . Programme
une fonction racine(y) qui renvoie une solution x du problème pour y donné (ou None
s’il n’y a pas de solution).
• Pour p = 101 et y = 17, trouve x tel que x 2 = y (mod p).
• Pour p = 15 486 869 et y = 8 371 779, tu dois retrouver le x de la première question.
Combien de temps a pris la recherche ?
• Pour p = 15 486 869 et y = 13 017 204, trouve x tel que x 2 = y (mod p).
Conclusion : nous avons trouvé un problème difficile à résoudre, mais pour lequel il est facile de
vérifier qu’une solution donnée convient. Pour des valeurs de p plus grandes, la recherche d’une
solution x peut être beaucoup trop longue et ne pas aboutir. Nous allons voir comment on peut
ajuster la difficulté du problème.
3. Au lieu de chercher une solution exacte à notre problème x 2 = y (mod p), qui est équivalent
à x 2 − y (mod p) = 0. On cherche une solution approchée, c’est-à-dire qui vérifie :
x 2 − y (mod p) 6 m.
Par exemple si m = 5, alors on peut avoir (modulo p) : x 2 − y = 0, x 2 − y = 1, x 2 − y = 2,. . .
ou x 2 − y = 5.
Programme une fonction racine_approchee(y,marge) qui trouve une solution appro-
chée à notre problème x 2 = y (mod p).
Combien de temps faut-il pour trouver un solution au problème approché lorsque p =
15 486 869, y = 8 371 779 et m = 20 ? Choisis un nombre premier p assez grand et trouve
une marge d’erreur m de sorte que trouver une solution au problème approché nécessite
environ entre 30 et 60 secondes de calculs (pour un y quelconque).
Voici des exemples de nombres premiers que tu peux utiliser pour tes essais :
101 1097 10651 100109 1300573 15486869
179426321 2276856017 32416187567
Cours 1 (Chronomètre).
Le module time permet de chronométrer le temps d’exécution mais aussi de savoir la date et
l’heure (voir aussi le module timeit expliqué dans la fiche « Arithmétique – Tant que – I »).
Voici un petit script pour mesurer le temps de calcul d’une instruction.
import time
debut_chrono = [Link]()
BITCOIN 197
[Link](2)
fin_chrono = [Link]()
Pour éviter que quelqu’un ne vienne truquer le livre de compte, après chaque transaction on
ajoute dans le livre une certification construite à partir d’une preuve de travail. Voici ce que l’on
écrit dans le livre :
1. On commence par une preuve de travail quelconque. Pour nous ce sera [0,0,0,0,0,0].
2. On écrit la première transaction (par exemple "Amir -100").
3. On calcule et on écrit dans le livre une preuve de travail, qui va servir de certificat. C’est une
liste (par exemple [56,42,10,98,2,34]) obtenue après beaucoup de calculs prenant en
compte la transaction précédente et la précédente preuve de travail.
198 BITCOIN
4. À chaque nouvelle transaction (par exemple "Barbara +45"), quelqu’un calcule une preuve
de travail pour la dernière transaction associée à la précédente preuve. On écrit la transaction,
puis la preuve de travail.
preuve
preuve transaction 3
preuve transaction 2
La preuve de travail que l’on calcule dépend de la transaction précédente mais aussi de la preuve
de travail précédente, qui elle même dépend des données antérieures... Ainsi, chaque nouvelle
preuve de travail dépend en fait de tout ce qui a été écrit depuis le début (même si le calcul ne
porte explicitement que sur les deux dernières entrées).
Quelqu’un qui voudrait truquer une transaction passée devrait recalculer toutes les preuves de
travail qui viennent après. Ceci n’est pas possible pour une personne seule : il y a plusieurs
preuves de travail à calculer et chaque preuve demande beaucoup de calculs.
3. On aura besoin de transformer une phrase en une liste de nombres. De plus, on va découper
nos listes en blocs de taille N (avec N = 6), on rajoute donc des zéros en début de liste afin
qu’elle soit de longueur un multiple de N .
Écris une fonction phrase_vers_liste(phrase) qui convertit une chaîne de caractères
en une liste d’entiers entre 0 et 99 et si besoin rajoute des zéros devant afin que la liste ait
la bonne taille.
La formule à utiliser pour convertir un caractère en un entier strictement inférieur à 100
est :
ord(c) % 100
Par exemple : si phrase = "Vive moi !" alors la fonction renvoie :
[0, 0, 86, 5, 18, 1, 32, 9, 11, 5, 32, 33]
Le caractère "i" à pour code ASCII/unicode 105 donc, modulo 100, le nombre est 5. Note
que la fonction ajoute deux 0 en début de liste afin d’avoir une longueur qui est un multiple
de N = 6.
(d) On réduit chaque entier modulo 100 afin d’obtenir des entiers entre 0 et 99.
b0 b1 b2 b3 b4 b5
+ + +
(a) additions
• On ajoute terme à terme (et modulo 100), le résultat de ce mélange au second bloc.
• On recommence en partant du nouveau second bloc.
• Lorsqu’il ne reste plus qu’un bloc, on effectue 10 tours de mélange, le résultat est
l’empreinte de la liste.
Voici le schéma d’une situation avec trois blocs : dans un premier temps il y a trois blocs
(A,B,C) ; dans un second temps il ne reste plus que deux blocs (B’ et C) ; à la fin il ne reste
qu’un bloc (C”) : c’est l’empreinte !
A B C liste
bloc 1 bloc 2 bloc 3
10 tours
addition
A’
B’ C
10 tours
addition
B”
C’
10 tours
C” empreinte
Exemple avec la liste [0, 1, 2, 3, 4, 5, 1, 1, 1, 1, 1, 1, 10, 10, 10, 10, 10, 10].
• Le premier bloc est [0, 1, 2, 3, 4, 5], son mélange à 10 tours est [98, 95, 86, 55, 66, 75].
• On ajoute ce mélange au second bloc [1, 1, 1, 1, 1, 1] (voir la fonction addition() de
l’activité 2).
• La liste restante est maintenant [99, 96, 87, 56, 67, 76, 10, 10, 10, 10, 10, 10].
• On recommence. Le nouveau premier bloc est [99, 96, 87, 56, 67, 76], son mélange à 10
tours vaut [60, 82, 12, 94, 6, 80], on l’ajoute au dernier bloc [10, 10, 10, 10, 10, 10] pour
obtenir (modulo 100) [70, 92, 22, 4, 16, 90].
202 BITCOIN
1. Vérification (facile).
Programme une fonction verification_preuve_de_travail(liste,preuve) qui
renvoie vrai si la solution preuve proposée convient pour liste. Utilise la fonction
est_plus_petit() de l’activité 2.
2. Recherche de solution (difficile).
Programme une fonction preuve_de_travail(liste) qui cherche un bloc preuve
solution à notre problème pour la liste donnée.
Indications.
• La méthode la plus simple est de prendre un bloc preuve de nombres au hasard et de
recommencer jusqu’à trouver une solution.
• Tu peux aussi tester systématiquement tous les blocs en commençant avec
[0,0,0,0,0,0], puis [0,0,0,0,0,1]. . . et t’arrêter au premier qui convient.
BITCOIN 203
preuve
(a) Initialise une variable globale Livre qui est une liste et contient au départ une preuve
nulle : Livre = [ [0,0,0,0,0,0] ] .
(b) Une transaction est une chaîne de caractères comprenant un nom et la somme à ajouter
(ou à retrancher) à son compte. Par exemple "Abel +25" ou "Barbara -45".
Programme une fonction ajout_transaction(transaction) qui ajoute la chaîne
de caractères transaction à la liste Livre. Par exemple après l’initialisa-
tion ajout_transaction("Camille +100"), Livre vaut [ [0,0,0,0,0,0],
204 BITCOIN
2. Dès qu’une transaction est ajoutée, il faut calculer et ajouter au livre de compte une preuve
de travail. Programme une fonction minage(), sans paramètre, qui ajoute une preuve de
travail au livre.
Voici comment faire :
• On prend la dernière transaction transaction, on la transforme en une liste d’entiers
par la fonction phrase_vers_liste() de l’activité 2.
• On prend la preuve de travail prec_preuve située juste avant cette transaction.
• On forme la liste liste composée d’abord des éléments de prec_preuve, puis des
éléments de la liste d’entiers obtenue en convertissant la chaîne transaction.
• On calcule une preuve de travail de cette liste.
• On ajoute cette preuve au livre de compte.
Par exemple si le livre se termine par :
[3,1,4,1,5,9], "Abel +35"
alors après calcul de la preuve de travail le livre se termine par exemple par :
[3,1,4,1,5,9], "Abel +35", [32,17,37,73,52,90]
On rappelle que la preuve de travail n’est pas unique et qu’en plus elle dépend de l’objectif
Max.
3. Une seule personne à la fois ajoute une preuve de travail. Par contre tout le monde a la
possibilité de vérifier que la preuve proposée est correcte (et devrait le faire). Écris une
fonction verification_livre(), sans paramètre, qui vérifie que la dernière preuve
ajoutée au Livre est valide.
4. Écris un livre de compte qui correspond aux données suivantes :
• On prend Max = [0,0,5] et au départ Livre = [ [0,0,0,0,0,0] ].
• "Alfred -100" (Alfred doit 100 bitcoins).
• Barnabé en reçoit 150.
• Chloé gagne 35 bitcoins.
Conclusion : imaginons que Alfred veuille tricher, il veut changer le livre de compte afin de
recevoir 100 bitcoins au lieu d’en devoir 100. Il doit donc changer la transaction le concernant
en "Alfred +100" mais il doit alors recalculer une nouvelle preuve de travail ce qui est
compliqué, surtout il doit aussi recalculer la preuve de la transaction de Barnabé et aussi celle
de la transaction de Chloé !
Quelqu’un qui veut modifier une transaction doit modifier toutes les preuves de travail suivantes.
Si chaque preuve demande suffisamment de temps de calcul ceci est impossible. Pour le bitcoin
chaque preuve demande énormément de calculs (trop pour une personne seule) et une nouvelle
preuve est à calculer toutes les 10 minutes. Il est donc impossible pour une personne de modifier
une transaction passée.
L’autre aspect du bitcoin que nous n’avons pas abordé, c’est de s’assurer de l’identité de chaque
BITCOIN 205
personne impliquée, afin que personne ne puisse récupérer l’argent d’un autre. Ceci est rendu
possible grâce à la cryptographie à clé privée/clé publique (système RSA). Chaque compte est
identifié par une clé publique (deux très grands entiers), ce qui garantit l’anonymat. Mais surtout,
seul celui qui possède la clé privée du compte (un grand entier) peut accéder à ses bitcoins.
Chapitre
23
Constructions aléatoires
Tu vas programmer deux méthodes pour construire des figures qui ressemblent à des algues
ou des coraux. Chaque figure est formée de petits blocs lancés au hasard et qui se collent les
uns aux autres.
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5
Par exemple à l’étape 4, le bloc lancé dans la colonne numéro 2 ne descend pas jusqu’en bas
mais reste « scotché » à son voisin, il se retrouve donc définitivement suspendu.
Le lancer aléatoire de centaines de blocs sur une grande grille produit de jolies formes géomé-
triques ressemblant à des algues.
indice j
i=0
0 0 0 0 1 0
i=1
0 0 1 0 0 0
indice i
0 0 1 0 0 0 i=2
0 0 1 1 0 0
i=3
0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1 1 0 0
0 0 1 0 0 0 0 0 1 0 0 0
0 0 1 1 0 0 0 0 1 1 0 0
0 1 2 3 4 5 0 1 2 3 4 5
Avant Après
0 0 0 1 1 0
0 1 1 1 0 0
0 0 1 0 0 1
0 0 1 1 0 1
Lancer de 10 blocs
Affichage statique. Programme l’affichage graphique des blocs à partir d’un tableau.
Indications.
• Utilise le module tkinter, voir la fiche « Statistique – Visualisation de données ».
• Tu peux rajouter un bouton qui lance un bloc (ou plusieurs d’un coup).
Affichage dynamique (facultatif et difficile). Programme l’affichage des blocs qui tombent.
CONSTRUCTIONS ALÉATOIRES 211
Indications.
• C’est beaucoup plus compliqué à programmer, mais très joli à voir !
• Pour le déplacement des blocs, inspire-toi du programme « Mouvement avec tkinter » à
la fin de cette fiche.
• Pour faire une « pluie de blocs » de façon régulière (par exemple tous les dixièmes de
secondes) : on fait descendre tous les blocs existant d’une case et on en fait apparaître un
nouveau sur la ligne du haut.
On obtient petit à petit une sorte d’arbre qui ressemble à du corail. Les calculs sont très longs
car beaucoup de blocs sortent de la grille ou mettent longtemps avant de se fixer (surtout au
début). En plus, on ne peut lancer les blocs qu’un par un.
Première partie.
1. Modélise de nouveau l’espace de travail par un tableau de n lignes et p colonnes contenant
des 0 ou des 1. Initialise toutes les valeurs à 0 sauf 1 au centre du tableau.
2. Programme une fonction est_dedans(i,j) qui détermine si la position (i, j) est bien
dans la grille (sinon c’est que le bloc est en train de sortir).
3. Programme une fonction est_libre(i,j) qui détermine si le bloc en position (i, j) peut
bouger (la fonction renvoie « vrai ») ou s’il est collé (la fonction renvoie « faux »).
4. Programme une fonction lancer_un_bloc(), sans paramètre, qui simule la création d’un
bloc et son déplacement aléatoire, jusqu’à ce qu’il se colle ou qu’il quitte la grille.
Indications.
• Le bloc est créé à une position aléatoire (i, j) de la grille.
• Tant que le bloc est dans la grille et libre de bouger :
CONSTRUCTIONS ALÉATOIRES 213
• Le point clé est que cette fonction sera exécutée une nouvelle fois après un court laps de
temps. La commande :
[Link](50,deplacer)
demande une nouvelle exécution de la fonction deplacer() après un court délai (ici 50
millisecondes).
• La répétition de petits déplacements simule le mouvement.
from tkinter import *
Largeur = 400
Hauteur = 200
root = Tk()
canvas = Canvas(root,width=Largeur,height=Hauteur,background="white")
[Link](fill="both", expand=True)
# Le rectangle à déplacer
rect = canvas.create_rectangle(x0,y0,x0+20,y0+20,width=2,fill="red")
# Fonction principale
def deplacer():
global x0, y0, dx, dy
x0 = x0 + dx # Nouvelle abscisse
y0 = y0 + dy # Nouvelle ordonnée
[Link](rect,x0,y0,x0+20,y0+20) # Déplacement
return
CONSTRUCTIONS ALÉATOIRES 215
# Boutons
bouton_deplacer=Button(root,text="Déplacer",width=20,
command=action_deplacer)
bouton_deplacer.pack(pady=10)
bouton_quitter = Button(root,text="Quitter",width=20,command=[Link])
bouton_quitter.pack(side=BOTTOM, pady=10)
[Link]()
C I N Q U I È M E PA R T I E
GUIDES
Chapitre
1. Test et boucles
une condition
deux points
if condition :
instruction_1 bloc d’instructions indenté
instruction_2 sera exécuté uniquement
... si la condition est vérifiée
instructions suivantes
suite du programme
if condition :
instruction bloc exécuté
instruction si la condition est vérifiée
...
else:
instruction bloc exécuté
... si la condition n’est pas vérifiée
instructions suivantes
220 GUIDE DE SURVIE PYTHON
une condition
deux points
while condition :
instruction_1 bloc d’instructions indenté
instruction_2 sera exécuté tant que
... la condition est vérifiée
instructions suivantes
suite du programme
2. Type de données
# Définition de la fonction
def ma_fonction (param) :
instruction_1
instruction_2
... un paramètre
return resultat
renvoie un résultat
# Appel de la fonction
x = 7
val = ma_fonction (x)
argument
appel de la fonction
résultat renvoyé
un ou plusieurs paramètres
def somme_produit(x,y):
""" Calcule la somme et le produit de deux nombres. """
S = x + y # Somme
P = x*y # Produit
return S, P # Renvoie les résultats
# Appel de la fonction
som, prod = somme_produit(3,7) # Résultats
GUIDE DE SURVIE PYTHON 223
# Boucle principale
while r != 0: # Tant que le reste n'est pas nul
r = r - 1 # Diminuer le reste
• Docstring. Tu peux décrire ce que fait une fonction en commençant par un docstring, c’est-à-dire
une description en français, entourée par trois guillemets. Par exemple :
def produit(x,y):
""" Calcule le produit de deux nombres
Entrée : deux nombres x et y
Sortie : le produit de x par y """
p = x * y
return p
def ma_fonction(x):
x = x + 1
return x
x = 7
print(ma_fonction(x))
print(x)
— La variable x est initialisée à 7.
— L’appel de la fonction ma_fonction(x) est donc la même chose que ma_fonction(7)
et renvoie logiquement 8.
— Que vaut la variable x à la fin ? La variable x est inchangée et vaut toujours 7 ! Même s’il y
a eu entre temps une instruction x = x + 1. Cette instruction a changé le x à l’intérieur
de la fonction, mais pas le x en dehors de la fonction.
• Les variables définies à l’intérieur d’une fonction sont appelées variables locales. Elles n’existent
pas en dehors de la fonction.
• Si une variable dans une fonction porte le même nom qu’une variable dans le programme
(comme le x dans l’exemple ci-dessus), il y a deux variables distinctes ; la variable locale
n’existant que dans la fonction.
Pour bien comprendre la portée des variables, tu peux colorier les variables globales d’une fonction
en rouge, et les variables locales avec une couleur par fonction. Le petit programme suivant définit
une fonction qui ajoute un, et une autre qui calcule le double.
variable globale
x = 7
def plus_un( x ):
x = x +1
variable locale
return x
def double( x ):
x = 2 * x
autre variable locale
return x
print( x )
print(plus_un( x ))
print(double( x ))
print( x )
Le programme affiche d’abord la valeur de x, donc 7, puis il ajoute un à 7, il affiche donc 8, puis il
affiche le double de x, donc 14. La variable globale x n’a jamais changé, le dernier affichage de x
est donc encore 7.
GUIDE DE SURVIE PYTHON 225
4. Modules
5. Erreurs
a = 3
b = 2
Python renvoie le message d’erreur IndentationError : unexpected indent. Il indique le numéro de
ligne où se situe l’erreur d’indentation, il pointe même à l’aide du symbole « ^ » l’endroit exact de
l’erreur.
• while x >= 0
x = x - 1
Python renvoie le message d’erreur SyntaxError : invalid syntax car il manque les deux points
après la condition while x >= 0 :
• chaine = Coucou le monde renvoie une erreur car il manque les guillemets pour définir
la chaîne de caractères.
GUIDE DE SURVIE PYTHON 227
def produit(a,b):
return a*b
Renvoie une erreur NameError : name ’produit’ is not defined car une fonction doit être définie
avant d’être utilisée.
228 GUIDE DE SURVIE PYTHON
5.5. Exercice
Corrige le code ! Python doit afficher 7 5 9.
a == 7
if (a = 2) or (a >= 5)
b = a - 2
c = a + 2
else
b = a // 2
c = 2 * a
print(a b c)
n = 10
while n != "0":
n = n - 1
print(n)
Avec une boucle « tant que » il faut prendre grand soin de bien écrire la condition et de vérifier
qu’elle finit pas être fausse. Ici, elle est mal formulée, cela devrait être while n!= 0:.
Chapitre
Principales fonctions
25
1. Mathématiques
Opérations classiques
• a + b, a - b, a * b opérations classiques
• a / b division « réelle » (renvoie un nombre flottant)
• a // b quotient de la division euclidienne (renvoie un entier)
• a % b reste de la division euclidienne, appelé a modulo b
• abs(x) valeur absolue
• x ** n puissance x n
• 4.56e12 pour 4.56 × 1012
Module « math »
L’usage d’autres fonctions mathématiques nécessite le recours au module math qui s’appelle par la
commande :
from math import *
p
• sqrt(x) racine carrée x
• cos(x), sin(x), tan(x) fonctions trigonométriques cos x, sin x, tan x en radians
• pi valeur approchée de π = 3.14159265 . . .
• floor(x) entier juste en-dessous de x
• ceil(x) entier juste au-dessus de x
• gcd(a,b) pgcd de a et de b
Module « random »
Le module random génère des nombres de façon pseudo-aléatoire. Il s’appelle par la commande :
from random import *
• random() à chaque appel, renvoie un nombre flottant x au hasard vérifiant 0 6 x < 1.
• randint(a,b) à chaque appel, renvoie un nombre entier n au hasard vérifiant a 6 n 6 b.
• choice(liste) à chaque appel, tire au hasard un élément de la liste.
• [Link]() mélange la liste (la liste est modifiée).
232 PRINCIPALES FONCTIONS
Écriture binaire
• bin(n) renvoie l’écriture binaire de l’entier n sous la forme d’une chaîne. Exemple : bin(17)
renvoie '0b10001'.
• Pour écrire directement un nombre en écriture binaire, il suffit d’écrire le nombre en commençant
par 0b (sans guillemets). Par exemple 0b11011 vaut 27.
2. Booléens
Un booléen est une donnée qui prend soit la valeur True (« Vrai »), soit la valeur False (« Faux »).
Comparaisons
Les tests de comparaison suivants renvoient un booléen.
• a == b test d’égalité
• a < b test inférieur strict
• a <= b test inférieur large
• a > b ou a >= b test supérieur
• a != b test de non égalité
Ne pas confondre « a = b » (affectation) et « a == b » (test d’égalité).
3. Chaînes de caractères I
Chaînes
• "A" ou 'A' un caractère
• "Python" ou 'Python' une chaîne de caractères
• len(chaine) la longueur de la chaîne. Exemple : len("Python") renvoie 6.
• chaine1 + chaine2 concaténation.
Exemple : "J aime bien" + "Python" renvoie "J aime bienPython".
• chaine[i] renvoie le i-ème caractère de chaine (la numérotation commence à 0).
Exemple avec chaine = "Python", chaine[1] vaut "y". Voir le tableau ci-dessous.
Lettre P y t h o n
Rang 0 1 2 3 4 5
Conversion nombre/chaîne
• Chaîne. str(nombre) convertit un nombre (entier ou flottant) en une chaîne. Exemples :
str(7) renvoie la chaîne "7" ; str(1.234) renvoie la chaîne "1.234".
PRINCIPALES FONCTIONS 233
Sous-chaînes
• chaine[i:j] renvoie la sous-chaîne des caractères de rang i à j − 1 de chaine.
Exemple : avec chaine = "Ceci est une chaine", chaine[2:6] renvoie "ci e".
• chaine[i:] renvoie les caractères de rang i jusqu’à la fin de chaine.
Exemple : chaine[5:] renvoie "est une chaine".
• chaine[:j] renvoie les caractères du début jusqu’au rang j − 1 de chaine. Exemple :
chaine[:4] renvoie "Ceci".
Mise en forme
La méthode format() permet de mettre en forme du texte ou des nombres. Cette fonction renvoie
une chaîne de caractères.
• Texte
Test Test Test
— '{:10}'.format('Test') alignement à gauche (sur 10 caractères)
— '{:>10}'.format('Test') alignement à droite
— '{:^10}'.format('Test') centré
• Entier
456 456 000456
— '{:d}'.format(456) entier
— '{:6d}'.format(456) alignement à droite (sur 6 caractères)
— '{:06d}'.format(456) ajout de zéros non significatifs (sur 6 caractères)
• Nombre flottant
3.141593 3.14159265 3.1416 003.1416
— '{:f}'.format(3.141592653589793) nombre flottant
— '{:.8f}'.format(3.141592653589793) 8 chiffres après la virgule
— '{:8.4f}'.format(3.141592653589793) sur 8 caractères avec 4 chiffres après la
virgule
— '{:08.4f}'.format(3.141592653589793) ajout de zéros non significatifs
234 PRINCIPALES FONCTIONS
4. Chaînes de caractères II
Encodage
• chr(n) renvoie le caractère associé au numéro de code ASCII/unicode n. Exemple : chr(65)
renvoie "A" ; chr(97) renvoie "a".
• ord(c) renvoie le numéro de code ASCII/unicode associé au caractère c. Exemple :
ord("A") renvoie 65 ; ord("a") renvoie 97.
Le début de la table des codes ASCII/unicode est donné ci-dessous.
39 ’ 49 1 59 ; 69 E 79 O 89 Y 99 c 109 m 119 w
Majuscules/minuscules
• [Link]() renvoie une chaîne en majuscules.
• [Link]() renvoie une chaîne en minuscules.
Chercher/remplacer
• sous_chaine in chaine renvoie « vrai » ou « faux » si sous_chaine apparaît dans
chaine.
Exemple : "PAS" in "ETRE OU NE PAS ETRE" vaut True.
• [Link](sous_chaine) renvoie le rang auquel la sous-chaîne a été trouvée (et -1
sinon).
Exemple : avec chaine = "ABCDE", [Link]("CD") renvoie 2.
• [Link](sous_chaine,nouv_sous_chaine) remplace chaque occurrence de
la sous-chaîne par la nouvelle sous-chaîne.
Exemple : avec chaine = "ABCDE", [Link]("CD","XY") renvoie "ABXYE".
Séparer/regrouper
PRINCIPALES FONCTIONS 235
5. Listes I
Construction d’une liste
Exemples :
• liste1 = [5,4,3,2,1] une liste de 5 entiers.
• liste2 = ["Vendredi","Samedi","Dimanche"] une liste de 3 chaînes.
• liste3 = [] la liste vide.
• list(range(n)) liste des entiers de 0 à n − 1.
• list(range(a,b)) liste des entiers de a à b − 1.
• list(range(a,b,saut)) liste des entiers de a à b − 1, avec un pas donné par l’entier
saut.
Accéder à un élément
• liste[i] renvoie l’élément de la liste de rang i. Attention, le rang commence à 0.
Exemple : liste = ["A","B","C","D","E","F"] alors liste[2] renvoie "C".
• nouv_liste = liste + [element] fournit une nouvelle liste avec un élément en plus
à la fin. Exemple : [1,2,3,4] + [5] vaut [1,2,3,4,5].
• [element] + liste renvoie une liste où l’élément est ajouté au début. Exemple : [5]
+ [1,2,3,4] vaut [5,1,2,3,4].
• liste1 + liste2 concatène les deux listes. Exemple : avec liste1 = [4,5,6] et
liste2 = [7,8,9] alors liste1 + liste2 vaut [4,5,6,7,8,9].
Exemple de construction. Voici comment construire la liste qui contient les premiers carrés :
6. Listes II
Mathématiques
• max(liste) renvoie le plus grand élément. Exemple : max([10,16,13,14]) renvoie 16.
• min(liste) renvoie le plus petit élément. Exemple : min([10,16,13,14]) renvoie 10.
• sum(liste) renvoie la somme de tous les éléments. Exemple : sum([10,16,13,14])
renvoie 53.
Ordonner
• sorted(liste) renvoie la liste ordonnée des éléments.
Exemple : sorted([13,11,7,4,6,8,12,6]) renvoie la liste [4,6,6,7,8,11,12,13].
• [Link]() ne renvoie rien mais par contre la liste liste est maintenant ordonnée.
Supprimer un élément
Trois méthodes.
• [Link](element) supprime la première occurrence trouvée.
Exemple : liste = [2,5,3,8,5], la commande [Link](5) modifie la liste qui
maintenant vaut [2,3,8,5] (le premier 5 a disparu).
• del liste[i] supprime l’élément de rang i (la liste est modifiée).
• element = [Link]() supprime le dernier élément de la liste et le renvoie. C’est l’opé-
ration « dépiler ».
Liste de listes
Exemple :
tableau = [ [2,14,5], [3,5,7], [15,19,4], [8,6,5] ]
correspond au tableau :
indice j
i=0 2 14 5
i=1 3 5 7
indice i
i=2 15 19 4
i=3 8 6 5
Alors tableau[i] renvoie la sous-liste de rang i, et tableau[i][j] renvoie l’élément situé dans
la sous-liste de rang i, au rang j de cette sous-liste. Par exemple :
• tableau[0] renvoie la sous-liste [2,14,5].
• tableau[1] renvoie la sous-liste [3,5,7].
• tableau[0][0] renvoie l’entier 2.
• tableau[0][1] renvoie l’entier 14.
• tableau[2][1] renvoie l’entier 19.
Un tableau de n lignes et p colonnes.
• tableau = [[0 for j in range(p)] for i in range(n)] initialise un tableau et
le remplit de 0.
• tableau[i][j] = 1 modifie une valeur du tableau (celle à l’emplacement (i, j)).
7. Entrée/sortie
Affichage
• print(chaine1,chaine2,chaine3,...) affiche des chaînes ou des objets. Exemple :
print("Valeur =",14) affiche Valeur = 14. Exemple : print("Ligne 1 \n Ligne
2") affiche sur deux lignes.
• Séparateur. print(...,sep="...") change le séparateur (par défaut le séparateur est
le caractère espace). Exemple : print("Bob",17,13,16,sep="; ") affiche Bob; 17;
13; 16.
• Fin de ligne. print(...,end="...") change le caractère placé à la fin (par défaut c’est le
saut de ligne \n). Exemple print(17,end="") puis print(89) affiche 1789 sur une seule
ligne.
Entrée clavier
input() met le programme en pause et attend de l’utilisateur un message au clavier (qu’il
termine en appuyant sur la touche « Entrée »). Le message est une chaîne de caractères.
PRINCIPALES FONCTIONS 239
Voici un petit programme qui demande le prénom et l’âge de l’utilisateur et affiche un message du
style « Bonjour Kevin » puis « Tu es mineur/majeur » selon l’âge.
prenom = input("Comment t'appelles-tu ? ")
print("Bonjour",prenom)
8. Fichiers
Commande
• fic = open("mon_fichier.txt","r") ouverture en lecture ("r" = read).
• fic = open("mon_fichier.txt","w") ouverture en écriture ("w" = write). Le fichier
est créé s’il n’existe pas, s’il existait le contenu précédent est d’abord effacé.
• fic = open("mon_fichier.txt","a") ouverture en écriture, les données seront écrites
à la fin des données actuelles ("a" = append).
• [Link]("une ligne") écriture dans le fichier.
• [Link]() lit tout le fichier (voir plus bas pour autre méthode).
• [Link]() lit toutes les lignes (voir plus bas pour autre méthode).
• [Link]() fermeture du fichier.
[Link]("Bonjour le monde\n")
ligne = "Coucou\n"
[Link](ligne)
[Link]()
print(ligne)
[Link]()
9. Tortue
Le module turtle s’appelle par la commande :
from turtle import *
Principales commandes
• forward(longueur) avance de longueur pas
• backward(longueur) recule
• right(angle) tourne vers la droite selon l’angle donné en degrés
• left(angle) tourne vers la gauche
• setheading(direction) s’oriente dans une direction (0 = droite, 90 = haut, −90 = bas,
180 = gauche)
• goto(x,y) se déplace jusqu’au point (x, y)
• setx(newx) change la valeur de l’abscisse (déplacement horizontal)
• sety(newy) change la valeur de l’ordonnée (déplacement vertical)
• down() abaisse le stylo
• up() relève le stylo
• width(epaisseur) change l’épaisseur du trait
• color(couleur) change la couleur du trait : "red", "green", "blue", "orange". . .
• position() renvoie la position (x, y) de la tortue
• heading() renvoie la direction angle vers laquelle pointe la tortue
• towards(x,y) renvoie l’angle entre l’horizontale et le segment commençant à la tortue et
finissant au point (x, y)
• speed("fastest") vitesse maximale de déplacement
• exitonclick() termine le programme dès que l’on clique
Plusieurs tortues
Voici un exemple de programme avec deux tortues.
[Link]('red')
[Link]('blue')
[Link](100)
[Link](90)
[Link](100)
10. Matplotlib
Avec le module matplotlib il est très facile de tracer une liste. Voici un exemple.
liste1 = [3,5,9,8,0,3]
liste2 = [4,7,7,2,8,9]
[Link](liste1,color="red")
[Link](liste2,color="blue")
[Link]()
[Link]()
Principales fonctions.
• [Link](liste) trace les points d’une liste (sous la forme (i, `i )) et les joint.
• [Link](listex,listey) trace les points d’une liste (sous la forme (x i , yi ) où x i parcourt
la première liste et yi la seconde).
• [Link](x,y,color='red',s=100) affiche un point en (x, y) (d’une grosseur s).
• [Link]() trace une grille.
242 PRINCIPALES FONCTIONS
11. Tkinter
11.1. Graphiques
Pour afficher ceci :
le code est :
# Module tkinter
from tkinter import *
# Fenêtre tkinter
root = Tk()
# Un rectangle
canvas.create_rectangle(50,50,150,100,width=2)
# Un ovale
canvas.create_oval(50,110,180,160,width=4)
PRINCIPALES FONCTIONS 243
# Du texte
canvas.create_text(400,75,text="Bla bla bla bla",fill="blue")
# Ouverture de la fenêtre
[Link]()
Quelques explications :
• Le module tkinter nous permet de définir des variables root et canvas qui définissent
une fenêtre graphique (ici de largeur 800 et de hauteur 600 pixels). On décrit ensuite tout
ce que l’on veut ajouter dans la fenêtre. Et enfin, la fenêtre est affichée par la commande
[Link]() (tout à la fin).
• Attention ! Le repère graphique de la fenêtre a son axe des ordonnées dirigé vers le bas. L’origine
(0, 0) est le coin en haut à gauche (voir la figure ci-dessous).
• Commande pour tracer un rectangle : create_rectangle(x1,y1,x2,y2) ; il suffit de pré-
ciser les coordonnées (x 1 , y1 ) et (x 2 , y2 ) de deux sommets opposés. L’option width ajuste
l’épaisseur du trait, outline définit la couleur de ce trait et fill définit la couleur de rem-
plissage.
• Une ellipse est tracée par la commande create_oval(x1,y1,x2,y2), où (x 1 , y1 ), (x 2 , y2 )
sont les coordonnées de deux sommets opposés d’un rectangle encadrant l’ellipse voulue (voir
la figure). On obtient un cercle lorsque le rectangle correspondant est un carré.
• Le texte est affiché par la commande canvas.create_text() en précisant les coordonnées
(x, y) du point à partir duquel on souhaite afficher le texte.
(0, 0) x
(x 1 , y1 )
(x 2 , y2 )
(x 1 , y1 )
(x 2 , y2 )
y
Portion de cercle. La fonction create_arc() n’est pas très intuitive. Il faut penser que l’on
dessine un cercle, en précisant les coordonnées de deux sommets opposés d’un carré qui l’entoure,
puis en précisant l’angle de début et l’angle du secteur (en degrés).
canvas.create_arc(x1,y1,x2,y2,start=debut_angle,extent=mon_angle)
244 PRINCIPALES FONCTIONS
extent=θ
(x 1 , y1 )
start=θ0
(x 2 , y2 )
11.2. Boutons
Il est plus ergonomique d’afficher des fenêtres dans lesquelles les actions sont exécutées en cliquant
sur des boutons.
Voici un petit programme qui affiche une fenêtre avec deux boutons. Le premier bouton change la
couleur du rectangle, le second termine le programme.
Le code est :
root = Tk()
canvas = Canvas(root, width=400, height=200, background="white")
[Link](fill="both", expand=True)
def action_bouton():
[Link]("all") # Efface tout
couleurs = ["red","orange","yellow","green","cyan","blue","violet"]
coul = choice(couleurs) # Couleur au hasard
PRINCIPALES FONCTIONS 245
canvas.create_rectangle(100,50,300,150,width=5,fill=coul)
return
bouton_couleur=Button(root,text="Afficher",width=20,command=action_bouton)
bouton_couleur.pack()
bouton_quitter = Button(root,text="Quitter",width=20,command=[Link])
bouton_quitter.pack()
[Link]()
Quelques explications :
• On crée un bouton par la commande Button. L’option text personnalise le texte qui s’affiche
sur le bouton. On ajoute le bouton créé à la fenêtre par la méthode pack.
• Le plus important est l’action associée au bouton ! C’est l’option command qui reçoit le nom
de la fonction à exécuter lorsque le bouton est cliqué. Pour notre exemple command =
action_bouton associe au clic sur le bouton un changement de couleur.
• Attention ! il faut donner le nom de la fonction sans parenthèses : commande=ma_fonction
et pas command = ma_fonction().
• Pour associer au bouton « Quitter » la fermeture du programme, l’argument est command =
[Link].
• La commande [Link]("all") efface tous les dessins de notre fenêtre graphique.
11.3. Texte
Voici comment afficher du texte avec Python et le module des fenêtres graphiques tkinter.
Le code est :
# Ouverture de la fenêtre
[Link]()
Quelques explications :
• Le texte est affiché par la fonction canvas.create_text(). Il faut préciser les coordonnées
(x, y) du point à partir duquel on souhaite afficher le texte.
• L’option text permet de passer la chaîne de caractères à afficher.
• L’option anchor permet de préciser le point d’ancrage du texte, anchor=NW signifie que la
zone de texte est ancrée au point Nord-Ouest (NW) (voir la figure ci-dessous).
• L’option fill permet de préciser la couleur du texte.
• L’option font permet de définir la fonte (c’est-à-dire le style et la taille des caractères). Voici
des exemples de fontes, à toi de les tester :
— Font(family="Times", size=20)
— Font(family="Courier", size=16, weight="bold") en gras
— Font(family="Helvetica", size=16, slant="italic") en italique
(0, 0) x
(x 1 , y1 ) ancre Nord-Ouest
(x 2 , y2 )
# Fenêtre
root = Tk()
canvas = Canvas(root, width=800, height=600, background="white")
[Link](side=LEFT, padx=5, pady=5)
canvas.focus_set()
x = event.x
y = event.y
canvas.create_rectangle(x,y,x+10,y+10,fill="red")
print("Clic à x =",x,", y =",y)
return
# Association clic/action
[Link]("<Button-1>", action_clic_souris)
# Lancement
[Link]()
Voici quelques explications :
• La création de la fenêtre est habituelle. Le programme se termine par le lancement de la fenêtre
avec la commande mainloop().
• Le premier point clé est d’associer un clic de souris à une action, c’est ce que fait la ligne
[Link]("<Button-1>", action_clic_souris)
Chaque fois que le bouton gauche de la souris est cliqué, Python exécute la fonction
action_clic_souris. Note qu’il n’y a pas de parenthèses pour l’appel à la fonction.
• Second point clé : la fonction action_clic_souris récupère les coordonnées du clic et ici
ensuite fait deux choses : elle affiche un petit rectangle à l’endroit du clic et affiche dans la
fenêtre du terminal les coordonnées (x, y).
• Les coordonnées x et y sont exprimées en pixels ; (0, 0) désigne le coin en haut à gauche de la
fenêtre (la zone délimitée par canvas).
11.5. Mouvement
Voici un programme qui fait se déplacer un petit carré en le faisant rebondir sur les bords de la
fenêtre.
• Cet objet est (un petit peu) déplacé par la fonction deplacer() qui décale le rectangle de
(dx,dy).
• Le point clé est que cette fonction sera exécutée une nouvelle fois après un court laps de temps.
La commande :
[Link](50,deplacer)
demande une nouvelle exécution de la fonction deplacer() après un court délai (ici 50
millisecondes).
• La répétition de petits déplacements simule le mouvement.
Largeur = 400
Hauteur = 200
root = Tk()
canvas = Canvas(root, width=Largeur, height=Hauteur, background="white")
[Link](fill="both", expand=True)
# Le rectangle à déplacer
rect = canvas.create_rectangle(x0,y0,x0+20,y0+20,width=2,fill="red")
# Fonction principale
def deplacer():
global x0, y0, dx, dy
x0 = x0 + dx # Nouvelle abscisse
y0 = y0 + dy # Nouvelle ordonnée
[Link](rect,x0,y0,x0+20,y0+20) # Déplacement
return
PRINCIPALES FONCTIONS 249
# Boutons
bouton_deplacer=Button(root,text="Déplacer",width=20,command=action_deplacer)
bouton_deplacer.pack(pady=10)
bouton_quitter = Button(root,text="Quitter",width=20,command=[Link])
bouton_quitter.pack(side=BOTTOM, pady=10)
[Link]()
Chapitre
26
Notes et références
Tu trouveras ici des commentaires et des indications de lectures sur chacune des activités.
Ressources générales
• Apprendre à programmer avec Python 3 de Gérard Swinnen, aux éditions Eyrolles. C’est un des
livres de référence en français pour débuter. La seconde moitié du livre contient des notions
beaucoup plus avancées. Le livre est disponible gratuitement en téléchargement, selon la licence
Creative Commons BY-NC-SA :
[Link]/swi/[Link]
• La documentation officielle de Python contient des tutoriels et les explications de chacune des
fonctions. Malheureusement certaines pages sont en anglais
[Link]/fr/3/
• Wikipédia est une source fiable pour en savoir plus sur certaines notions (principalement les
projets) mais le niveau n’est pas toujours adapté à un lycéen.
• Internet et en particulier les forums ont bien souvent la réponse aux questions que tu te poses !
• Les plus fondus d’entre vous peuvent participer au projet Euler (en anglais) qui propose une
liste d’énigmes mathématico-informatique. Accrochez-vous !
[Link]
252 NOTES ET RÉFÉRENCES
1. Premiers pas
L’apprentissage d’un langage de programmation peut être très difficile. C’est assez dur d’apprendre
tout seul dans son coin. Il n’est pas rare de reste bloquer plusieurs heures pour une bête erreur de
syntaxe. Il faut commencer modestement, ne pas hésiter à recopier du code déjà écrit par d’autres,
être persévérant et demander de l’aide rapidement !
4. Fonctions
Assez rapidement il faut comprendre la structure d’un programme informatique : on décompose
le programme en blocs de définitions et d’actions simples. On regroupe des actions simples dans
des actions intermédiaires. Et à la fin le programme principal consiste juste à exécuter quelques
bonnes fonctions.
Les arguments/paramètres d’une fonction sont d’un apprentissage délicat. On peut définir une
fonction par def fonc(x): et l’appeler par fonc(y). Le x correspond à une variable mathéma-
tique muette. En informatique, on préfère parler de la portée de la variable qui peut être locale ou
globale.
Ce que l’on peut retenir, c’est que tout ce qui passe à l’intérieur d’une fonction n’est pas accessible en
dehors de la fonction. Il faut juste utiliser ce que renvoie la fonction. Il faut s’interdire l’utilisation
de global dans un premier temps.
Dernier point, il est vraiment important de commenter abondamment ton code et de bien expliquer
ce que font tes fonctions. Si tu définis une fonction fonc(x) : prévois trois lignes de commentaires
pour (a) dire ce que fait cette fonction, (b) dire quelle entrée est attendue (x doit être un entier ?
un nombre flottant ? positif ?. . . ), (c) dire ce que renvoie la fonction.
Il faut aussi commenter les points principaux du code, donner des noms bien choisis aux variables.
Tu seras bien content d’avoir un code lisible lorsque tu reliras ton code plus tard !
Un bon informaticien devrait vérifier que le paramètre passé en argument vérifie bien l’hypothèse
attendue. Par exemple si fonc(x) est définie pour un entier x et que l’utilisateur transmet une
chaîne de caractères, alors un gentil message d’avertissement devrait être envoyé à l’utilisateur
sans faire échouer tout le programme ! Les commandes assert, try/except permettent de gérer
ce genre de problème. Pour notre part, nous nous abstiendrons de ces vérifications en supposant
que l’utilisateur/programmeur utilise les fonctions et les variables en bonne intelligence !
7. Listes I
Python est particulièrement souple et agile pour l’utilisation des listes. Les « vieux » langages
n’autorisaient souvent que les listes contenant un seul type d’élément, et pour parcourir une liste il
fallait toujours procéder ainsi :
for i in range(len(liste)):
print(liste[i])
Alors que :
for element in liste:
print(element)
est beaucoup plus naturel !
Le tri d’une liste est une opération fondamentale en informatique. Imaginerait-on un dictionnaire
contenant 60 000 mots, mais non classés par ordre alphabétique ? Ordonner une liste est une
opération difficile, il existe beaucoup d’algorithmes de tri. L’algorithme du tri à bulles, présenté ici
est l’un des plus simples. Programmer des algorithmes plus rapides au lycée est un beau challenge :
il faut comprendre la récursivité et la notion de complexité.
9. Fichiers
Les fichiers permettent de faire communiquer Python avec le monde extérieur : on peut par
exemple récupérer un fichier de notes pour en calculer les moyennes et produire un bulletin pour
chaque élève. Pour les plus avancés d’entre vous les fichiers sont une bonne occasion d’utiliser la
gestion des erreurs avec try/except.
Les activités sur les images sont sympathiques et ces formats d’images seront utilisés par la suite,
même si ce format a le gros désavantage de produire des fichiers de grande taille. Néanmoins
ils sont standards et reconnus par les logiciels d’images (Gimp par exemple). Notez que certains
logiciels écrivent des fichiers avec une seule donnée par ligne (ou bien toutes les données sur une
seule ligne). C’est un bon exercice d’implémenter la lecture de tous les formats possibles !
11. Binaire I
La première difficulté avec l’écriture binaire c’est de bien faire la différence entre un nombre et
l’écriture du nombre. Nous sommes tellement habitués à l’écriture décimale que l’on a oublié son
origine, 1234 c’est juste 1 × 1000 + 2 × 100 + 3 × 10 + 4 × 1.
Comme les ordinateurs travaillent avec des 0 et 1 il faut être à l’aise avec l’écriture binaire. Le
passage à l’écriture binaire n’est pas très difficile, il est tout de même préférable de faire quelques
exemples à la main avant de s’attaquer à la programmation.
On utilisera l’écriture binaire pour d’autres problèmes sur le principe suivant : vous avez 4 inter-
rupteurs alors [Link] signifie que vous actionnez le premier et le dernier interrupteur et pas les
autres.
256 NOTES ET RÉFÉRENCES
12. Listes II
Les listes sont tellement utiles que Python possède toute une syntaxe efficace pour les gérer : le
tranchage des listes et les listes par compréhension. On pourrait bien sûr s’en passer (c’est d’ailleurs
le cas pour la plupart des autres langages) mais ce serait dommage. Nous aurons aussi besoin de
listes de listes et en particulier de tableaux à deux dimensions pour afficher de belles images.
13. Binaire II
Il y a 10 sortes de personnes, celles qui comprennent le binaire et les autres !
5 4
+ 3
18. L-système
On retrouve le thème « chercher/remplacer » mais cette fois avec une vision géométrique. Les
figures obtenues sont belles, faciles à programmer à l’aide de la tortue, mais le plus joli c’est de
voir le tracé en direct des L-systèmes. Pour les L-systèmes définis par des expressions contenant
des crochets on retrouve la notion de pile.
Les formules sont tirées du livre The algorithmic beauty of plants, par P. Prusinkiewicz et A. Linden-
mayer (Springer-Verlag, 2004) en accès libre ici : The algorithmic beauty of plants (pdf).
258 NOTES ET RÉFÉRENCES
Les illustrations qui débutent chaque partie de ce livre sont des itérations du L-système appelé la
courbe de Hilbert et défini par :
depart = "X" regle1 = ("X","gYAdXAXdAYg")
regle2 = ("Y","dXAgYAYgAXd")
22. Bitcoin
Avant de placer toutes ses économies dans des bitcoins mieux vaut en comprendre le fonctionne-
ment ! Les activités présentées ici ont pour but de présenter une version (très) simplifiée de la
blockchain qui est à la base de cette monnaie virtuelle. Le principe de la blockchain et de la preuve
de travail ne sont pas si compliqués, tu trouveras des explications plus détaillées dans les articles
de Jean-Paul Delahaye parus dans la revue Pour la science :
• Bitcoin, la cryptomonnaie (2013) ([Link]/∼jdelahay/pls/2013/[Link])
• Les preuves de travail (2014) ([Link]/j̃delahay/pls/2014/[Link])
• Du bitcoin à Ethereum : l’ordinateur-monde (2016) ([Link]/j̃delahay/pls/2016/[Link])
Vous pouvez récupérer l’intégralité des codes Python des activités ainsi que tous les fichiers
sources sur la page GitHub d’Exo7 : « GitHub : Python au lycée ».
Les vidéos des cours avec des explications pas à pas et la présentation des projets sont disponibles
depuis la chaîne Youtube : « Youtube : Python au lycée ».
Exo7
Ce livre est diffusé sous la licence Creative Commons – BY-NC-SA – 4.0 FR.
Sur le site Exo7 vous pouvez télécharger gratuitement le livre en couleur.
Index
π, 7 quitter, 99
**, 3 tant que, 44
+=, 46 bouton, 80
=, 4, 28 break, 99
#, 5
!=, 28 caractère, 51
//, 43 carré magique, 112
<=, 28 ceil, 7
==, 28 chaîne, 51, 86
>=, 28 caractères, 188
%, 43 majuscule, 36
regrouper, 137
abs, 7 séparer, 136
ADN, 55 chercher, 127
affectation, 4, 5, 28 choice, 86
and, 29 chr, 57
angle, 94 clic, 180
append, 63 close, 85
argument, 37, 158 codage des caractères, 56
ascii, 57 commentaire, 5
concaténation, 36, 51, 65
bin, 105 conjecture de Goldbach, 95
binaire, 101, 117, 188 cos, 7
bitcoin, 195 crible d’Ératosthène, 68
bits, 102 csv, 87
blockchain, 197
booléen, 28 def, 33
boucle degrés, 94
pour, 8, 53, 64 del, 66
dépiler, 133, 163 hasard, 27, 123
distance, 54, 92 hash, 199
diviseur, 46
division euclidienne, 3, 43 if, 25
docstring, 37 image, 89, 167
down, 14 import, 6
in, 8, 53, 109, 127
écart-type, 76 indentation, 8
écriture index, 109, 127
binaire, 101, 117, 188 input, 26
décimale, 29, 101 int, 26, 86
polonaise, 140 intérêts, 64
else, 25 isdigit, 137
empiler, 133
jeu de la vie, 175
entrée, 26
join, 137
espérance, 123
et, 29, 118 left, 14
eval, 146 len, 51, 64
expression rationnelle, 128 list, 9, 188
liste, 63, 109
facteur premier, 68 ajouter, 63, 65
False, 28 de listes, 110
fenêtre, 76 fusionner, 65
fichier, 85 inverser, 66
find, 127 longueur, 64
flocon de Koch, 159 par compréhension, 109
floor, 7 sous-liste, 65
fonction, 33 supprimer, 66
argument, 37 trancher, 109
argument optionnel, 158 trier, 67
de hachage, 199 lois de Morgan, 119
docstring, 37 L-système, 157
paramètre, 34
return, 37, 223 majuscule, 36
fonte, 148 markdown, 149
for, 8, 53, 64 math, 6
forward, 14 matplotlib, 69
max, 76
gcd, 7 médiane, 82
global, 134 min, 75
goto, 14 minage, 202
graphe, 183 module, 6
graphique, 13, 69, 76 math, 6
matplotlib, 69 range, 9
random, 27 regex, 128
re, 128 remove, 66
time, 196 remplacer, 127, 157
timeit, 48 replace, 128
tkinter, 76, 147, 180, 213 reste, 3, 43
turtle, 13 return, 33, 37, 223
modulo, 3, 43 reverse/reversed, 66
moyenne, 75, 83 right, 14
round, 7
nombre flottant, 3 rvb/rgb, 90, 92
nombre premier, 46, 68
non, 29, 118 shuffle, 113
None, 56 si/alors, 25
not, 29 sin, 7
not in, 53 sinon, 25
sort/sorted, 67
open, 85 souris, 180
opération logique, 29, 118 split, 136
or, 29 sqrt, 6
ord, 57 str, 27, 51, 85
ou, 29, 118 sum, 75
palindrome, 55, 117 tableau, 110
paramètre, 34 temps de calcul, 48, 196
pbm/pgm/ppm, 89, 170 time, 196
pgcd, 7 timeit, 48
pi, 7 tir balistique, 70
pile, 162 tkinter, 76, 147, 180, 213
plot, 70 tortue, 13, 38, 157
pop, 163 tri, 66
ppcm, 7 triangle, 29
preuve de travail, 195 triangle de Sierpinski, 16, 161
print, 4 True, 28
puissance, 3 try/except, 100
puissances de 2, 102 turtle, 13
quartiles, 82 unicode, 57, 151
quotient, 43 up, 14
upper, 36
racine carrée, 6, 97
radians, 94 valeur absolue, 7
randint, 27 variable, 4
random, 27 globale, 134
locale, 42 while, 44
variance, 76 write, 85