Algorithmique appliquée
1 Edupython
1.1 Python3
1.1.1 Généralités
Nous programmerons en Python 3 qui est un language libre de programmation dont le site officiel – en anglais – est https://docs.python.org/3/ (les exemples de la documentation de la librairie python disponible à l'adresse https://docs.python.org/3/library/ peuvent vous intéresser).
Python permet un développement rapide d'applications (language interprété faiblement typé) dans des domaines très variés (voir par exemple https://github.com/trending/python) en mettant à disposition plusieurs paradigmes de programmation (programmation orientée objet, programmation fonctionnelle, programmation impérative, …).
Attention: il existe des différences notables entre la version 2 et la version 3 du language Python!
1.1.2 Indentation
On appelle indentation la suite d'espaces et/ou de tabulations en début de ligne. En python on n'utilisera jamais de tabulations (heureusement edupython convertit automatiquement une tabulation en une série de 4 espaces).
En python l'indentation est significative: ajouter ou supprimer des espaces en début de ligne peut modifier l'exécution d'un programme ou même générer une erreur de syntaxe (ce qui signifie q'une tentaive d'exécution du programme échouera sans qu'aucune instruction ne soit exécutée).
Plus précisément l'indentation permet de regrouper plusieurs instructions en un seul bloc syntaxique. Ainsi dans le script suivant
def nbr_chiffres(p): if type(p) != int: print("Fournir un nombre entier SVP") return None elif p<0: print("Fournir un nombre positif SVP") return None elif 0 <= p < 10: return 1 elif 10<= p < 100: return 2 elif 100<= p < 1000: return 3 else: print("Fournir un nombre <1000 SVP") return None
- les lignes 2 à 16 forment un bloc syntaxique;
- les lignes 3 à 4 forment un bloc syntaxique;
- la ligne 9 forme un bloc syntaxique;
- la ligne 13 forme un bloc syntaxique;
- les lignes 15 à 16 forment un bloc syntaxique.
1.2 Présentation d'Edupython
Tout éditeur de texte peut être utilisé pour écrire un programmable en Python mais nous utiliserons exclusivement le logiciel Edupython téléchargable à l'adresse http://edupython.tuxfamily.org/ et qui à l'avantage d'intégrer:
- un éditeur adapté (coloration syntaxique, mise en évidence des erreurs de syntaxe, mise en évidence des parenthèses appairées, );
- un interpréteur Python3 (le composant qui exécute le programme);
- un débogueur en liaison avec l'éditeur;
- des modules complémentaires (pour une utilisation plus avancée comme l'utilisation de bases de données).
1.3 Se repérer dans Edupython
Lorsque vous lancez EduPython vous obtenez une fenêtre subdivisée en quatre grande partie représentées dans la Figure 1
- Barre de menu/outils
- permet d'accéder aux menus habituels (pour ouvrir/enregistrer un fichier, …)
- permet de faire tourner le script écrit dans l'éditeur;
- permet d'utiliser le débogueur…
- Éditeur de texte
- avec coloration syntaxique du code pour éviter de perdre du temps sur des erreurs grossières (chaîne de caractère non fermée, identifiant invalide, …);
- avec détection et mise en évidence d'erreurs de syntaxes.
- Console
- permet de saisir rapidement des instructions Python pour faire des tests (par exemple en cas de doute sur le nom d'une variable ou d'une fonction);
- la sortie standard est redirigée vers la console (donc les
instructions
print
des scripts lancés depuis edupython affichent les messages dans la console).
2 Bases
2.1 Algo
2.1.1 Algorithmes
Un algorithme ou programme est
- une suite d'instructions;
- chaque instruction manipulant des données (nombres entiers, nombres flottants, chaîne de caractères, ou bien des données plus complexes comme des listes, des dictionnaires, des graphes, …);
- l'instruction exécutée après l'instruction courante n'est pas
toujours l'instruction de la ligne suivante: le flot d'éxecution
(c'est à dire l'ordre d'exécution des instructions) peut
lui-même dépendre des données. Il est ainsi possible de sauter
des instructions (cas du
if
-elif
-else
) ou bien de revenir en arrière (cas des bouclesfor
et des boucleswhile
), … - le programme peut aussi afficher des données, écrire dans un fichier, envoyer des données sur une interface réseau, … En fait c'est ce qui distingue un programme d'un véritable algorithme, un algorithme ne pouvant (par définition) que retourner une valeur.
2.1.2 Variables: partie 1
Une variable est un espace aloué en mémoire qui fait donc référence à un contenu susceptible d'évoluer lors de l'éxecution du programme. Une variable est désignée par son identifiant et à chaque instant un identifiant ne peut désigner qu'une variable.
#+RESULTS
Un identifiant (c'est à dire le nom d'une variable) doit être composé uniquement de lettres, de chiffres et du tiret bas (underscore). De plus le premier caractère ne doit pas être un chiffre.
- identifiants valables:
mon_entier
,_temporaire23
, ~identifiant_correcte_mais_tres_long~,a_as_12_bbh
- identifiants non valables:
,mon-entier
,23temporaire
,avec espace
@home
Dans beaucoup de languages il est nécessaire de déclarer une variable afin qu'un espace mémoire de taille suffisante lui soit aloué. Cela est inutile en Python et si la première utilisation d'une variable est pour lui affecter une valeur alors cette affectation vaut déclaration.
Cependant si la première utilisation d'une variable n'est pas une
affectation il se produit une erreur NameError
. Par exemple le
programme:
p = 1 print(p + q)
se traduit par l'erreur "NameError: name 'q' is not defined"
.
En python, le type de valeur référencé par une variable peut évoluer
durant l'exécution: une variable comme mavar
peut contenir un entier
comme 2
puis un flottant comme 1.4
puis une chaîne de caractère
comme "police"
. Autrement dit le script suivant est valide:
mavar = 2 mavar = 1.4 mavar = "police"
2.1.3 Premier programme
Lancer Edupython, saisir le programme suivant (cadre en haut à gauche dont les lignes sont numérotées) puis l'exécuter. Vérifier que la sortie standard – qui s'affiche dans la console – correspond au contenu du cadre en bas à gauche. Le détail de l'exécution instruction après instruction est lui affiché dans la colonne de droite (lors du survol des lignes du tableau par votre souris la ligne correspondante du code source est aussi mise en évidence).
p = 1 print("p vaut:", p) p = 2+p print("p vaut:", p) p = 5*p print("p vaut:", p)
p vaut: 1 p vaut: 3 p vaut: 15
Ligne | Instruction | p (1-6;0) |
---|---|---|
1 | 'p = 1' | |
2 | 'print("p vaut:", p)' | 1 |
3 | 'p = 2+p' | 1 |
4 | 'print("p vaut:", p)' | 3 |
5 | 'p = 5∗p' | 3 |
6 | 'print("p vaut:", p)' | 15 |
2.2 Booléens
2.2.1 Valeurs booléennes et comparaison
- les valeurs booléennes en Python s'écrivent
True
etFalse
(attention aux majuscules!); - les opérateurs
<
et>
ont leur sens usuel entre deux nombres (entiers ou flottants); - les inégalités larges
<=
et>=
ne pouvant être entrées directement au clavier nécessitent deux caractères; - l'opérateur d'égalité en valeur
==
nécessite lui aussi deux caractères pour le distinguer de l'opérateur d'affectation=
. - pour tester si une condition n'est pas vérifiée on peut utiliser
not
. - Pour tester la différence de deux valeurs
a
etb
il y a plus simple quenot a==b
à savoira != b
print("3<2?:", 3 < 2) print("3>2?:", 3 > 2) print("4<=5?:", 4 <= 5) print("4>=5?:", 4 >= 5) print("5==5.0?:", 5 < 5.0) a=15 b = 12 c = 12 print("a<b?:", a < b) print("a==c?:", a == b) print("b==c?:", b == c)
3<2?: False 3>2?: True 4<=5?: True 4>=5?: False 5==5.0?: False a<b?: False a==c?: False b==c?: True
Ligne | Instruction | a (1-11;0) | b (1-11;0) | c (1-11;0) |
---|---|---|---|---|
1 | 'print("3<2?:", 3 < 2)' | |||
2 | 'print("3>2?:", 3 > 2)' | |||
3 | 'print("4<=5?:", 4 <= 5)' | |||
4 | 'print("4>=5?:", 4 >= 5)' | |||
5 | 'print("5==5.0?:", 5 < 5.0)' | |||
6 | 'a=15' | |||
7 | 'b = 12' | 15 | ||
8 | 'c = 12' | 15 | 12 | |
9 | 'print("a<b?:", a < b)' | 15 | 12 | 12 |
10 | 'print("a==c?:", a == b)' | 15 | 12 | 12 |
11 | 'print("b==c?:", b == c)' | 15 | 12 | 12 |
2.2.2 Tests if
- else
Lancer Edupython et y saisir le programme ci-dessous (attention à
bien saisir les signes :
en fin de ligne if
et en fin de ligne
else
)
p = 10 if p>10: print("p est strictement plus grand que 10") else: print("p est inférieur ou égal à 10")
p est inférieur ou égal à 10
Ligne | Instruction | p (1-5;0) |
---|---|---|
1 | 'p = 10' | |
2 | 'if p>10:' | 10 |
5 | ' print("p est inférieur ou égal à 10")' | 10 |
Modifier la première ligne du programme précédent comme ci-dessous puis exécuter ce nouveau programme. On s'aperçoit que le flot d'exécution (c'est à dire les instructions qui sont exécutées, voir la colonne "Ligne" du tableau de droite) a changé: celui-ci dépend bien des données!
p = 11 if p>10: print("p est strictement plus grand que 10") else: print("p est inférieur ou égal à 10")
p est strictement plus grand que 10
Ligne | Instruction | p (1-5;0) |
---|---|---|
1 | 'p = 11' | |
2 | 'if p>10:' | 11 |
3 | ' print("p est strictement plus grand que 10")' | 11 |
2.2.3 if
- elif
- elif
- … - else
Il est parfois nécessaires de discriminer entre plus de deux
valeurs. Pour cela on ajoute autant de condition elif
que
nécessaire entre le if
et le else
p = 24 if p==25: print("p est égal à 25.") elif p==24: print("p est égal à 24.") elif p>25: print("p est strictement supérieur à 25.") else: print("p est strictement inférieur à 25 et différent de 24.")
p est égal à 24.
Ligne | Instruction | p (1-9;0) |
---|---|---|
1 | 'p = 24' | |
2 | 'if p==25:' | 24 |
4 | 'elif p==24:' | 24 |
5 | ' print("p est égal à 24.")' | 24 |
Remarque: le if
et chaque elif
doit être suivi d'une condition,
contrairement à else
qui doit être immédiatement suivi de :
(aux
espaces près).
2.2.4 TP
- Recopier puis compléter l'algorithme ci-dessous afin
- qu'il demande un entier
a
à l'utilisateur (première ligne déjà écrite); - qu'il affiche
"a est strictement plus grand que 1"
,"a est inférieur ou égal à 1"
ou"a est égal à 1"
suivant la valeur dea
.
- qu'il demande un entier
- Écrire un algorithme qui
- demande deux entiers
first_int
etsecond_int
à l'utilisateur - puis affiche
"first_int est strictement plus grand que second_int"
,"first_int est strictement inférieur à second_int"
ou"first_int est égal à second_int"
suivant les valeurs defirst_int
etsecond_int
.
- demande deux entiers
- Dans la console Edupython entrer successivement (on validera
chaque entrée avec la touche entrée)
5%2
,6%2
,7%2
,8%2
,9%2
,10%2
,11%2
,12%2
. - A votre avis (et à l'aide de la question précédente), à
quelle condition sur l'entier
a
l'expressiona % 2
retourne-t-elle0
? - À l'aide des deux questions précédentes, écrire un algorithme
qui accepte un entier
my_nbr
en entrée puis affiche"a est pair"
ou"a est impair"
suivant la valeur dea
.
- Dans la console Edupython entrer successivement (on validera
chaque entrée avec la touche entrée)
Recopier l'algorithme ci-dessous. Pourquoi le script ci-dessous n'affiche-t-il pas
"p est égal à 25."
? On donner la réponse sous la forme d'un commentaire (rappel: en python, les commentaires sont introduits par le symbol#
)p = 25 if p>24: print("p est strictement supérieur à 24.") elif p==25: print("p est égal à 25.") else: print("p est strictement inférieur à 24.")
Écrire un programme qui accepte une chaîne de caractères en entrée puis affiche
"la longueur de cette chaîne est paire"
ou"la longueur de cette chaîne est impaire"
suivant la longueur de cette chaîne (rappel: sima_chaine
est une chaîne alorslen(ma_chaine)
est la longueur de cette chaîne)chaine = input("Saisir une chaîne de caractères") if len(chaine) % 2 == 0: print("la longueur de cette chaîne est paire") else: print("la longueur de cette chaîne est impaire")
Rappelons (voir ici si vous ne me croyez pas) qu'une année est bisextile si et seulement si
- elle est divisible par 4 mais pas par 100;
- ou bien si elle est divisible par 400.
Rappelons aussi que en python un entier
n
est- divisible par
4
si et seulement sin%4==0
; - divisible par
100
si et seulement sin%100==0
; - divisible par
400
si et seulement si400==0
.
azaz
- Vérifier dans la console les valeurs retournées par les
expressions
8 % 4
,9 % 4
,124 % 4
,126 % 4
,200 % 100
,233 % 100
,800 % 400
et801 % 400
sont cohérentes. Compléter le script suivant afin qu'il
- commence par demander un entier
annee
à l'utilisateur; - puis affiche
"Année bisextile"
ou"Année non bisextile"
suivant que l'année correspondante soit ou non bisextile.
On vérifiera que entre 2016 et 2020 seuls les années 2016 et 2020 sont bisextiles.
- commence par demander un entier
annee=int(input("Saisir une année"))
2.3 Built-in
2.3.1 La fonction type
Python dispose d'une fonction nommée type
qui retourne le type de
son argument.
Attention: le commande type retourne elle-même une quantité d'un type particulier (qui n'est pas une chaîne de caractères)!
print("Type entier:", type(128)) print("Type floattant:", type(128.0)) print("Type chaîne de caractère:", type("J'aime les maths")) print("Type d'un type:", type(type("Un peu plus complexe"))) print("Type d'un type:", type(type(7.18)))
Type entier: <class 'int'> Type floattant: <class 'float'> Type chaîne de caractère: <class 'str'> Type d'un type: <class 'type'> Type d'un type: <class 'type'>
Remarques: Voici la signification de quelques abréviations utilisées comme nom de type:
int
pour "integer" c'est à dire "entier" (voir la traduction);str
pour "string" c'est à dire "chaîne de caractères" (voir la traduction);
2.3.2 La fonction print
- La fonction
print
affiche ses argument sur la "sortie standard"; - ceux-ci sont séparés par un espace;
- le tout est suivi d'un retour à la ligne;
- Les arguments de la fonction
print
peuvent être de tout type est la représentation textuelle obtenue est presque toujours très bonne (c'est à dire complète et lisible).
p = 7 print("p vaut:", p) p = p + 3 print("maintenant p vaut:", p) p = 2*p print("Et maintenant p vaut:", p)
p vaut: 7 maintenant p vaut: 10 Et maintenant p vaut: 20
2.3.3 Les fonctions de conversion
Les fonctions int
et float
sont des fonctions de conversion qui
retournent respectivement un entier et un flottant. Elles acceptent
des arguments de type variés et leur utilisation est donc diverse.
- passage entre entiers et flottants
float(10)
retourne le nombre flottant10.0
(ce qui n'est pas exactement la même chose que l'entier10
puisque leur type diffère;int(10.0)
retourne l'entier10
;int(10.5)
retourne l'entier10
obtenu en supprimant la partie décimale de10.5
;
- passage entre représentation textuelle et numérique
- float("10.5") retourne le flottant
10.5
qui est très différent de la chaîne de caractères "10.5" (par exemple évaluer dans la console les expressionsfloat("10.5")+1
puis"10.5"+1
) - int("10") retourne l'entier
10
qui est très différent de la chaîne de caractères "10" (par exemple évaluer dans la console les expressionsint("10")+1
puis"10"+1
)
- float("10.5") retourne le flottant
2.3.4 La fonction input
La fonction input
permet de demander à l'utilisateur de saisir
une valeur et retourne cette valeur sous le forme d'une chaîne de
caractères. Si l'on souhaite
- obtenir une valeur entière il faut donc passer la valeur
retournée par la fonction
input
à la fonctionint
(la fonctionint
convertit une chaîne de caractères ne contenant que des chiffres en nombre entier), ce qui donneint(input("Mon message:"))
- obtenir une valeur flottante il faut donc passer la valeur
retournée par la fonction
input
à la fonctionfloat
(la fonctionfloat
convertit une chaîne de caractères ne contenant que des chiffres et le symbole.
en nombre flottant), ce qui donnefloat(input("Mon message:"))
Remarque: au lieu de modifier le code source pour tester plusieurs
valeurs, il vaut mieux utiliser la fonction input. Mais attention à
ne pas oublier de convertir dans le type voulu car "12"
est très
différent de 12
!
2.4 Types
2.4.1 Entiers et flottants
Quelques exemples valent mieux qu'un long discours:
- Entiers
13
,-13
,1300000
,0
;- Flottants
10.2
,2.
,-13.5
,1300000.1
,14
,.2
,14.
;
Les opération usuelles entre nombres (entiers ou flottants) sont +, -, *, /.
p = 1.3 print("p vaut: ", p) p = p + 3 print("maintenant p vaut: ", p) p = 2*p print("Et maintenant p vaut: ", p)
p vaut: 1.3 maintenant p vaut: 4.3 Et maintenant p vaut: 8.6
Ligne | Instruction | p (1-6;0) |
---|---|---|
1 | 'p = 1.3' | |
2 | 'print("p vaut: ", p)' | 1.3 |
3 | 'p = p + 3' | 1.3 |
4 | 'print("maintenant p vaut: ", p)' | 4.3 |
5 | 'p = 2∗p' | 4.3 |
6 | 'print("Et maintenant p vaut: ", p)' | 8.6 |
2.4.2 Chaîne de caractères
Les chaînes de caractère peuvent être saisie avec des guillemets simples ou double. Il n'y a aucune différence sauf si la chaîne contient elle-même des guillemets:
print("Une chaîne de caractères") print('Une autre chaîne de caractères') print("Il m'a dit: 'bonjour'!") print('Et je lui ai répondu: "merci"!')
Une chaîne de caractères Une autre chaîne de caractères Il m'a dit: 'bonjour'! Et je lui ai répondu: "merci"!
Ligne | Instruction |
---|---|
1 | 'print("Une chaîne de caractères")' |
2 | "print('Une autre chaîne de caractères')" |
3 | 'print("Il m\'a dit: \'bonjour\'!")' |
4 | 'print(\'Et je lui ai répondu: "merci"!\')' |
Si une chaîne de caractère délimitée par des guillemets simples
(respectivement doubles) contient le caractère "
(resp '
) alors
celui-ci doit être précédé d'un backslash (\
) pour éviter qu'il ne
soit interprété comme la fin de la châine de caractère (on dit que le
backslash est un caractère d'échappement et que dans la chaîne
"A\"B"
le guillemet entre le "A"
et le "B"
est échappé).
print("Il m'a dit: \"bonjour\"!") print('Et je lui ai répondu: \'merci\'!')
Il m'a dit: "bonjour"! Et je lui ai répondu: 'merci'!
Ligne | Instruction |
---|---|
1 | 'print("Il m\'a dit: ?"bonjour?"!")' |
2 | "print('Et je lui ai répondu: ?'merci?'!')" |
2.4.3 La valeur None
None
est l'unique valeur de son type qui estNoneType
;None
n'est égale qu'àNone
:
print('None == "": ', None == "") print('None == 0: ', None == 0) print('None == .0: ', None == 0.) print('None == None: ', None == None)
None == "": False None == 0: False None == .0: False None == None: True
2.4.4 Les listes
- Définition
- Une liste représente un ensemble ordonné d'objets indéxés à partir de 0 (comme souvent en informatique);
- Pour saisir une liste il suffit d'écrire ses éléments dans l'ordre, séparés par des virgules, le tout encadré par des crochets;
- si
mavar
est une liste alorsmavar[0]
est son premier élément (donc d'indexe 0),mavar[1]
son second élément (donc d'indexe 1),mavar[2]
est le troisième élément (donc d'indexe 2), … - tenter d'accéder à un élémént via un indice supérieur ou égal à
la longueur de la liste est une erreur signalée par
"IndexError: list index out of range"
. - la fonction
len
retourne la longueur de la liste donnée en argument (rappel: fonctionne aussi avec les chaînes de caractères).
ma_lst = [49, True, 72.3, "Bla!"] print("ma_lst:", ma_lst) print("1er élmt de ma_lst:", ma_lst[0]) print("2nd élmt de ma_lst:", ma_lst[1]) ma_lst[1] = "MW" print("Après modification:") print("1er élmt de ma_lst:", ma_lst[0]) print("2nd élmt de ma_lst:", ma_lst[1])
ma_lst: [49, True, 72.3, 'Bla!'] 1er élmt de ma_lst: 49 2nd élmt de ma_lst: True Après modification: 1er élmt de ma_lst: 49 2nd élmt de ma_lst: MW
- Indices positifs
- pour faire référence à un élément d'une liste on saisit
l'identifiant de la liste suivi de l'indice de l'élément
recherché entre crochets:
maliste[monindice]
- une référence à un élément d'une liste peut se faire en lecture
comme dans
nbr = maliste[monindice] + 1
ou en écriture comme dansmaliste[monindice] = 112
.
ma_lst = [49, 72.3, "London"] print("ma_lst:", ma_lst) print("Premier élmt de ma_lst:", ma_lst[0]) print("Second élmt de ma_lst:", ma_lst[1])
ma_lst: [49, 72.3, 'London'] Premier élmt de ma_lst: 49 Second élmt de ma_lst: 72.3
Attention à ne pas tenter d'accéder à un élément d'une liste d'indice supérieur ou égal à sa longeur, même en écriture! Ainsi l'exemple suivant
maliste = ["Indice 0", "Indice 1"] maliste[2] = "Indice 2"
se traduit par l'erreur
"IndexError: list assignment index out of range"
- pour faire référence à un élément d'une liste on saisit
l'identifiant de la liste suivi de l'indice de l'élément
recherché entre crochets:
- Indices négatifs
- Les indices négatifs parcourent les éléments de la liste à partir de
la fin. Ainsi
mavar[-1]
représente le dernier élément de la liste etmavar[-2]
l'avant dernier. - sinon ils peuvent être utilisés en lecture ou en écriture (comme les indices positifs);
- tenter d'accéder à un élémént via un indice strictemtn inférieur à
la longueur de la liste est une erreur signalée par
"IndexError: list index out of range"
.
funky_l = ["Po", 71, [1,2,9]] print("funky_l:", funky_l) print("Premier élément de funky_l:", funky_l[0]) print("Dernier élément de funky_l:", funky_l[-1]) print("Et funky_l[-1][1]:", funky_l[-1][1])
funky_l: ['Po', 71, [1, 2, 9]] Premier élément de funky_l: Po Dernier élément de funky_l: [1, 2, 9] Et funky_l[-1][1]: 2
- Les indices négatifs parcourent les éléments de la liste à partir de
la fin. Ainsi
- Modifiction de listes
Les listes sont modifiables en python. En effet on peut
- changer l'élément d'indice donné (si l'indice n'est pas trop grand);
- ajouter des éléments au début, au milieu ou en fin de liste;
- supprimer des éléments au début, au milieu ou en fin de liste (attention: cela décale les indices des éléments suivants);
- Modification de l'élément d'indice donné (ou accès en écriture)
On utilise comme déjà vu la notation avec des crochets
rst12 = ["Il y a", 12, "élèves"] rst12[1] = 145 print(rst12)
['Il y a', 145, 'élèves']
Le nouvel élément peut très bien avoir un type différent du précédent:
bzr_lst = [12, [1,2], "?"] bzr_lst[2] = bzr_lst[0] print(bzr_lst)
[12, [1, 2], 12]
Rappelons que la notation avec des crochets ne permet pas d'accéder – même en écriture – à un élément d'indice supérieur ou égal à la longueur de la liste (ou pour les indices négatifs inférieur à l'opposé de cette longueur).
- Suppression d'éléments d'une liste
- On utilise pour cela le mot cléf
del
suivi du nom de la liste puis entre crochet l'indice que l'on souhaite supprimer; - attention car supprimer un élément d'une liste décale les indices de tous les éléments suivants.
a = ["utf8", 20, 40, "azb126z", "FR"] del a[1] print(a)
['utf8', 40, 'azb126z', 'FR']
- On utilise pour cela le mot cléf
- Création rapide de liste
- si maliste est une liste et
n
n entier naturel alorsn*maliste
crée une liste obtenue en concatenantn
fois la listemaliste
- on utilise surtout cela pour créer rapidement une liste de
longueur donnée:
maliste_longueur13 = 13*[None]
liste_longueur7 = 7*[None] liste_longueur3 = 3*[None] print("liste_longueur7:", liste_longueur7) print("liste_longueur3:", liste_longueur3)
liste_longueur7: [None, None, None, None, None, None, None] liste_longueur3: [None, None, None]
- si maliste est une liste et
2.4.5 TP
- Écrire un programme qui demande à l'utilisateur de saisir deux
chaînes de caractères puis retourne une liste à trois éléments qui
sont dans l'ordre
- la première chaîne saisie par l'utilisateur;
- la seconde chaîne saisie par l'utilisateur
- la somme des longueurs des deux chaînes;
- Écrire un script python qui demande deux nombres à l'utilisateur puis affiche une liste constituée de ces deux éléments triés dans l'ordre croissant
- Faire de même que l'exercice précédent mais avec trois valeurs cette fois.
- Écrire un script python
commençant par les lignes suivantes:
mois = ["janvier", "février", "mars", "avril", "mai", "juin", "juillet", "août", "septembre", "octobre", "novembre", "décembre"]
- qui demande un entier à l'utilisateur;
- affiche le message "Mauvais indice" si le nombre saisi n'est pas compris entre 1 et 12;
- affiche le nom du mois correspondant sinon (donc afficher
"décembre"
si l'utilisateur a entré 12).
- Faire de même que l'exercice précédent avec les jours de la semaine. Précisons que
- la semaine commence un lundi;
- l'algorithme doit donc afficher "mercredi" si l'utilisateur a entré 3.
- Écrire un programme qui demande un nombre entiers à l'utilisateur
puis
- affiche
"Entrée invalide"
si ce nombre est négatif ou strictement plus grand que 10. - dans le cas contraire affiche la liste de tous les nombres
entier de 0 à 10 compris excepté l'entier entré par
l'utilisateur. Par exemple si l'utilisateur entre 3 alors le
programme doit afficher
[0,1,2,4,5,6,7,8,9,10]
.
- affiche
- Écrire un script python
commençant par les lignes suivantes (inutile de comprendre leur fonctionnement et utiliser le bouton bleu "Copy" pour sélectionner le code pour la copie):
def jour_dans_semaine(num_mois, num_jour_ds_mois): """num_mois doit être compris entre 1 et 12 et num_jour_ds_mois entre 1 et 31. Retourne un nombre entre 1 et 7 représentant le jour de la semaine. """ mois = [4, 0, 1, 4, 6, 2, 4, 0, 3, 5, 1, 3] return ((num_jour_ds_mois-1 + mois[num_mois-1]) % 7)+1
On admettra qu'après ces lignes
jour_dans_semaine(a, b)
est un entier compris entre 1 et 7 représentant le jour de la semaine de la date b/a/2016 (la semaine commençant le lundi). Ainsijour_dans_semaine(7, 14)
retourne 4 car le 14 juillet 2016 était un jeudi, quatrième jour de la semaine.- qui demande deux nombres à l'utilisateur;
- puis affiche le jour de la semaine correspondante en toutes lettres (par exemple "lundi"). On passera par une liste…
Améliorer le programme précédent pour qu'il vérifie que les entiers entrés par l'utilisateur représentent une date en 2016. On pourra utiliser la définition de variable ci-dessous qui donne dans l'ordre le nombre de jours de chaque mois en 2016 en commençant en janvier
# Numéro du dernier jour de chaque mois de 2016 nbr_jour_ds_mois = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
- Écrire un script python qui
débute par les lignes suivantes (inutile de comprendre leur fonctionnement pour l'instant, leur effet est décrit dans le commentaire en fin de code):
nbr_val = int(input("Nombre de valeurs:")) # nbr_val doit être un nombre entier mais aucune verificaton n'est # faite... valeurs_lst = [None]*nbr_val for i in range(nbr_val): valeurs_lst[i] = float(input("Entrer une valeur:")) valeurs_lst.sort() # À partir de maintenant nbr_val est un entier et valeurs_lst est une # liste triée dans l'ordre croissant contenant les nbr_val valeurs # entrées par l'utilisateur (qui doivent être des entiers ou des # flottants). Ainsi si l'utilisteur entre dans l'ordre 3, 4.2, -1.2 # puis 9.7 alors après ces lignes nbr_val vaut 3 et valeurs_lst est la # liste [-1.2, 4.2, 9.7]
- affiche la médiane des valeurs entrée par l'utilisateur. Voir par
exemple en bas de la première page ici pour la définition de la
médiane ou encore ici (rappel: un entier
i
est pair si et seulement sii%2==0
).
3 Boucles
3.1 Boucle for
3.1.1 Syntaxe et exemples
- La boucle
for
a pour syntaxefor myvar in myliste:
où myliste est une liste et myvar est un identifiant. Le bloc syntaxique qui suit (délimité par l'indentation par rapport àfor
) est alors exécuté une fois pour chaque élément demyliste
, la variable d'identifiantmyvar
prenant les valeurs des éléments demyliste
(dans l'ordre). - Dans
for myvar in myliste:
,myvar
doit être un identifiant etmyliste
doit représenter une liste. Ainsifor i in [1,2,3]:
est correct de même quefor j in maliste:
simaliste
est une variable contenant une liste.
print("Avant la boucle for") for i in [-3, 4, 5, 10]: print(" i vaut:", i) print("Après la boucle for")
Avant la boucle for i vaut: -3 i vaut: 4 i vaut: 5 i vaut: 10 Après la boucle for
Ligne | Instruction | i (1-4;0) |
---|---|---|
1 | 'print("Avant la boucle for")' | |
2 | 'for i in [-3, 4, 5, 10]:' | |
3 | ' print(" i vaut:", i)' | -3 |
2 | 'for i in [-3, 4, 5, 10]:' | -3 |
3 | ' print(" i vaut:", i)' | 4 |
2 | 'for i in [-3, 4, 5, 10]:' | 4 |
3 | ' print(" i vaut:", i)' | 5 |
2 | 'for i in [-3, 4, 5, 10]:' | 5 |
3 | ' print(" i vaut:", i)' | 10 |
2 | 'for i in [-3, 4, 5, 10]:' | 10 |
4 | 'print("Après la boucle for")' | 10 |
Autre exemple:
prime_int_lst = [2, 3, 5, 7, 11] print("Avant la boucle for") for nbr in prime_int_lst: print(" ", nbr, "est premier.") print("Après la boucle for")
Avant la boucle for 2 est premier. 3 est premier. 5 est premier. 7 est premier. 11 est premier. Après la boucle for
Ligne | Instruction | nbr (1-5;0) | prime_int_lst (1-5;0) |
---|---|---|---|
1 | 'prime_int_lst = [2, 3, 5, 7, 11]' | ||
2 | 'print("Avant la boucle for")' | [2, 3, 5, 7, 11] | |
3 | 'for nbr in prime_int_lst:' | [2, 3, 5, 7, 11] | |
4 | ' print(" ", nbr, "est premier.")' | 2 | [2, 3, 5, 7, 11] |
3 | 'for nbr in prime_int_lst:' | 2 | [2, 3, 5, 7, 11] |
4 | ' print(" ", nbr, "est premier.")' | 3 | [2, 3, 5, 7, 11] |
3 | 'for nbr in prime_int_lst:' | 3 | [2, 3, 5, 7, 11] |
4 | ' print(" ", nbr, "est premier.")' | 5 | [2, 3, 5, 7, 11] |
3 | 'for nbr in prime_int_lst:' | 5 | [2, 3, 5, 7, 11] |
4 | ' print(" ", nbr, "est premier.")' | 7 | [2, 3, 5, 7, 11] |
3 | 'for nbr in prime_int_lst:' | 7 | [2, 3, 5, 7, 11] |
4 | ' print(" ", nbr, "est premier.")' | 11 | [2, 3, 5, 7, 11] |
3 | 'for nbr in prime_int_lst:' | 11 | [2, 3, 5, 7, 11] |
5 | 'print("Après la boucle for")' | 11 | [2, 3, 5, 7, 11] |
3.2 Boucles while
3.2.1 Syntaxe et exemples
- La boucle
while
a pour syntaxewhile condition:
où condition est une expression booléenne (dont l'évaluation retourneTrue
ouFalse
). Le bloc syntaxique qui suit (délimité par l'indentation par rapport àwhile
) est exécuté tant quecondition
retourneTrue
. Autrement dit la boucle s'arrête la première fois quecondition
retourneFalse
.
i = 1 print("i avant la boucle while:", i) while i<10: i = 2*i print("i après la boucle while", i)
i avant la boucle while: 1 i après la boucle while 16
Ligne | Instruction | i (1-5;0) | (while cond) i<10 |
---|---|---|---|
1 | 'i = 1' | ||
2 | 'print("i avant la boucle while:", i)' | 1 | |
3 | 'while i<10:' | 1 | V |
4 | ' i = 2∗i' | 1 | |
3 | 'while i<10:' | 2 | V |
4 | ' i = 2∗i' | 2 | |
3 | 'while i<10:' | 4 | V |
4 | ' i = 2∗i' | 4 | |
3 | 'while i<10:' | 8 | V |
4 | ' i = 2∗i' | 8 | |
3 | 'while i<10:' | 16 | F |
5 | 'print("i après la boucle while", i)' | 16 |
Autre exemple:
solde = 100 print("solde avant la boucle while:", solde) while solde<120: solde = solde*1.05 print(solde) print("solde après la boucle while", solde)
solde avant la boucle while: 100 105.0 110.25 115.7625 121.55062500000001 solde après la boucle while 121.55062500000001
Ligne | Instruction | solde (1-6;0) | (while cond) solde<120 |
---|---|---|---|
1 | 'solde = 100' | ||
2 | 'print("solde avant la boucle while:", solde)' | 100 | |
3 | 'while solde<120:' | 100 | V |
4 | ' solde = solde∗1.05' | 100 | |
5 | ' print(solde)' | 105.0 | |
3 | 'while solde<120:' | 105.0 | V |
4 | ' solde = solde∗1.05' | 105.0 | |
5 | ' print(solde)' | 110.25 | |
3 | 'while solde<120:' | 110.25 | V |
4 | ' solde = solde∗1.05' | 110.25 | |
5 | ' print(solde)' | 115.7625 | |
3 | 'while solde<120:' | 115.7625 | V |
4 | ' solde = solde∗1.05' | 115.7625 | |
5 | ' print(solde)' | 121.55062500000001 | |
3 | 'while solde<120:' | 121.55062500000001 | F |
6 | 'print("solde après la boucle while", solde)' | 121.55062500000001 |
3.3 TP
- un compte est rémunéré à 5%. Son solde au premier janvier 2017 était
de 200 euros.
dans le contexte de cet exercice, qu'affiche le programme ci-dessous?
solde = 200 for annee in range(2018, 2030): solde = solde*1.05 print(solde)
dans le contexte de cet exercice, qu'affiche le programme ci-dessous?
solde = 200 annee = 2017 while solde<300: solde = solde*1.05 annee = annee + 1 print(annee)
- En fait l'algorithme ci-dessus ne prend pas en compte les frais fixes de 30 euros par an pour la tenu de ce compte (qui sont prévelés après le versement des intérêts). Modifier maintenant cet algorithme afin qu'il prenne en compte ces frais et pour qu'il affiche l'année où le solde de ce compte est au moins de 400 euros.
Le programme ci-dessous est un "jeu" où l'utilisatur doit trouver une valeur (ici la valeur ne change pas et vaut toujours 10…)
nbr_a_deviner = 10 nbr_correct = False while not nbr_correct: nbr = int(input("Saisir un nombre entier: ")) if nbr == nbr_a_deviner: nbr_correct = True else: nbr_correct = False if not nbr_correct: print("Essayez encore une fois") print("You win!")
- Recopier puis modifier ce programme pour qu'il affiche
"Nombre trop grand"
ou bien"Nombre trop petit"
suivant la valeur entrée au lieu de simplement afficher"Essayez encore une fois"
.
- Recopier puis modifier ce programme pour qu'il affiche
On admettra que la fonction suivante nommée
est_premier
retourneTrue
si et seulement si son argument est un nombre premier.def est_premier(n): if n<=1: return False for i in range(2,n-1): if n%i==0: return False return True
- Vérifier que l'appel
est_premier(11)
retourneTrue
et que que l'appelest_premier(12)
retourneFalse
. - Écrire un programme qui affiche tous les nombres premiers qui sont
inférieurs à
200
. - Écrire un programme qui affiche les
200
premiers nombres premiers.
- Vérifier que l'appel
- Écrire une fonction nommée
countdown
acceptant un unique argument que l'on supposera être un entier strictement positif et qui affiche un compte à rebours à partir de cet entier. Ainsicountdown(4)
doit afficher dans l'ordre 4, 3, 2, 1, et enfin 0. - Écrire une fonction nommée
countdown_boom
acceptant un unique argument que l'on supposera être un entier strictement positif et qui affiche un compte à rebours à partir de cet entier tel quecountdown_boom(4)
affiche dans l'ordre 4, 3, 2, 1, et enfin "Boom".
- Écrire une fonction nommée
En partant d'un nombre entier strictement positif, on dresse la liste des nombres entiers obtenus de la façon suivante:
s’il est pair, on le divise par 2; s’il est impair, on le multiplie par 3 et on ajoute 1. Ensuite on répéte l’opération tant que le nombre obtenu est différent de 1 (si l'on obtient 1 alors on s'arrête).
Ainsi si l'on part de 5, on obtient dans l'ordre 16 (car 5 est impair et 3*5+1=16) puis 8 (car 16 est pair et 16/2=8) puis 4 (car 8 est pair et 8/2=4) puis 2 (car 4 est pair et 4/2=2) puis 1 (car 2 est pair et 2/2=1). On vérifie de même que si l'on part de 6 alors on obtient cette fois dans l'ordre: 6, 3, 10, 5, 16, 8, 4, 2, 1.
Les suites de nombres ainsi obtenues sont appelées suites de syracuse. Ainsi 5, 16, 8, 4, 2, 1 est la suite de syracuse obtenue à partir de l'entier 5 et 6, 3, 10, 5, 16, 8, 4, 2, 1 est la suite de syracuse obtenue à partir de l'entier 6.
La fonction suivante nommée
terme_suiv_syracuse
permet d'obtenir le nombre suivant de la suite si le nombre courant est donné comme paramètre x:def terme_suiv_syracuse(x): if x%2==0: return int(x/2) else: return 3*x+1
- vérifier que les valeurs retournées par les appels
terme_suiv_syracuse(5)
etterme_suiv_syracuse(16)
sont cohérentes. - afficher les termes de la suite ainsi obtenue si l'on part de
l'entier 5 (on utilisera la fonction
terme_suiv_syracuse
). - écrire une fonction nommée
syracuse
qui accepte un unique argument (que l'on supposera de typeint
) et qui affiche tous les termes de la suite obtenue à partir de l'entierx
. Ainsi l'appelsyracuse(6)
doit afficher dans l'ordre6
,3
,10
,5
,16
,8
,4
,2
et enfin1
. - écrire une fonction nommée
temps_de_vols_syracuse
qui accepte un unique argument (que l'on supposera de typeint
) et qui retourne le nombre d'entiers de la suite obtenue à partir de l'entierx
. Ainsi l'appeltemps_de_vols_syracuse(6)
doit retourner9
(car la suite de syracuse6
,3
,10
,5
,16
,8
,4
,2
,1
est constituée de 9 entiers). On vérifiera que l'appeltemps_de_vols_syracuse(27)
retourne bien112
.
- vérifier que les valeurs retournées par les appels
4 Fonctions
4.1 Qu'est-ce?
Une fonction est
- un bloc de code
- sui est nommé, c'est à dire qu'on associe un identifiant à ce bloc de code;
- qui dépend éventuellement de paramètres (aussi appelés arguments), qui sont des variables dont les valeurs initiales (en début du bloc de code) peuvent varier à chaque appel;
- qui retourne une valeur (un nombre flottant, un entier,
None
, ou tout autre objet python comme une liste ou autre…). Si aucune valeur n'est explicitement retournée par le code d'une fonction alors cette dernière retourneraNone
. - qui peut être exécuté (on dit plutôt appelé) plusieurs fois et avec des paramètres différents entre chaque appel.
Nous avons déjà croisé des fonctions qui font partie intégrante du
language python. Ainsi len
est une fonction qui accepte un
argument (qui doit être une liste ou une chaîne de caractères) et
retourne un entier (qui représente la longueur de cette liste ou de
cette chaîne de caractères). Ainsi len([1,6,3])
est un appel à la
fonction len
avec comme argument la liste [1,6,3]
et qui
retourne 3
, si bien que print(len([1,6,3]))
affiche 3
.
4.2 Définition de fonction
Pour définir une fonction en python on écrit dans l'ordre
- le mot-cléf
def
suivi de un ou plusieurs espaces; - l'identifiant de la fonction (comme
fonction_carree
ouclient_le_plus_riche
ou encoredtls1_heartbeat
). Cet identifiant est soumis aux même règles que les identifiants de variables; - une liste d'identifiants pour les arguments (qui sont des variables valables dans le corps de la fonction) séparés par des virgules et entre parenthèses;
- deux points
:
(comme pour toutes les instructions qui délimitent des bloques de code commeif
,elif
etelse
); - le corps de la fonction est ensuite entièrement indenté (de quatre
espaces) par rapport à la ligne contenant
def
ce qui permet ce délimiter le corps de la fonction (c'est à dire de savoir où s'arrête la définition);
De plus
- dans le corps d'une fonction, on peut utiliser
(éventuellement plusieurs fois) l'instruction return
- l'instruction
return
accepte une valeur comme argument (comme dansreturn 1
oureturn True
ou encore ,return [1,2,"police"]
); - lors de l'exécution du corps de la fonction, l'instruction return provoque l'arrêt de l'exécution du code de la fonction et le retour au code appelant.
Le code suivant définit une fonction d'identifiant dernier_element
et acceptant exactement un seul argument (appelé ).
def dernier_element(maliste): if type(maliste)!=list: print("Erreur: l'argument n'est pas une liste.") return None elif len(maliste) == 0: print("Erreur: la liste est vide.") return None else: return maliste[-1]
4.3 Appel de fonction
Pour appeler une fonction (après sa définition!) on:
- écrit son identifiant;
- suivi, entre parenthèses et séparées par des virgules, des valeurs données à chaque paramètre pour cet appel (valeurs données dans le même ordre que dans la définition de la fonction);
Par exemple print("premier argument", "second argument")
,
len([2,9,2])
et range(3, 8)
sont des appels de fonctions.
Dans l'exemple ci-dessous on appelle la fonction len
avec comme
paramètre equipe
ce qui retourne la longueur de cette liste que l'on
stoque dans la variable nbr_joueurs
puis que l'on affiche.
equipe = [["Lassana", "Diarra"], ["Presnel", "Kimpembe"], ["Paul", "Pogba"], ["Abou", "Diaby"], ["Kingsley", "Coman"], ["Francois", "Clerc"], ["Ousmane", "Dembélé"], ["Aly", "Cissokho"], ["Geoffrey", "Kondogbia"], ["Steve", "Mandanda"], ["Karim", "Benzema"], ["Yann", "M'Vila"], ["Nabil", "Fekir"], ["Hatem", "Ben Arfa"], ["Layvin", "Kurzawa"], ["Raphael", "Varane"], ["Paul-Georges", "Ntep"], ["Olivier", "Giroud"], ["Maxime", "Gonalons"], ["Anthony", "Martial"], ["Loic", "Remy"], ["Guillaume", "Hoarau"]] nbr_joueurs = len(equipe) print(nbr_joueurs)
22
4.4 Exemples
La fonction suivante, appelée fonction_carre
, retourne le carré de
son argument et
- les lignes 1 et 2 forment la définition de la fonction
fonction_carre
; - un premier appel à la fonction
fonction_carre
avec comme paramètre12
est effectué à la ligne 4; - un second appel à la fonction
fonction_carre
avec comme paramètre3
est effectué à la ligne 6.
def fonction_carre(x): return x*x douze_au_carre = fonction_carre(12) print(douze_au_carre) print(fonction_carre(3))
144 9
Ligne | Instruction | douze_au_carre (1-6;0) | x (1-2;1) | x (1-2;1) |
---|---|---|---|---|
1 | 'def fonction_carre(x):' | |||
4 | 'douze_au_carre = fonction_carre(12)' | |||
1 | 'def fonction_carre(x):' | 12 | ||
2 | ' return x∗x' | 12 | ||
5 | 'print(douze_au_carre)' | 144 | ||
6 | 'print(fonction_carre(3))' | 144 | ||
1 | 'def fonction_carre(x):' | 144 | 3 | |
2 | ' return x∗x' | 144 | 3 |
La fonction suivante, appelée plus_grand
, accepte trois arguments et
retourne le plus grand des trois. Ici elle est appelée avec les
arguments 3
, 4
et 1
et retourne donc 4
.
def plus_grand(x, y, z): if x > y: if x > z: return x else: return z else: if y > z: return y else: return z return y print(plus_grand(3, 4, 1))
4
Ligne | Instruction | x (1-12;1) | y (1-12;1) | z (1-12;1) |
---|---|---|---|---|
1 | 'def plus_grand(x, y, z):' | |||
14 | 'print(plus_grand(3, 4, 1))' | |||
1 | 'def plus_grand(x, y, z):' | 3 | 4 | 1 |
2 | ' if x > y:' | 3 | 4 | 1 |
8 | ' if y > z:' | 3 | 4 | 1 |
9 | ' return y' | 3 | 4 | 1 |
4.5 TP
Qu'affiche le script suivant? Expliquer.
def somme_deux_arguments(x,y): return x+y somme = somme_deux_arguments(11, 12) print(somme)
- Définir une fonction
produit_deux_arguments
qui accepte deux arguments (supposés de typefloat
ouint
) et retourne leur produit. - Définir une fonction
somme_trois_arguments
qui accepte trois arguments (supposés de typefloat
ouint
) et retourne leur somme. - Définir une fonction
moyenne_trois_arguments
qui accepte trois arguments (supposés de typefloat
ouint
) et retourne leur moyenne.
Modifier la définition de fonction ci-dessous afin que cette fonction accepte un argument que nous supposerons être une liste puis retourne la somme des éléments de cette liste (ainsi le script ci-dessous devrait afficher 17 car 3+4+10=17 ce qui n'est pas le cas car la définition de la fonction est bogguée).
def somme_elmt_liste(lst): somme_tmp = 1 for elmt in lst: somme_tmp = elmt return somme_tmp somme = somme_elmt_liste([3, 4, 10]) print(somme)
- Définir une fonction qui accepte un argument que nous
supposerons être une liste puis retourne le produit des éléments
de cette liste. On vérifiera que cette fonction retourne bien
120
lorsqu'elle est appelée avec l'argument[1,2,3,4,5]
.
- Écrire une fonction
mamoyenne
qui accepte un seul argument que l'on supposera être une liste et retourne la moyenne des élements de cette liste. On vérifiera que cette fonction retourne bien4
lorsqu'elle est appelée avec l'argument[1,9,2]
. - Créer une fonction
nbr_strictement_positifs
qui accepte un argument de type liste et retourne le nombre d'éléments de cette liste qui sont strictement positifs. On vérifiera que cette fonction retourne bien2
lorsqu'elle est appelée avec l'argument[-1,7,0,-3,4]
. Un élève a 500 euros sur son compte. Son compte est rémunéré à 5%, c'est à dire que le solde est multiplié par 1,05 par chaque année. Il a alors défini une fonction en Python nommée
prediction_solde
qui accepte en argument le solde initial et le nombre d'annee et retourne le solde de ce compte apres ce nombre d'années. Cette fonction est donnée ci-dessousdef prediction_solde(solde_init, nbr_annee): solde_tmp = solde_init for annee in range(nbr_annee): solde_tmp = solde_tmp*1.05 return solde_tmp
- Copier cette définition dans un script puis appeler cette
fonction pour afficher le solde de ce compte après 10 ans (vous
devez trouver environ
814.447313388721
). - En fait les frais de gestion de compte sont de 17,7 euros par an
(somme qui est prélevée avant la rémunération à 5%). Définir une
nouvelle fonction
prediction_solde2
qui accepte en argument le solde initial et le nombre d'annee et retourne le solde de ce compte apres ce nombre d'années. Vérifier que le solde après 10 ans est maintenant de environ 580,69 euros.
- Copier cette définition dans un script puis appeler cette
fonction pour afficher le solde de ce compte après 10 ans (vous
devez trouver environ
- Créer une fonction
renverse_et_incremente
qui accepte un unique argument (on supposera qu'il s'agit d'une liste de nombres) et qui retourne une liste de même longueur obtenue en retournant la liste donnée en argument et en ajoutant1
à chaque élément de cette liste. Ainsi l'appelrenverse_et_incremente([1, 3, 7, 2])
doit retourner[3, 8, 4, 2]
, et l'on vérifie que c'est bien le cas. Pour vous aider, on propose de commencer comme ci-dessous - Créer une fonction
permute_extremites
qui accepte un unique argument que l'on supposera de type liste et qui retourne la liste obtenue en échangeant le premier et le dernier élément de la liste donnée en argument. Ainsi l'appelpermute_extremites([1,4,True,False,3])
doit retourner[3,4,True,False,1]
. - Définir une fonction
un_elmt_en_commun
acceptant deux arguments que l'on supposera être de typelist
et qui retourneTrue
si ces deux listes ont au moins un élément en commun etFalse
dans le cas contraire. Ainsi l'appelun_elmt_en_commun([1,2],[4,3,7])
doit renvoyerFalse
, l'appelun_elmt_en_commun([1,2],[4,2,7])
doit renvoyerTrue
et l'appelun_elmt_en_commun([1,2,7],[1,2,7])
doit aussi renvoyerTrue
. - Définir une fonction
un_elmt_en_commun
acceptant deux arguments que l'on supposera être de typelist
et qui retourneTrue
si ces deux listes ont au moins un élément en commun etFalse
dans le cas contraire. Ainsi l'appelun_elmt_en_commun([1,2],[4,3,7])
doit renvoyerFalse
, l'appelun_elmt_en_commun([1,2],[4,2,7])
doit renvoyerTrue
et l'appelun_elmt_en_commun([1,2,7],[1,2,7])
doit aussi renvoyerTrue
.
- Définir une fonction
5 Cryptage
Dans toute cette partie on considérera les 26 lettres majuscules non accentuées de l'alphabet latin numérotées dans l'ordre alphabétique de 0 à 25. Pour chaque entiers a et b on s'interressera à la transformation qui à la lettre d'indice x associe la lettre d'indice (ax+b)%26.
Pour toute cette section on fournit les fonctions ci-dessous dont il
est inutile de comprendre le code. La signification de leurs
arguments et de la valeur retournée est décrite dans la docstring de
la fonction, c'est à dire dans la châine de caractère juste sous la
ligne commençant par def
.
def indice_lettre(l): """Retourne l'indice entre 0 et 25 de son argument si ce dernier est bien un caractère majuscule non accentué (en python un caractère est une chaîne de caractères de longueur 1), sinon arrête l'exécution en provoquant une erreur. Args: l: chaîne de carcatère Retourne: Un entier entre 0 et 25 """ if not type(l) is str: raise Exception("L'argument n'est pas une chaîne de caractère") if len(l) != 1: raise Exception("La chaîne de caractère n'est pas un caractère seul") indice_ascii = ord(l) if indice_ascii < ord("A") or indice_ascii > ord("Z"): raise Exception("Le caractère n'est pas une lettre majuscule non accentuée") return indice_ascii - ord("A")
def lettre_d_indice(n): """Retourne le caractère majuscule non accentué d'indice n si n est un entier compris entre 0 et 25, dinon arrête l'exécution en provoquant une erreur. Args: n: entier compris entre 0 et 25 Retourne: Un caractère majuscule. """ if not type(n) is int: raise Exception("L'argument n'est pas un entier "+str(type(n))) if n < 0 or n > 25: raise Exception("L'entier n n'est pas compris entre 0 et 25") return chr(n+ord("A"))
5.1 TP
Pour chaque nouveau programme de ce TP, on commencera par
copier-coller les définitions des fonctions indice_lettre
et
lettre_d_indice
ci-dessus
- Afficher les valeurs retournées par les appels
indice_lettre("A")
,indice_lettre("B")
,indice_lettre("Z")
lettre_d_indice(0)
,lettre_d_indice(1)
,lettre_d_indice(25)
et expliquer en quoi cela correspond aux valeurs attendues. - Afficher les valeurs retournées par
lettre_d_indice(indice_lettre("A"))
,lettre_d_indice(indice_lettre("Z"))
,indice_lettre(lettre_d_indice(0))
etindice_lettre(lettre_d_indice(25))
. Expliquer ces valeurs. On s'interesse au cryptage où le caractère d'indice
n
(oùn
est compris entre 0 et 25) est crypté en le caractère d'indice(21*n+5)% 26
. Ainsi le caractère"A"
- qui est d'indice
indice_lettre("A")
, c'est à dire0
; - est crypté en le caractère d'indice
(21*0+5)% 26
, soit d'indice5
; - c'est à dire en
lettre_d_indice(5)
, soit en"F"
Les étapes ci-dessous sont transcrites en python ci-dessous
indice_lettre_depart = indice_lettre("A") indice_lettre_cryptee = (21*indice_lettre_depart+5)% 26 lettre_cryptee = lettre_d_indice(indice_lettre_cryptee) print(lettre_cryptee)
- Vérifier comme ci-dessus que le caractère
"B"
est crypté en le caractère"A"
. - Écrire une fonction nommée
cryptage_a21_b5_car
qui accepte un argument que nous supposerons être un caractère majuscule non accentué et qui retourne le caractère crypté. Vérifier que les valeurs retournées par les appelscryptage_a21_b5_car("A")
etcryptage_a21_b5_car("B")
sont cohérentes. - Écrire une fonction
cryptage_a21_b5_str
qui accepte un unique argument que nous supposerons de typestr
et retourne cette chaîne de caractères cryptée caractère par caractère à l'aide de la fonctioncryptage_a21_b5_car
(ainsi l'appelcryptage_a21_b5_str("AB")
doit retourner"FA"
carcryptage_a21_b5_car("A")
retourne"F"
etcryptage_a21_b5_str("B")
retourneA
). Pour cela on rappelle que l'operateur de concaténation en python est+
(donc par exempleprint("M." + " " + "Bosché")
affiche"M. Bosché"
). - Écrire deux fonctions nommées
cryptage_a5_b1_car
etcryptage_a5_b1_str
analoguent àcryptage_a21_b5_car
etcryptage_a21_b5_str
mais où le caractère d'indicen
est crypté en le caractère d'indice(5*n+1)% 26
. On vérifiera que l'appelcryptage_a5_b1_car("A")
retourneB
. - Afficher la valeur retournée par
cryptage_a5_b1_str(cryptage_a21_b5_str("HELLOWORLD"))
. À quoi correspont la fonctioncryptage_a5_b1_str
pour la fonction de cryptagecryptage_a21_b5_str
?
- Écrire deux fonctions nommées
Écrire une fonction nommée
cryptage_a_b_car
- qui accepte trois arguments que nous appellerons
a
,b
etl
où nous supposerons quea
etb
sont des entiers etl
un caractère majuscule non accentué - et qui retourne la lettre d'indice
(a*n+b)% 26
.
On vérifiera que l'appel
cryptage_a_b_car(21,5,"A")
retourne la même chose quecryptage_a21_b5_car("A")
à savoir"F"
.- qui accepte trois arguments que nous appellerons
- Écrire une fonction
cryptage_a_b_str
qui accepte trois arguments que nous appelleronsa
,b
etl
où nous supposerons quea
etb
sont des entiers etl
une chaîne de caractères majuscules non accentués et qui retourne la chaîne de caractère obtenue en cryptantl
lettre par lettre à l'aide decryptage_a_b_str
. On vérifiera que l'appelcryptage_a_b_str(21, 5, "AB")
retourne"FA"
.
- qui est d'indice
Décrypter le texte suivant en sachant qu'il est obtenu par l'appel
cryptage_a_b_str(a, b, texte)
où texte est un texte écrit en français (la ponctuation et les espaces ont été enlevés ainsi que les accents) eta
etb
sont des entiers (que l'on peut supposer compris entre0
et25
). Aide: parmi les 26*26=676 combinaisons possibles pour les entiers a et b, on pourra ne s'intéresser qu'aux combinaisons qui à partir detexte_crypte
produisent une chaîne de caractères comportant au moins 50 caractères"R"
, 30 caractères"A"
, moins de 10 caractères"Z"
et moins de 10 lettre"W"
.texte_crypte="WVXIVEIVXVAMNAMXGBEVBEWVKINARNDXRPAXMDMBVXVANXXVLCWVVANMDPANWVRPAXDGVINAMTBVWDZAPINARVWPBCWDPBWVLVEIDXGVXGIPDMXGVWOPLLVXPAMWVXXVBWVXRNBXVXGVXLNWOVBIXEBCWDRXVMGVWNRPIIBEMDPAGVXZPBQVIAVLVAMXPAMIVXPWBGVUEPXVIGNAXBAVGVRWNINMDPAXPWVAAVWWVWVXGIPDMXANMBIVWXDANWDVANCWVXVMXNRIVXGVWOPLLVNKDATBVRVMMVGVRWNINMDPARPAXMNLLVAMEIVXVAMVNMPBXWVXLVLCIVXGBRPIEXXPRDNWWVBIINEEVWWVXNAXRVXXVWVBIXGIPDMXVMWVBIXGVQPDIXNKDATBVWVXNRMVXGBEPBQPDIWVZDXWNMDKVMRVBUGBEPBQPDIVUVRBMDKEPBQNAMVMIVNRONTBVDAXMNAMRPLENIVXNQVRWVCBMGVMPBMVDAXMDMBMDPAEPWDMDTBVVAXPDVAMEWBXIVXEVRMVXNKDATBVWVXIVRWNLNMDPAXGVXRDMPJVAXKPAGVVXGVXPILNDXXBIGVXEIDARDEVXXDLEWVXVMDARPAMVXMNCWVXMPBIAVAMMPBSPBIXNBLNDAMDVAGVWNRPAXMDMBMDPAVMNBCPAOVBIGVMPBX"
La question précédente a montré que le fait de crypter un même caractère toujours de la même façon fragilise la méthode de cryptage. On décide donc de crypter des blocs de deux caractères d'un coup au lieu de crypter les caractère un à un. Pour crypter une chaîne constituée de deux caractères:
- on récupère l'indice
x
de la première lettre; - on récupère l'indice
y
de la seconde lettre; - le première caractère de la chaîne cryptée sera alors la
lettre d'indice
(x+9*y) % 26
et le second la lettre d'indice(15*x+6*y) % 26
.
En python, le cryptage de la chaîne
"AB"
s'écrit doncmsg = "AB" x = indice_lettre(msg[0]) y = indice_lettre(msg[1]) x_crypte = (x+9*y) % 26 y_crypte = (15*x+6*y) % 26 lettre_1_crypt = lettre_d_indice(x_crypte) lettre_2_crypt = lettre_d_indice(y_crypte) msgc = lettre_1_crypt + lettre_2_crypt print(msgc)
- Vérifier que
"CD"
est crypté en"DW"
. - Écrire une fonction nommée
crypt_a1_b9_c15_d6_bloc
qui accepte une chaîne de caractère dont on supposera qu'elle est de longueur2
et qui retourne la chaîne cryptée. On vérifiera que l'appelcrypt_a1_b9_c15_d6_bloc("BO")
retourne"XV"
. - Pour crypter une chaîne de longueur quelconque on doit tout
d'abord commencer par la concatener avec
"Z"
si sa longueur est impaire afin d'obtenir une chaîne de longueur paire. Écrire une fonction nomméeremplissage
qui accepte un unique argument que l'on supposera être une chaîne de caractères et qui retourne la même chaîne si sa longueur est paire et la chaîne concatenée avec"Z"
sinon. On vérifiera que l'appelremplissage("SIO")
retourne"SIOZ"
et que l'appelremplissage("BOOM")
retourne"BOOM"
. - Écrire une fonction nommée
crypt_a1_b9_c15_d6_str
qui accepte un unique argument que l'on supposera de typestr
et retourne cette chaîne une fois cryptée. On vérifiera que l'appelcrypt_a1_b9_c15_d6_str("JEDETESTELEPROFDEMATH"))
retourne"TDNRDXHUZWJUNBGPICPKYV"
. À cette question on transforme une chaîne de deux caractères de la façon suivante:
- on récupère l'indice
x
de la première lettre; - on récupère l'indice
y
de la seconde lettre; - le première caractère de la chaîne cryptée sera alors la
lettre d'indice
(6*x+17*y) % 26
et le second la lettre d'indice(11*x+y) % 26
.
Questions:
- Écrire une fonction nommée
trans_a6_b17_c11_d1_bloc
qui accepte une chaîne de caractère dont on supposera qu'elle est de longueur2
et qui retourne la chaîne transformée comme expliquée ci-dessus. - Observer ce que retournent
trans_a6_b17_c11_d1_str(crypt_a1_b9_c15_d6_str("LAVIEENROSE"))
ettrans_a6_b17_c11_d1_str(crypt_a1_b9_c15_d6_str("HELLOWORLD"))
. À votre avis, qu'esttrans_a6_b17_c11_d1_str
pour la fonction de cryptagecrypt_a1_b9_c15_d6_str
?
- on récupère l'indice
- on récupère l'indice
En cryptant les messages comme dans les deux questions précédentes mais avec d'autres coefficients (ainsi il existe des entiers a,b,c,d que l'on peut supposer compris entre 0 et 25 tels que la chaîne obtenue à partir d'une chaîne de longueur 2 soit celle dont la première lettre est d'indice
(a*x+b*y) % 26
et la seconde celle d'indice(c*x+d*y) % 26
…) on a obtenu le texte crypté ci-dessoustexte_crypte = "SDSUYQGOAJRFOCRGUYRFUXVUQAHYBJSDEIJJGZALLZWYBMAEUKDFBXRDEYNAOCKETYDHMNULUGOORKPJBPUYRFWTGVNNDHMNGZDFOKRFANEWUMULOCWYGZDFUYAJITMNMPYVPJWLYRXDEDEIHRXFBJYRMAHEOCSBOJWRWGIILSEQPTEDAWUECWVUYIPFTPXLBVXFBJGZBXSZULNZOCMAOJQHLZEVNYGKYRPIUVIKXUOCSGIJRFZAVHIIIDXUOIVHQAYVGZUMSUYQGOAJRFLJXFRDEYNAOCSJDFATVUIIELGVRDUVFOGIDHWZNNUMXDFBEWVHQANAXLKSSDQHAJRFJGQUSDXUGICSIILSOCOJUFEOATVUALSDIKIXKCMNCZSZOHEIUEQSWEJJGZSUOCRFSPRFELGVEQUMLZOHBXCABVQAYVALSDLOAMGZKCEXGZKATBIAOPALIIJPQUYVEDQNKJBXIAUXVUUVFOGIDHSPRFPTBVQSINOJYIEYKCVHQAYVWYVVOCRDUXEVANCIFBALJTBVJGQUSDXUHRJJIARQXFEDIIVUNNRGYOTPZDBXIAUXVUUYSWDTUVLOWYNBOCUYMNMSAJGZUMEYANCDTBEWZAVHQAANGZIJXFAJRFALUMDROCALOHBXCABVQAVUWYMNYIEYKCVHQALIRFALOCDFPJKSSGIIWYDHYHHRPJBRYPAJLSAMBVKSRFZACSEDSGHAGKUMLZORNAOCGUIAOPWYEIGODFCSFCWYNGXDALSJLORDVHMNTBMNTPTBMNZNBVHRXDRDSZIDHXDHVHQAANGZYRSDELGVRDXFZVUVIKTBHRKQWYUXDUGIDHMNPTSTLSEQPODHVLBPIVTYWYOFGIFOHRPJQUSUYQGOAJRFWTXDIIBWLBHXRDDHIDXDMNDTUMJGOCIXUKKEVUALOKZZEWVHQAYVKSUPOCLBALSDNAEQSWDFNNMNKZKZCNYRVUIDXDKSSDAEKSRFZACSEDIDXDQUSUYQGOAJRFEIVTWYNYKMZMDHHXSDIKIXKCMNCZSZOHEIXFEDYHXFBJSDLOAMGZWEFIFZQHLBEDEDRKQSADXUKYQSIXJWOCEYTBLJOCOCELRKVHIAOPSDALBZBJVHQAHYEDTPXZGZDHIIQHUZBVQUDFXFEDIIVUNNPOJJLBVHMPYVGZALIXLOGIDHIDVLYIEYKCVHQAANDFYIRFWEYOOCYQGOGZLSBPRDUYRFANBVEDGZAJZAEQRGBRYPPOJJYIEYKCVHQATCOCUKMAALIIIIYRXUEWIIKEVUIIRGOCKZUQJGPNOCWERFIIPOUGAMZDOCLBANAJRFTPBVOCALWGLZEIGOPJAJZAUEQSMBRFEIOCRFSPCJYBOCALEYANCDTBEWZAVHQASTOJCHDTSDHXHROCPTVHXDIIPTUFTBYRSDALBZBJVHQACFQLRDRXRFOJEDWGKPSUHRKSJJGZKCMPYVGZALSDXLKSTBLTWYOPCPOPEIJJYIEYKCVHQAANDFYIRFWEYOOCYQGOSDGZZANNMAJWRXKSSDQHAJRFJGQUSDXUXFEDYHQUSDUVOJHLEDWGALVUIIQHUZBVQUDFXFEDIIVUNNPOJJLBVHMPYVGZALIXLOGIDHIDQSPTWEQXJJOCUKMAALEYHYSZULNZTPLBXZUVSUGIDHRGYIEYKCVHQANAOCZADHEVXFZVUVEIUEQSIXINOJTBIILOQAANBNWYDUTPPNWRKCJJMSXSATEVDRQARKKSRDKSXFEWIIGZUMSUYQGOAJRFSURFTYDHQSLJBPCSEDSWNACSZAHRNNNBOCZAGKKAGKPTWYNBOCNDNNMAKEVUSUDFUXSTLJNNNBIAQHCDTBEWZAVHQAANTBWEEILBWYMNNBOCGUOHWRIKAJRFUMPIFBMNOCTPIAOPPTVHXDOKOCGUOHWRIKAJRFIISPCJIHGIDHWZOJEYVULDSJUMXUOCSGJSUKOPEIHLBJAJHEBNWYATEOQLSGATVULBHRKSSDEDPTWYMNYIEYKCVHQABWYOVLUKEDKEVUALBZBJEQWTXDUMYVSGAQOJSGIDSZUMAJRFBXKSGOGZOCMNEDZEAEAJWGEDWGQNHXALLJRFKANNQSQLCSYVKYQSALLJRFLJLBXZUVSUGIDHWZEVAJUVMNADXUKYQSUYEIRDHXVHBVEDRFRDIAVWCAIIALEDYRCDTBEWZARDDHALMVOPALSUZVUXVUQAYVALGZYRPOOCEDAWRFLJOCALIXLOGIDHWZALOKUGOOOJIIPOJJIAOPLBXZUVSUGIDHWZADXUAMNBOCSWAJUMAJRFLJOCOCKETHEDNBJJYQTPALPTTBQUSDCDTBEWZAVHQARKJJYIEYKCVHQAOJYRSDEDPJQARKOCOCKETHEDNBOCWCKEZVGZSUZAAMMNKEVUOJWGSUCSEDUMSDCIUGBMEWIIKEVUEVWLCBQSLSOCXFATSJIIGZUMSUYQGOAJRFLJKSSDEDOCALADEWZAGKUMYVSGGUTBIIPORFRGDHIITHGZALUMDRVTBVOCOCOFDHAJRFOJSGVCUCRKJJBJAJBZHRIAIJDHPOWUVPYODHRDTPALWEDTZZBXIAUXVUDHWYZAQUUYWGDERDGZNBDNRDTPBVOCDHZAFZRJEYXDOCYRKEVUCSEDLJNNLJOCSWRKBVQAYVWRCHOCTPBJAJBZDHIAOXDHPOPREVSWALKCITPCSJSUHRRDLBRXYACFPTEDLOWYWEMWIAXUOCUYEIEWVHBVEDZNVHEORGOCKCEXEOGIQUIIDEUKKETPTBQULJJHEDIIVUBJAJBZOCHLBMKYQSVUUMYVSWRKBVQARKNNKCDHOJMNSGOLSUYQGOAJRFUMSQVUSJDFWLMNIJKJWENOYIWEPTNNWGSDGXDHUZEWNNWGWYSDEDNDRDNDOCKCDHAJWREIAGSKHRAMTPHRKSSDEDOCPFNNRGRXVHHRXFATOOAXVHQARKTV"
Décrypter ce message en sachant que le message de départ contient le mot
"IMPOT"
6 Tri
Dans cette section nous nous intéresserons à différentes façons de trier dans l'ordre croissant une liste de taille quelconque.
6.1 Tri à bulle
Pour trier (rappel: nous trierons toujours dans l'ordre croissant)
une liste L
avec le tri à bulle, on
- parcourt tous les indices
i
pour cette liste en allant du plus petit indice possible (à savoir0
) à l'avant-dernier (à savoirlen(L)-2
); - à chaque fois que l'on tombe sur un indice
i
tel queL[i]>L[i+1]
(ce qui signifie que l'élément d'indice courant, à savoiri
, et le suivant ,ne sont pas dans le bon ordre) on échange ces deux éléments de position dans la listeL
; - si on n'a jamais
L[i]>L[i+1]
, c'est que la liste est triée dans l'ordre croissant. Sinon on reprend les étapes précédentes.
Voir cette animation pour un exemple de fonctionnement de cette
algorithme avec la liste L=[56,22,14,5,35,69,8,15,12,7]
.
Remarquez que sur cet exemple, le tri nécessite neuf parcours de la
liste L
. On s'aperçoit que les éléments les plus grand
"remontent" la liste alors que les éléments plus petits descendent.
Si à la fin de chaque parcourt on coupe la liste en une première
partie non triée et une seconde triée on obtient le tableau suivant
Numéro de parcours | Début non trié | Fin triée |
---|---|---|
1 | [22,14,5,35,56,8,15,12,7] |
[69] |
2 | [14,5,22,35,8,15,12,7] |
[56,69] |
3 | [5,14,22,8,15,12,7] |
[35,56,69] |
4 | [5,14,8,15,12,7] |
[22,35,56,69] |
5 | [5,8,14,12,7] |
[15,22,35,56,69] |
6 | [5,8,14,12,7] |
[15,22,35,56,69] |
7 | [5,8,12,7] |
[14,15,22,35,56,69] |
8 | [5,8,7] |
[12,14,15,22,35,56,69] |
9 | [5,7] |
[8,12,14,15,22,35,56,69] |
10 | [] |
[5,7,8,12,14,15,22,35,56,69] |
Le tri à bulle appliqué en python mais "à la main" (comprendre sans
boucle) à la liste [5,8,9,4]
est donné ci-dessous. Des
commentaires ont été ajoutées pour documenter le code et des
instructions print
pour expliquer l'exécution.
Le but de cette sous-section est de coder cet algorthme de tri puis de visualiser ses performances.
L = [8,5,9,4] print("Liste de départ: ", L) # PARCOURS 1 print("- PARCOURS 1:") # # Échange 1 # # Le plus petit indice i>=0 et i<=2 tel que L[i]>L[i+1] est i=0 donc # on échange L[0] et L[1] tmp = L[0] L[0] = L[1] L[1] = tmp # print(" Après échange 1: ", L) # # Échange 2 # # Maintenant L = [5,8,9,4]. On continue le parcours à partir de i=1 et # on remarque que le plus petit indice i avec i>=1 et i<=2 tel que # L[i]>L[i+1] est i=2 donc on échange L[2] et L[3] tmp = L[2] L[2] = L[3] L[3] = tmp # Maintenant L = [5,8,4,9] print(" Après échange 2: ", L) # # Il n'y a pas d'indice i avec i>=2 et i<=2 tel que L[i]>L[i+1]. Comme # on a effectué des échanges pendant le parcours courant on effectue # un autre parcours car on n'est pas sûr que la liste soit triée (et # d'ailleurs elle ne l'est pas). # # PARCOURS 2 print("\n- PARCOURS 2:") # # Échange 3 # # Maintenant L = [5,8,4,9]. Le plus petit indice i>=0 et i<=2 tel que # L[i]>L[i+1] est i=1 donc on échange L[1] et L[2] tmp = L[1] L[1] = L[2] L[2] = tmp # Maintenant L = [5,4,8,9] print(" Après échange 4: ", L) # Il n'y a pas d'indice i avec i>=2 et i<=2 tel que L[i]>L[i+1]. Comme # on a effectué des échanges pendant le parcours courant on effectue # un autre parcours car on n'est pas sûr que la liste soit triée (et # d'ailleurs elle ne l'est pas). # # PARCOURS 3 print("\n- PARCOURS 3:") # # Échange 4 # # Maintenant L = [5,4,8,9]. Le plus petit indice i>=0 et i<=2 tel que # L[i]>L[i+1] est i=0 donc on échange L[0] et L[1] tmp = L[0] L[0] = L[1] L[1] = tmp # Maintenant L = [4,5,8,9] print(" Après échange 5: ", L) # # Il n'y a pas d'indice i avec i>=1 et i<=2 tel que L[i]>L[i+1]. Comme # on a effectué des échanges pendant le parcours courant on effectue # un autre parcours car on n'est pas sûr que la liste soit triée (en # fait elle l'est). # # PARCOURS 4 print("\n- PARCOURS 4:") # # Quel que soit l'indice i, 0<=i<=2, on n'a jamais L[i]>L[i+1]: la # liste est triée et on s'arrête là. print("La liste triée: ", L)
Compléter les programme suivant afin qu'il affiche la liste
[5,8,9,4]
triée à l'aide du tri à bulle.L = [5,8,9,4] liste_triee_bool = False while not liste_triee_bool: liste_triee_bool = True for i in range(len(L)-1): if L[i] > L[i+1]: tmp = L[i] ... = ... ... = ... liste_triee_bool = ... print(L)
- Écrire une fonction nommée
tri_a_bulle_en_place
qui accepte un unique argument que l'on supposera être une liste de nombres et qui trie cette liste. - Écrire une fonction nommée
tri_a_bulle_sans_effet_de_bord
qui accepte un unique argument que l'on supposera être une liste de nombres et retourne cette liste triéesans modifier cette liste
(Autrement dit on commencera par créer une copie de la liste passée en argument).
- Écrire une fonction nommée
- Sauvegarder le script de la question précédente dans un nouveau
fichier puis:
ajouter au tout début de ce script les lignes suivantes (qui importent des modules python, le premier s'appelant
timeit
et permet de chronométrer des portions de code, et le second s'appelantmatplotlib.pyplot
et permettant de tracer des graphiques)import time import gc import random import matplotlib.pyplot as plt
ajouter à la fin du script les lignes suivantes (qui définissent une fonction qui trace le temps que met en moyenne votre fonction
tri_a_bulle_en_place
à trier une liste en fonction de la taille de cette liste)def performance_tri_a_bulle(taille_max, nbr=40): """Affiche le temps nécessaire en moyenne pour trier une liste avec le tri à bulle en fonction de la taille de cette liste. Args: taille_max: considérer les liste de longueur comprises entre 0 et taille_max. nbr: nombre de valeurs pour le calculs des moyennes. Retourne: None """ plt_x = [None]*(taille_max+1) plt_y = [None]*(taille_max+1) i = 0 for taille in range(1,taille_max+1): i += 1 temps_cumule = 0 gc.disable() for j in range(nbr): L = [random.randint(0,255) for xx in range(taille)] t_avant = time.clock() tri_a_bulle_en_place(L) t_apres = time.clock() temps_cumule += (t_apres-t_avant)*1000 gc.enable() gc.collect() plt_x[i] = taille plt_y[i] = temps_cumule/nbr fig = plt.figure() ax = fig.add_subplot(111) ax.plot(plt_x, plt_y, 'or', label="Tri à bulle") ax.set_title("Temps pour trier une liste avec le tri à bulle en fonction\n" + "de la taille de la liste.") ax.set_xlabel("Taille de la liste") ax.set_ylabel("Temps (en ms)") legend = ax.legend(loc='upper center', shadow=True) plt.show() performance_tri_a_bulle(100)
- Exécuter ce script et observer le graphique. Pour trier une liste deux fois plus longue, faut-il à votre avis plus de deux fois plus de temps en général?
Copier la définition de
tri_a_bulle_en_place
en une nouvelle fonctiontri_a_bulle_en_place_ameliore
et améliorer les performances de cette fonction de tri en observant- que après le ieme parcourt les derniers i éléments sont déjà à leur place;
- qu'il est inutile de reprendre le parcourt en début de liste à chaque fois mais uniquement à partir de la position précédent le premier échange du parcours précédent puisque les éléments situant avant ce premier échange sont dans l'ordre croissant.
Aide: on gardera et actualisera en mémoire le numéro de parcourt courant dans une variable nommée
num_parcours_courant
ainsi que la position du précédent échange dans une variable nomméepos_premier_echange
(que l'on initialisera à0
).Vérifier que l'appel
tri_a_bulle_en_place_ameliore([[5,1,3,2,0])
renvoie un résultat cohérent.def performance_tri_a_bulle_ameliore(taille_max, nbr=40): """Affiche le temps nécessaire en moyenne pour trier une liste avec le tri à bulle en fonction de la taille de cette liste. Args: taille_max: considérer les liste de longueur comprises entre 0 et taille_max. nbr: nombre de valeurs pour le calculs des moyennes. Retourne: None """ plt_x = [None]*(taille_max+1) plt_y1 = [None]*(taille_max+1) plt_y2 = [None]*(taille_max+1) i = 0 for taille in range(1,taille_max+1): i += 1 temps_cumule = 0 for j in range(nbr): L = [random.randint(0,255) for xx in range(taille)] t_avant = time.clock() tri_a_bulle_en_place(L) t_apres = time.clock() temps_cumule += (t_apres-t_avant)*1000 plt_x[i] = taille plt_y1[i] = temps_cumule/nbr i = 0 for taille in range(1,taille_max+1): i += 1 temps_cumule = 0 for j in range(nbr): L = [random.randint(0,255) for xx in range(taille)] t_avant = time.clock() tri_a_bulle_en_place_ameliore(L) t_apres = time.clock() temps_cumule += (t_apres-t_avant)*1000 plt_y2[i] = temps_cumule/nbr fig = plt.figure() ax = fig.add_subplot(111) ax.plot(plt_x, plt_y1, 'or', label="Trie à bulle non amélioré") ax.plot(plt_x, plt_y2, 'ob', label="Trie à bulle amélioré") ax.set_title("Comparaison avec l'algorithme de tri ameliore") ax.set_xlabel("Taille de la liste") ax.set_ylabel("Temps (en ms)") legend = ax.legend(loc='upper center', shadow=True) plt.show() performance_tri_a_bulle_ameliore(100)
Pour ceux qui n'ont pas fini le TD, merci de copier le script suivant dans un fichier puis de l'éxécuter (puis attendre quelques secondes)
import time import gc import random import matplotlib.pyplot as plt def tri_a_bulle_en_place(L): liste_triee_bool = False while not liste_triee_bool: liste_triee_bool = True for i in range(len(L)-1): if L[i] > L[i+1]: tmp = L[i] L[i] = L[i+1] L[i+1] = tmp liste_triee_bool = False return L def tri_a_bulle_en_place_ameliore(L): liste_triee_bool = False passe = 0 pos_echange = 0 while not liste_triee_bool: passe += 1 liste_triee_bool = True pos_deb = max(0, pos_echange-1) pos_echange=None for i in range(pos_deb, len(L)-passe): if L[i] > L[i+1]: if pos_echange is None: pos_echange = i tmp = L[i] L[i] = L[i+1] L[i+1] = tmp liste_triee_bool = False return L def performance_tri_a_bulle_ameliore(taille_max, nbr=40): """Affiche le temps nécessaire en moyenne pour trier une liste avec le tri à bulle en fonction de la taille de cette liste. Args: taille_max: considérer les liste de longueur comprises entre 0 et taille_max. nbr: nombre de valeurs pour le calculs des moyennes. Retourne: None """ plt_x = [None]*(taille_max+1) plt_y1 = [None]*(taille_max+1) plt_y2 = [None]*(taille_max+1) i = 0 for taille in range(1,taille_max+1): i += 1 temps_cumule = 0 for j in range(nbr): L = [random.randint(0,255) for xx in range(taille)] t_avant = time.clock() tri_a_bulle_en_place(L) t_apres = time.clock() temps_cumule += (t_apres-t_avant)*1000 plt_x[i] = taille plt_y1[i] = temps_cumule/nbr i = 0 for taille in range(1,taille_max+1): i += 1 temps_cumule = 0 for j in range(nbr): L = [random.randint(0,255) for xx in range(taille)] t_avant = time.clock() tri_a_bulle_en_place_ameliore(L) t_apres = time.clock() temps_cumule += (t_apres-t_avant)*1000 plt_y2[i] = temps_cumule/nbr fig = plt.figure() ax = fig.add_subplot(111) ax.plot(plt_x, plt_y1, 'or', label="Trie à bulle non amélioré") ax.plot(plt_x, plt_y2, 'ob', label="Trie à bulle amélioré") ax.set_title("Comparaison avec l'algorithme de tri ameliore") ax.set_xlabel("Taille de la liste") ax.set_ylabel("Temps (en ms)") legend = ax.legend(loc='upper center', shadow=True) plt.show() performance_tri_a_bulle_ameliore(100)
6.2 Tri par sélection
Le tri par sélection est celui du joueur de carte: on trie les éléments en parcourant la liste "de gauche à droite" en gardant la partie de gauche triée et en insérant l'élément courant à la bonne position dans cette partie triée de la liste (donc située à gauche de la position courante).
Le tri par sélection appliqué en python mais "à la main"
(comprendre sans boucle) à la liste [5,8,6,4]
est donné
ci-dessous. Des commentaires ont été ajoutées pour documenter le
code et des instructions print
pour expliquer l'exécution.
lst_a_trier = [8,5,6,4] print("- Étape 0:") print(" lst_a_trier: ", lst_a_trier) # -> [5,8,6,4] # Étape 1: on place les deux premiers éléments dans l'ordre. print("- Étape 1:") elmt_courant = lst_a_trier[1] lst_a_trier[1] = lst_a_trier[0] lst_a_trier[0] = elmt_courant print(" lst_a_trier: ", lst_a_trier) # -> [5,8,6,4] # Étape 2: on place le troisième élément pour que les trois premiers soient triés print("- Étape 2:") elmt_courant = lst_a_trier[2] lst_a_trier[2] = lst_a_trier[1] lst_a_trier[1] = elmt_courant print(" lst_a_trier: ", lst_a_trier) # -> [5,6,8,4] # Étape 4: on place le cinquième élément pour que les cinq premiers soient triés print("- Étape 4:") elmt_courant = lst_a_trier[3] lst_a_trier[3] = lst_a_trier[2] lst_a_trier[2] = lst_a_trier[1] lst_a_trier[1] = lst_a_trier[0] lst_a_trier[0] = elmt_courant print(" lst_a_trier: ", lst_a_trier) # -> [5,6,8,4]
Pour les questions suivantes on utilisera la fonction suivante qui accepte une liste comme argument et retourne l'indice de son minimum
Compléter les programme suivant afin qu'il affiche la liste
[5,8,9,4]
triée à l'aide du tri par sélection.lst_a_trier = [8,5,9,4] for i in range(1, len(lst_a_trier)): elmt_courant = lst_a_trier[i] j=i while j>0 and lst_a_trier[j-1]>elmt_courant: lst_a_trier[j] = lst_a_trier[...] j = j-1 lst_a_trier[...] = elmt_courant
- Écrire une fonction nommée
tri_par_insertion_en_place
qui accepte un unique argument que l'on supposera être une liste de nombres et qui retourne cette liste triée. - Écrire une fonction nommée
tri_par_insertion_sans_effet_de_bord
qui accepte un unique argument que l'on supposera être une liste de nombres et retourne cette liste triéesans modifier cette liste
(Autrement dit on commencera par créer une copie de la liste passée en argument). - Créer un nouveau script puis
ajouter (si elles n' sont pas déjà) au tout début de ce script les lignes suivantes (qui importent des modules nécessaires pour la suite)
import time import random import gc import matplotlib.pyplot as plt
- ajouter à la suite la définition de la fonction
tri_a_bulle_en_place
écrite au TP précédent ajouter à la suite du script les lignes suivantes (où est définie puis appelée une fonction
performance_tri_par_sélection
qui tracent le temps que met en moyenne votre fonctiontri_par_sélection
à trier une liste en fonction de la taille de cette liste)def performance_tri_par_sélection(taille_max, nbr=40): """Affiche le temps nécessaire en moyenne pour trier une liste avec le tri par sélection en fonction de la taille de cette liste. Args: taille_max: considérer les liste de longueur comprises entre 0 et taille_max. nbr: nombre de valeurs pour le calculs des moyennes. Retourne: None """ plt_x = [None]*(taille_max+1) plt_y = [None]*(taille_max+1) i = 0 gc.disable() for taille in range(1,taille_max+1): gc.collect() i += 1 temps_cumule = 0 for j in range(nbr): L = [random.randint(0,255) for xx in range(taille)] t_avant = time.clock() tri_par_insertion_en_place(L) t_apres = time.clock() temps_cumule += (t_apres-t_avant)*1000 plt_x[i] = taille plt_y[i] = temps_cumule/nbr fig = plt.figure() ax = fig.add_subplot(111) ax.plot(plt_x, plt_y, "og", label="Tri par sélection") ax.set_xlabel("Taille de la liste") ax.set_ylabel("Temps (en ms)") legend = ax.legend(loc='upper center', shadow=True) gc.enable() plt.show() performance_tri_par_sélection(100)
- Souvegarder le script de la question précédente dans un nouveau
fichier puis:
ajouter au tout début de ce script les lignes suivantes
import time import random import gc import matplotlib.pyplot as plt
ajouter à la fin du script les lignes suivantes (qui tracent le temps que met en moyenne votre fonction
tri_par_sélection
à trier une liste en fonction de la taille de cette liste)def performance_tri_par_insertion_et_a_bulle(taille_max, nbr=40): """Affiche le temps nécessaire en moyenne pour trier une liste avec le tri par sélection en fonction de la taille de cette liste. Args: taille_max: considérer les liste de longueur comprises entre 0 et taille_max. nbr: nombre de valeurs pour le calculs des moyennes. Retourne: None """ plt_x = [None]*(taille_max+1) plt_y1 = [None]*(taille_max+1) plt_y2 = [None]*(taille_max+1) i = 0 for taille in range(1,taille_max+1): i += 1 temps_cumule_tri_sel = 0 for j in range(nbr): L = [random.randint(0,255) for xx in range(taille)] t_avant = time.clock() tri_a_bulle_en_place(L) t_apres = time.clock() temps_cumule_tri_sel += (t_apres-t_avant)*1000 plt_x[i] = taille plt_y1[i] = temps_cumule_tri_sel/nbr temps_cumule_tri_sel = 0 for j in range(nbr): L = [random.randint(0,255) for xx in range(taille)] t_avant = time.clock() tri_par_insertion_en_place(L) t_apres = time.clock() temps_cumule_tri_sel += (t_apres-t_avant)*1000 plt_y2[i] = temps_cumule_tri_sel/nbr fig = plt.figure() ax = fig.add_subplot(111) ax.plot(plt_x, plt_y1, 'or', label="Tri à bulle") ax.plot(plt_x, plt_y2, 'og', label="Tri par sélection") ax.set_title("Comparaison du tri à bulle et du tri par insertion") ax.set_xlabel("Taille de la liste") ax.set_ylabel("Temps (en ms)") legend = ax.legend(loc='upper center', shadow=True) plt.show() performance_tri_par_insertion_et_a_bulle(100)
Le script ci-dessous définit une autre fonction de tri nommée
tri_qsort_en_place
qui implémente un algorithme de tri appelé quick-sort et connu comme étant particulièrement rapide (inutile de comprendre comment fonctionnne cet algorithme) puis affiche les performances de ce tri de avec celles des deux tris précédentsimport time import gc import random import matplotlib.pyplot as plt def tri_qsort_en_place_aux(l, fst, lst): if fst >= lst: return i, j = fst, lst pivot = l[fst] while i <=j: while l[i] < pivot: i += 1 while l[j] > pivot: j -= 1 if i<=j: l[i], l[j] = l[j], l[i] i, j = i+1, j-1 tri_qsort_en_place_aux(l, fst, j) tri_qsort_en_place_aux(l, i, lst) def tri_qsort_en_place(l): tri_qsort_en_place_aux(l, 0, len(l)-1) def performance_tri_par_insertion_et_a_bulle_et_qsort(taille_max, nbr=40): """Affiche le temps nécessaire en moyenne pour trier une liste avec le tri par sélection en fonction de la taille de cette liste. Args: taille_max: considérer les liste de longueur comprises entre 0 et taille_max. nbr: nombre de valeurs pour le calculs des moyennes. Retourne: None """ plt_x = [None]*(taille_max+1) plt_y1 = [None]*(taille_max+1) plt_y2 = [None]*(taille_max+1) plt_y3 = [None]*(taille_max+1) i = 0 gc.disable() for taille in range(1,taille_max+1): gc.collect() i += 1 temps_cumule_tri_sel = 0 for j in range(nbr): L = [random.randint(0,255) for xx in range(taille)] t_avant = time.clock() tri_a_bulle_en_place(L) t_apres = time.clock() temps_cumule_tri_sel += (t_apres-t_avant)*1000 gc.collect() plt_x[i] = taille plt_y1[i] = temps_cumule_tri_sel/nbr temps_cumule_tri_bulle = 0 for j in range(nbr): L = [random.randint(0,255) for xx in range(taille)] t_avant = time.clock() tri_par_insertion_en_place(L) t_apres = time.clock() temps_cumule_tri_bulle += (t_apres-t_avant)*1000 plt_y2[i] = temps_cumule_tri_bulle/nbr temps_cumule_tri_qsort = 0 for j in range(nbr): L = [random.randint(0,255) for xx in range(taille)] t_avant = time.clock() tri_qsort_en_place(L) t_apres = time.clock() temps_cumule_tri_qsort += (t_apres-t_avant)*1000 plt_y3[i] = temps_cumule_tri_qsort/nbr gc.enable() fig = plt.figure() ax = fig.add_subplot(111) ax.plot(plt_x, plt_y1, 'or', label="Tri à bulle") ax.plot(plt_x, plt_y2, 'og', label="Tri par sélection") ax.plot(plt_x, plt_y3, 'ob', label="Tri qsort") ax.set_title("Comparaison du tri à bulle, du tri par insertion et du tri qsort") ax.set_xlabel("Taille de la liste") ax.set_ylabel("Temps (en ms)") legend = ax.legend(loc='upper center', shadow=True) plt.show() performance_tri_par_insertion_et_a_bulle_et_qsort(100)
Ce tri vous paraît-il réellement plus performant?
6.3 Fonctions de comparaison et relations d'ordre
Nous allons étendre les tris à des listes de types plus complexes. En effet, les techniques de tri ne s'adressent pas qu'aux listes de nombres. Par exemple, pour élaborer un dictionnaire, il est nécessaires de trier des mots dans l'ordre alphabétique, qui est un ordre sur les chaînes de caractères. Mais on peut aussi souhaiter trier une liste de clients (chaque client étant représenté par un certains nombres de champs). Il est alors nécessaire de préciser l'ordre utilisé pour trier cette liste. On peut par exemple
- trier par date de premier achat puis par ordre alphabétique du nom du client puis par numéro de client;
- ou trier dans l'ordre alphabétique du nom du client puis dans l'ordre inverse du premier achat puis par numéro de client;
et l'on n'obtiendra pas le même résultat en général.
- Dans un fichier, afficher les valeurs renvoyées par les
expression
"AB"<"BA"
,"BA"<"BA"
et"AAA"<"A"
. À quel ordre sur les chaînes de caractère correspond l'opérateur relationel<
en python? - Recopier la définition de votre fonction
tri_par_insertion_en_place
au début d'un nouveau script puis afficher la valeur renvoyée par l'expressiontri_par_insertion_en_place(["AB", "BA", "AA", "BB", "AAAA", "BBB"])
. Qu'en pensez-vous?
- Dans un fichier, afficher les valeurs renvoyées par les
expression
- Dans un fichier, afficher les valeurs renvoyées par les
expression
[1, 7]<[2, 8]
,[1, 7]<[1, 1]
,[3, 4]<[2, 5]
et[2, 5]<[2, 5, 5]
. À quel ordre sur les listes correspond l'opérateur relationel<
en python (grosse aide)? - Recopier la définition de votre fonction
tri_par_insertion_en_place
au début d'un nouveau script puis afficher la valeur renvoyée par l'expressiontri_par_insertion_en_place([[1, 7], [2, 8], [1, 1], [3, 4], [2, 5], [2, 5, 5]])
. Qu'en pensez-vous?
- Dans un fichier, afficher les valeurs renvoyées par les
expression
Écrire une fonction de comparaison
inf_strict_comp_long_puis_ordre_alpha
qui compare deux chaînes de caractères par leur longueur puis (si elles sont de même longueur) en utilisant l'ordre alphabétique. Ainsi cette fonction doit accepter deux arguments (que nous supposerons être des chaînes de caractères) et doit- retourner
True
si le première chaîne de caractère est de longueur strictement plus petite que la seconde (rappel: sic
est une chaîne alorslen(c)
est la longueur de cette chaîne); - retourner
True
si les deux chaînes ont même longueur et la première est strictement plus petite que l'autre dans l'ordre alphabétique (rappel: d'après le premier exercice de ce TP, la chaînec1
est avant la chainec2
pour l'ordre alphabétique si et seulement si l'expressionc1 < c2
retourneTrue
); - retourner
False
sinon.
On pourra s'aider du squelette suivant
def inf_strict_comp_long_puis_ordre_alpha(c1, c2): if len(c1) < len(c2): return ... elif len(c1) == len(c2): if c1 < c2: ... else: ... else: ...
À la suite de ces définitions on affichera les valeurs retournées par les appels
inf_strict_comp_long_puis_ordre_alpha("AA", "B")
,inf_strict_comp_long_puis_ordre_alpha("AA", "AB")
etinf_strict_comp_long_puis_ordre_alpha("DD", "ABC")
et on s'assurera que les valeurs affichées sont cohérentes.- retourner
- Écrire la définition d'une fonction
tri_comp_long_puis_ordre_alpha_en_place
qui trie (en utilisant l'algorithme de tri à bulle ou le tri par sélection, à votre guise) une liste de chaînes de caractères en utilisant l'ordre défini par la fonctioninf_strict_comp_long_puis_ordre_alpha
(c'est à dire que qu'une chaînec1
sera considérée strictement inférieur à une autre chaînec2
si et seulement si l'appelinf_strict_comp_long_puis_ordre_alpha(c1, c2)
retourneTrue
). On affichera la valeur retournée par l'appeltri_comp_long_puis_ordre_alpha_en_place(["AB", "BA", "AA", "BB", "AAAA", "BBB"])
et on vérifiera sa cohérence.
Écrire une fonction de comparaison
inf_strict_comp_inv_long_puis_ordre_alpha
qui compare deux chaînes de caractères dans l'ordre inverse de leur longueur puis (si elles sont de même longueur) en utilisant l'ordre alphabétique.À la suite de ces définitions on affichera les valeurs retournées par les appels
inf_strict_comp_inv_long_puis_ordre_alpha("AA", "B")
,inf_strict_comp_inv_long_puis_ordre_alpha("AA", "AB")
etinf_strict_comp_inv_long_puis_ordre_alpha("AA", "ABC")
.- Écrire la définition d'une fonction
tri_comp_inv_long_puis_ordre_alpha_en_place(l)
qui trie (en utilisant l'algorithme de tri à bulle ou le tri par insertion, à votre guise) une liste de chaînes de caractères en utilisant l'ordre défini par la fonctioninf_strict_comp_inv_long_puis_ordre_alpha
. On affichera la valeur retournée par l'appeltri_comp_inv_long_puis_ordre_alpha_en_place(["AB", "BA", "AA", "BB", "AAAA", "BBB"])
et on vérifiera sa cohérence.
Le but de cet exercice est de trier de plusieurs façons la liste des présidences des États-Unis d'Amérique. Celles-ci sont fournies dans la variable
list_usa_psdt
définie ci-dessous.# Liste des présidences des États-Unis (les mandats successifs du même # présidents sont considérés comme ne faisant qu'une présidence). # Chaque élement de cette liste est lui même une liste composée dans # l'ordre: # # - de la date de début de présidence # - de la date de fin de fin de présidence # - du prénom du président # - du nom du président # # Rmq: Le deuxième prénom (Delano dans Franklin Delano Roosevelt) et # les initiales supplémentaires (S. dans Harry S. Truman) ont été # enlevés sauf pour George W. Bush pour le distinguer de son père... list_usa_psdt = [[1897, 1901, "William", "McKinley"], [1963, 1969, "Lyndon", "Johnson"], [1933, 1945, "Franklin", "Roosevelt"], [1801, 1809, "Thomas", "Jefferson"], [1929, 1933, "Herbert", "Hoover"], [1921, 1923, "Warren", "Harding"], [1881, 1885, "Chester", "Arthur"], [1974, 1977, "Gerald", "Ford"], [1913, 1921, "Woodrow", "Wilson"], [1809, 1817, "James", "Madison"], [1869, 1877, "Ulysses", "Grant"], [1845, 1849, "James", "Polk"], [1969, 1974, "Richard", "Nixon"], [1857, 1861, "James", "Buchanan"], [1865, 1869, "Andrew", "Johnson"], [2009, 2017, "Barack", "Obama"], [1881, 1881, "James", "Garfield"], [1853, 1857, "Franklin", "Pierce"], [1817, 1825, "James", "Monroe"], [1909, 1913, "William", "Taft"], [1989, 1993, "George", "Bush"], [1981, 1989, "Ronald", "Reagan"], [1993, 2001, "Bill", "Clinton"], [1885, 1889, "Grover", "Cleveland"], [1849, 1850, "Zachary", "Taylor"], [1825, 1829, "John", "Adams"], [1893, 1897, "Grover", "Cleveland"], [1829, 1837, "Andrew", "Jackson"], [1841, 1845, "John", "Tyler"], [1945, 1953, "Harry", "Truman"], [1837, 1841, "Martin", "Van Buren"], [1953, 1961, "Dwight", "Eisenhower"], [1797, 1801, "John", "Adams"], [1789, 1797, "George", "Washington"], [2001, 2009, "George", "W. Bush"], [1889, 1893, "Benjamin", "Harrison"], [1901, 1909, "Theodore", "Roosevelt"], [1861, 1865, "Abraham", "Lincoln"], [1923, 1929, "John", "Coolidge"], [1841, 1841, "William", "Harrison"], [1850, 1853, "Millard", "Fillmore"], [1977, 1981, "James", "Carter"], [1961, 1963, "John", "Kennedy"], [1877, 1881, "Rutherford", "Hayes"]]
- Écrire la définition d'une fonction
inf_strict_comp_long_presidence_puis_debut_mandat
qui accepte deux argumentspsdce1
etpsdce2
(où, comme dans la définition delist_usa_psdt
ci-dessus, une présidence est une liste de longueur4
constitutée dans l'ordre du année de début, d'une année de fin, du prénom du président puis du nom du président) et qui renvoieTrue
si la présidencepsdce1
fut strictement plus courte que la présidencepsdce2
;True
si les présidencespsdce1
etpsdce2
étaient de même longueur et la présidencepsdce1
commença avantpsdce2
;False
sinon.
- Écrire la définition d'une fonction
tri_comp_long_presidence_puis_debut_mandat_en_place
qui trie (en utilisant l'algorithme de tri à bulle ou le tri par insertion, à votre guise) une liste de présidences en utilisant l'ordre défini par la fonctioninf_strict_comp_long_presidence_puis_debut_mandat
(c'est à dire que l'on supposera qu'une présidenceprdce1
est strictement inférieur àprdce2
si et seulement si l'appelinf_strict_comp_long_presidence_puis_debut_mandat(prdce1, prdce2)
retourneTrue
). On affichera la valeur retournée par l'appeltri_comp_long_presidence_puis_debut_mandat_en_place(list_usa_psdt)
et on vérifiera sa cohérence.. Écrire la définition d'une fonction
tri_comp_long_puis_alpha_nom_puis_alpha_prenom_puis_debut
qui trie (en utilisant l'algorithme de tri à bulle ou le tri par insertion, à votre guise) une liste de présidences en comparant les présidences- d'abord par leur durée;
- puis par l'ordre alphabétique du nom du président;
- puis par l'ordre alphabétique du prénom du président
- puis dans l'ordre des dates de début de présidence.
On commencera par écrire une fonction de comparaison
inf_strict_comp_long_puis_alpha_nom_puis_alpha_prenom_puis_debut
adéquate. On affichera la valeur retournée par l'appeltri_comp_long_puis_alpha_nom_puis_alpha_prenom_puis_debut(list_usa_psdt)
et on vérifiera sa cohérence.
- Écrire la définition d'une fonction
Ci-dessous est donnée une liste où chaque élément représente une capitale. Plus précisant chaque élément est une liste où
- le permier élement est une chaîne de caractères donnant le pays dont la ville est capitale;
- le second élement est une chaîne de caractères donnant le nom de la capitale;
- le troisième élément donne une estimation du nombre d'habitants de cette capitale.
liste_capitales = [['China', 'Beijing', 20693000], ['India', 'New Delhi', 16787949], ['Japan', 'Tokyo', 13189000], ['Philippines', 'Manila', 12877253], ['Russia', 'Moscow', 11541000], ['Egypt', 'Cairo', 10230350], ['Indonesia', 'Jakarta', 10187595], ['Democratic Republic of the Congo', 'Kinshasa', 10125000], ['South Korea', 'Seoul', 9989795], ['Bangladesh', 'Dhaka', 8906000], ['Mexico', 'Mexico City', 8851080], ['Iran', 'Tehran', 8846782], ['United Kingdom', 'London', 8630100], ['Peru', 'Lima', 8481415], ['Thailand', 'Bangkok', 8249117], ['Colombia', 'Bogotá', 7613303], ['Vietnam', 'Hanoi', 7587800], ['Hong Kong', 'Hong Kong', 7298600], ['Iraq', 'Baghdad', 7216040], ['Singapore', 'Singapore', 5535000], ['Turkey', 'Ankara', 5150072], ['Chile', 'Santiago', 5084038], ['Saudi Arabia', 'Riyadh', 4878723], ['Germany', 'Berlin', 3520000], ['Syria', 'Damascus', 3500000], ['Algeria', 'Algiers', 3415811], ['Spain', 'Madrid', 3233527], ['North Korea', 'Pyongyang', 3144005], ['Afghanistan', 'Kabul', 3140853], ['Kenya', 'Nairobi', 3138369], ['Greece', 'Athens', 3090508], ['Ethiopia', 'Addis Ababa', 3040740], ['Argentina', 'Buenos Aires', 2891082], ['Italy', 'Rome', 2868104], ['Ukraine', 'Kyiv', 2847200], ['Cameroon', 'Yaoundé', 2765568], ['Taiwan', 'Taipei', 2686516], ['Brazil', 'Brasília', 2648532], ['Jordan', 'Amman', 2600603], ['Angola', 'Luanda', 2453779], ['South Africa', 'Pretoria', 2345908], ['France', 'Paris', 2241346], ['Uzbekistan', 'Tashkent', 2207850], ['Azerbaijan', 'Baku', 2204200], ['Sweden', 'Stockholm', 1856475], ['Cuba', 'Havana', 2135498], ['Cambodia', 'Phnom Penh', 2011725], ['Romania', 'Bucharest', 1942254], ['Venezuela', 'Caracas', 1838939], ['Morocco', 'Rabat', 1789635], ['Austria', 'Vienna', 1749673], ['Sudan', 'Khartoum', 1740661], ['Hungary', 'Budapest', 1729040], ['Poland', 'Warsaw', 1711324], ['Belarus', 'Minsk', 1702061], ['Uganda', 'Kampala', 1659600], ['Ghana', 'Accra', 1640507], ['Madagascar', 'Antananarivo', 0.0704], ['Lebanon', 'Beirut', 1574387], ['Ecuador', 'Quito', 1504991], ['Zimbabwe', 'Harare', 1487028], ['Qatar', 'Doha', 1450000], ['Yemen', "Sana'a", 1431649], ['Guinea', 'Conakry', 1399981], ['Malaysia', 'Kuala Lumpur', 1381830], ['Uruguay', 'Montevideo', 1369797], ['Zambia', 'Lusaka', 1331254], ['Mali', 'Bamako', 1289626], ['Czech Republic', 'Prague', 1241664], ['Haiti', 'Port-au-Prince', 1235227], ['Libya', 'Tripoli', 1184045], ['Kuwait', 'Kuwait City', 1171880], ['Serbia', 'Belgrade', 1154589], ['Dominican Republic', 'Santo Domingo', 1111838], ['Somalia', 'Mogadishu', 1097133], ['Bulgaria', 'Sofia', 1090295], ['Congo', 'Brazzaville', 1088044], ['Belgium', 'Brussels', 1080790], ['Armenia', 'Yerevan', 0.3629], ['Mozambique', 'Maputo', 1076689], ['Sierra Leone', 'Freetown', 1070200], ['Ireland', 'Dublin', 1045769], ['Georgia', 'Tbilisi', 1044993], ['Senegal', 'Dakar', 1030594], ['Guatemala', 'Guatemala City', 1022000], ['Liberia', 'Monrovia', 1010970], ['Burkina Faso', 'Ouagadougou', 1005231], ['Nepal', 'Kathmandu', 1003285], ['Pakistan', 'Islamabad', 955629], ['Nicaragua', 'Managua', 926883], ['Myanmar', 'Naypyidaw', 925000], ['Mongolia', 'Ulan Bator', 907802], ['Malawi', 'Lilongwe', 902388], ['Canada', 'Ottawa', 898150], ['Bolivia', 'La Paz', 877363], ['Kyrgyzstan', 'Bishkek', 843240], ['Kazakhstan', 'Astana', 835153], ['Togo', 'Lomé', 824738], ['Panama', 'Panama City', 813097], ['Netherlands', 'Amsterdam', 810909], ['Croatia', 'Zagreb', 804200], ['Oman', 'Muscat', 797000], ['Niger', 'Niamey', 794814], ['Moldova', 'Chişinău', 794800], ['Israel', 'Jerusalem', 780200], ['Nigeria', 'Abuja', 778567], ['Albania', 'Tirana', 763634], ['Tunisia', 'Tunis', 767629], ['Turkmenistan', 'Ashgabat', 763537], ['Chad', "N'Djamena", 751288], ['Honduras', 'Tegucigalpa', 735982], ['Central African Republic', 'Bangui', 731548], ['Mauritania', 'Nouakchott', 719167], ['Rwanda', 'Kigali', 718414], ['Latvia', 'Riga', 713016], ['Jamaica', 'Kingston', 701063], ['Macedonia', 'Skopje', 668518], ['United States', 'Washington D. C.', 658893], ['Norway', 'Oslo', 645701], ['Finland', 'Helsinki', 596661], ['United Arab Emirates', 'Abu Dhabi', 585097], ['Tajikistan', 'Dushanbe', 582496], ['Portugal', 'Lisbon', 564657], ['Denmark', 'Copenhagen', 562253], ['Lithuania', 'Vilnius', 556723], ['Gabon', 'Libreville', 556425], ['Eritrea', 'Asmara', 1258001], ['El Salvador', 'San Salvador', 521366], ['Paraguay', 'Asunción', 520722], ['Macau', 'Macau', 520400], ['Scotland', 'Edinburgh', 492680], ['Djibouti', 'Djibouti', 475332], ["Côte d'Ivoire", 'Yamoussoukro', 454929], ['Guinea-Bissau', 'Bissau', 452640], ['Estonia', 'Tallinn', 440206], ['Slovakia', 'Bratislava', 424207], ['Puerto Rico', 'San Juan', 421356], ['New Zealand', 'Wellington', 398300], ['Burundi', 'Bujumbura', 384461], ['Bosnia and Herzegovina', 'Sarajevo', 383604], ['South Sudan', 'Juba', 372410], ['Australia', 'Canberra', 354644], ['Costa Rica', 'San José', 328195], ['Papua New Guinea', 'Port Moresby', 0.0409], ['Laos', 'Vientiane', 287579], ['Tanzania', 'Dodoma', 287200], ['Lesotho', 'Maseru', 267652], ['Cyprus', 'Nicosia', 270000], ['Slovenia', 'Ljubljana', 280140], ['Suriname', 'Paramaribo', 254147], ['Namibia', 'Windhoek', 252721], ['Bahamas', 'Nassau', 248948], ['Botswana', 'Gaborone', 225656], ['Benin', 'Porto-Novo', 223552], ['Kosovo', 'Prishtina', 198214], ['Transnistria', 'Tiraspol', 159163], ['Mauritius', 'Port Louis', 147251], ['Montenegro', 'Podgorica', 141854], ['Bahrain', 'Manama', 140616], ['Guyana', 'Georgetown', 134599], ['Cape Verde', 'Praia', 125464], ['Switzerland', 'Berne', 121631], ['Sri Lanka', 'Sri Jayawardenepura Kotte', 118556], ['Iceland', 'Reykjavík', 115000], ['Barbados', 'Bridgetown', 110000], ['Maldives', 'Malé', 103693], ['Bhutan', 'Thimphu', 101259], ['Equatorial Guinea', 'Malabo', 100677], ['New Caledonia', 'Nouméa', 89207], ['Northern Cyprus', 'Nicosia', 84893], ['Fiji', 'Suva', 84410], ['Swaziland', 'Mbabane', 81594], ['Luxembourg', 'Luxembourg', 76420], ['Saint Lucia', 'Castries', 70000], ['Northern Mariana Islands', 'Saipan', 62392], ['Comoros', 'Moroni', 60200], ['Solomon Islands', 'Honiara', 59288], ['East Timor', 'Dili', 59069], ['São Tomé and Príncipe', 'Sao Tome', 56166], ['American Samoa', 'Pago Pago', 52000], ['Trinidad and Tobago', 'Port of Spain', 50479], ['Nagorno-Karabakh Republic', 'Stepanakert', 49986], ['Curaçao', 'Willemstad', 49885], ['Saint Vincent and the Grenadines', 'Kingstown', 40020], ['Samoa', 'Apia', 39813], ['Vanuatu', 'Port Vila', 38000], ['Monaco', 'Monaco', 35986], ['Gambia', 'Banjul', 34828], ['Kiribati', 'Tarawa', 30000], ['Aruba', 'Oranjestad', 29998], ['Seychelles', 'Victoria', 29298], ['Gibraltar', 'Gibraltar', 29286], ['Jersey', 'Saint Helier', 28380], ['Brunei', 'Bandar Seri Begawan', 28135], ['Cayman Islands', 'George Town', 26798], ['Isle of Man', 'Douglas', 26600], ['French Polynesia', 'Papeete', 26200], ['West Bank', 'Ramallah', 25500], ['Marshall Islands', 'Majuro', 25400], ['Andorra', 'Andorra la Vella', 22884], ['Antigua and Barbuda', "St. John's", 22679], ['Tonga', 'Nukuʻalofa', 22400], ['Faroe Islands', 'Tórshavn', 18573], ['Guernsey', 'St. Peter Port', 16701], ['Belize', 'Belmopan', 16451], ['Greenland', 'Nuuk', 15469], ['Dominica', 'Roseau', 14847], ['Saint Kitts and Nevis', 'Basseterre', 13043], ['Åland', 'Mariehamn', 11296], ['United States Virgin Islands', 'Charlotte Amalie', 10817], ['Federated States of Micronesia', 'Palikir', 9900], ['British Virgin Islands', 'Road Town', 9400], ['Grenada', "St. George's", 7500], ['Malta', 'Valletta', 6444], ['Saint Barthélemy', 'Gustavia', 6000], ['Collectivity of Saint Martin', 'Marigot', 5700], ['Saint Pierre and Miquelon', 'Saint-Pierre', 5509], ['Cook Islands', 'Avarua', 5445], ['Liechtenstein', 'Vaduz', 5248], ['San Marino', 'City of San Marino', 4493], ['Tuvalu', 'Funafuti', 4492], ['Turks and Caicos Islands', 'Cockburn Town', 3700], ['Falkland Islands', 'Stanley', 2115], ['Svalbard', 'Longyearbyen', 2075], ['Christmas Island', 'Flying Fish Cove', 1493], ['Sint Maarten', 'Philipsburg', 1338], ['Wallis and Futuna', 'Mata-Utu', 1191], ['Anguilla', 'The Valley', 1169], ['Nauru', 'Yaren', 1100], ['Guam', 'Hagåtña', 1100], ['Montserrat', 'Brades', 391], ['Bermuda', 'Hamilton', 1010], ['Vatican City', 'Vatican City', 826], ['Saint Helena Ascension and Tristan da Cunha', 'Jamestown', 714], ['Niue', 'Alofi', 616], ['Tokelau', 'Atafu', 524], ['Palau', 'Ngerulmud', 391], ['Cocos (Keeling) Islands', 'West Island', 120], ['Pitcairn Islands', 'Adamstown', 56], ['South Georgia and the South Sandwich Islands', 'King Edward Point', 18]]
- Écrire une fonction de comparaison
inf_strict_comp_nbr_hab_puis_pays_alpha
qui compare deux capitales d'abord par leur nombre d'habitants puis compare le nom des pays de ces capitales par ordre alphabétique; - Trier la liste des pays à l'aide de l'ordre défini par la fonction
inf_strict_comp_nbr_hab_puis_pays_alpha
.
- Écrire une fonction de comparaison
- Écrire une fonction de comparaison
inf_strict_comp_inv_nbr_hab_puis_nom_cap_alpha
qui compare deux capitales d'abord dans l'ordre inverse de leur nombre d'habitants puis compare le nom des pays de ces capitales par ordre alphabétique; - Trier la liste des pays à l'aide de l'ordre défini par la fonction
inf_strict_comp_inv_nbr_hab_puis_nom_cap_alpha
.
- Écrire une fonction de comparaison
7 Tableaux
Les éléments d'une liste pouvant être de type quelconque, il est possible de créer des listes de listes en python. C'est ce que nous appelerons des tableaux par la suite. L'exemple suivant montre comment définir un tableau rectangulaire de nombres et comment utiliser les indices avec ce tableau.
a = [[10,11,12],[20,21,22]] print("1ère line du tableau a:", a[0]) print("2nd élément de la 1ère line du tableau a:", a[0][1])
1ère line du tableau a: [10, 11, 12] 2nd élément de la 1ère line du tableau a: 11
Un tableau rectangulaire de nombres comme ci-dessus sera assimilé à
une matrices dans la suite. Cependant il faut faire attention au
fait que, contrairement au cours de Mathématiques U21, les indices
commencent ici à 0
(puisque ce sont des indices de listes).
Dans toute cette section, on pourra utiliser la fonction
affiche_matrice
ci-dessous qui affiche un tableau rectangulaire
de nombres comme une matrice (inutile de comprendre le
fonctionnement de cette fonction) et arrête l'exécution en
affichant un message d'erreur explicite si le tableau n'est pas
rectangulaire ou contient des éléments qui ne sont pas des nombres.
def affiche_matrice(A): """Affiche la matrice représentée par le tableau à deux dimensions A. Args: A: Un tableau à deux dimension d'entiers (c'est à dire une liste de liste d'entiers) Retourne: Un entier entre 0 et 25 Retourne: Rien """ def affiche_ligne(ligne, taille_elmt): fmt_str = "{:^{taille}d}" res = " ".join([fmt_str.format(elmt, taille=taille_elmt) for elmt in ligne]) return "| {} |".format(res) if type(A) is not list: raise Exception("Ce n'est pas une liste!") if len(A) == 0: raise Exception("Le tableau est vide") len_lignes = None taille_elmt_max_str = 0 for nligne, ligne in enumerate(A): if type(ligne) is not list: raise Exception("La ligne {} n'est pas une liste!".format(str(ligne))) if len_lignes is None: len_lignes = len(ligne) elif len(ligne) != len_lignes: fmt_str = "Les lignes ne sont pas toutes de même longueur (longueur {} puis {})!" raise Exception(fmt_str.format(len(ligne), len_lignes)) for ncol,elmt in enumerate(ligne): if type(elmt) not in [int, float]: fmt_str = "L'élement {} (ligne {}, colonne {}) n'est pas un nombre!" raise Exception(fmt_str.format(str(elmt), nligne+1, ncol+1)) taille_elmt_max_str = max(len(str(elmt)), taille_elmt_max_str) print("\n".join([affiche_ligne(ligne, taille_elmt=taille_elmt_max_str+2) for ligne in A]))
Copier l'affectation suivante dans un nouveau script
tableau_a_deux_dim = [[2, 5, 4, 3, 1, 5, 1, 4, 3, 0, 2, 7, 2, 1, 6, 3, 3, 4, 0, 6], [4, 6, 7, 3, 2, 6, 7, 3, 0, 3, 6, 6, 6, 7, 3, 6, 7, 1, 4, 5], [3, 3, 4, 1, 2, 2, 3, 7, 6, 0, 0, 4, 2, 0, 5, 4, 3, 5, 1, 0], [4, 3, 4, 5, 5, 3, 5, 6, 0, 0, 4, 3, 6, 5, 7, 2, 6, 4, 4, 1], [0, 1, 3, 7, 2, 5, 1, 7, 1, 4, 3, 5, 0, 6, 3, 1, 3, 3, 3, 5], [0, 4, 6, 6, 7, 7, 2, 3, 0, 1, 3, 4, 4, 2, 0, 2, 6, 2, 4, 6], [1, 6, 4, 7, 6, 1, 6, 4, 2, 4, 5, 4, 2, 7, 1, 6, 6, 0, 6, 6], [2, 5, 5, 1, 1, 3, 1, 7, 5, 7, 1, 4, 3, 4, 4, 2, 0, 3, 2, 6], [2, 5, 0, 7, 6, 3, 2, 0, 3, 6, 3, 6, 6, 6, 4, 3, 2, 7, 7, 7], [5, 7, 5, 6, 6, 4, 3, 5, 6, 3, 2, 3, 2, 3, 4, 7, 1, 0, 5, 5], [5, 5, 4, 3, 4, 2, 1, 6, 1, 5, 4, 7, 3, 3, 0, 1, 5, 7, 1, 6], [7, 1, 1, 4, 6, 0, 3, 6, 1, 4, 4, 5, 7, 1, 4, 6, 4, 4, 0, 1], [1, 5, 5, 3, 1, 4, 3, 4, 5, 7, 1, 6, 2, 1, 1, 6, 6, 6, 5, 0], [1, 4, 3, 2, 6, 6, 7, 5, 5, 1, 2, 0, 5, 5, 5, 6, 7, 3, 0, 0], [3, 6, 0, 1, 2, 2, 1, 4, 0, 5, 6, 7, 1, 7, 6, 0, 7, 0, 6, 4], [7, 5, 6, 3, 1, 3, 0, 1, 5, 0, 7, 6, 7, 1, 7, 7, 0, 6, 6, 0], [1, 5, 4, 7, 6, 6, 7, 1, 0, 3, 5, 5, 1, 6, 0, 2, 1, 1, 4, 6], [7, 5, 6, 1, 3, 4, 6, 6, 1, 1, 4, 7, 6, 1, 0, 4, 3, 5, 0, 1], [0, 2, 7, 6, 6, 4, 0, 6, 5, 5, 6, 0, 0, 0, 1, 6, 3, 4, 0, 7], [1, 1, 0, 5, 4, 3, 0, 1, 5, 6, 2, 0, 2, 7, 1, 4, 6, 2, 1, 4]]
- Expliquer les valeurs retournées par les appels
tableau_a_deux_dim[0]
,tableau_a_deux_dim[1]
,tableau_a_deux_dim[0][1]
ettableau_a_deux_dim[1][0]
.
- Expliquer les valeurs retournées par les appels
Modifier la définition de la fonction
matrice_de_un
ci-dessous pour que lorsqu'elle est appelée avec les argumentsn
etp
elle retourne un tableau àn
lignes etp
colonnes ne contenant que des1
. On vérifiera que l'appelmatrice_de_un(3, 2)
retourne[[1,1],[1,1],[1,1]]
(utiliser la fonctionaffiche_matrice
pour mieux visualiser la matrice correspondante).Rappel python: L'expression
[None]*3
renvoie[None, None, None]
et[1]*4
renvoie[1, 1, 1, 1]
…def matrice_de_un(n, p): matrice = [None]*p for num_ligne in range(p): matrice[num_ligne] = [3]*p return matrice
- Écrire une fonction
matrice_coeff_num_ligne
qui accepte deux arguments que l'on appelleran
etp
et qui retourne un tableau àn
lignes etp
colonnes où les coefficient de la ième ligne sont égaux ài
. On vérifiera que l'appelmatrice_coeff_num_ligne(2, 3)
retourne[[1, 1, 1], [2, 2, 2]]
, et que l'appelmatrice_coeff_num_ligne(3, 2)
retourne[[1, 1], [2, 2], [3, 3]]
(utiliser la fonctionaffiche_matrice
pour mieux visualiser les matrices correspondantes). - Écrire une fonction
matrice_coeff_num_col
qui accepte deux arguments que l'on appelleran
etp
et qui retourne un tableau àn
lignes etp
colonnes où les coefficient de la ième colonne sont égaux ài
. On vérifiera que l'appelmatrice_coeff_num_col(2, 3)
retourne[[1, 2, 3], [1, 2, 3]]
et que l'appelmatrice_coeff_num_col(3, 2)
retourne[[1, 2], [1, 2], [1, 2]]
(utiliser la fonctionaffiche_matrice
pour mieux visualiser les matrices correspondantes). - Écrire une fonction
matrice_identite
qui accepte un unique argument que l'on nommeran
et retourne un tableau àn
lignes etn
colonnes représentant la matrice identité de taillen
. On vérifiera que l'appelmatrice_identite(3)
retourne[[1,0,0],[0,1,0],[0,0,1]]
. Dans cet exercice on considère un graphe G à 20 sommets nommés dans l'ordre alphabétique de
"A"
à"T"
et dont la matrice d'adjacence est donnée par le tableaumatrice_adj
ci-dessousmatrice_adj = [[0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0], [0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1], [0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1], [0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0], [0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0], [1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1], [1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1], [1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0], [0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0], [0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0], [0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1], [0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0], [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1], [1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1], [0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1]]
Pour obtenir l'indexe d'un sommet à partir de
0
étant donné son nom, on pourra utiliser la fonction suivante (déjà donnée dans un TP précédent):def indice_lettre(l): """Retourne l'indice entre 0 et 25 de son argument si ce dernier est bien un caractère majuscule non accentué (en python un caractère est une chaîne de caractères de longueur 1), sinon arrête l'exécution en provoquant une erreur. Args: l: chaîne de carcatère Retourne: Un entier entre 0 et 25 """ if not type(l) is str: raise Exception("L'argument n'est pas une chaîne de caractère") if len(l) != 1: raise Exception("La chaîne de caractère n'est pas un caractère seul") indice_ascii = ord(l) if indice_ascii < ord("A") or indice_ascii > ord("Z"): raise Exception("Le caractère n'est pas une lettre majuscule non accentuée") return indice_ascii - ord("A")
- Vérifier que l'appel
indice_lettre("T")
retourne bien19
. Compléter la définition de la fonction
nbr_succ_dans_G
ci-dessous afin- qu'elle accepte un unique argument que l'on supposera êtres le
nom d'un sommet de notre graphe (donc
"A"
,"B"
,"C"
,"D"
,"E"
,"F"
,"G"
,"H"
,"I"
,"J"
,"K"
,"L"
,"M"
,"N"
,"O"
,"P"
,"Q"
,"R"
,"S"
ou"T"
) - qu'elle retourne le nombre de successeurs de ce sommet dans
le graphe de matrice
matrice_adj
def nbr_succ_dans_G(sommet): indice_sommet = indice_lettre(sommet) nbr_succ = 0 for elmt in matrice_adj[indice_sommet]: if elmt == ...: nbr_succ = ... return ...
On vérifiera que l'appel
nbr_succ_dans_G("A")
retourne bien9
et que l'appelnbr_succ_dans_G("B")
retourne bien10
.- qu'elle accepte un unique argument que l'on supposera êtres le
nom d'un sommet de notre graphe (donc
Compléter a définition de la fonction
nbr_pred_dans_G
ci-dessous afin- qu'elle accepte un unique argument que l'on supposera êtres le
nom d'un sommet de notre graphe (donc
"A"
,"B"
,"C"
,"D"
,"E"
,"F"
,"G"
,"H"
,"I"
,"J"
,"K"
,"L"
,"M"
,"N"
,"O"
,"P"
,"Q"
,"R"
,"S"
ou"T"
) - qu'elle retourne le nombre de predecesseurs de ce sommet
dans le graphe de matrice
matrice_adj
def nbr_pred_dans_G(sommet): indice_sommet = indice_lettre(sommet) nbr_pred = 0 for line in matrice_adj: if line[...] == ...: nbr_pred = ... return ...
On vérifiera que l'appel
nbr_pred_dans_G("A")
retourne bien6
et que l'appelnbr_pred_dans_G("B")
retourne bien7
.- qu'elle accepte un unique argument que l'on supposera êtres le
nom d'un sommet de notre graphe (donc
- Définir une fonction
est_un_arc
qui accepte deux arguments que l'on supposera être des noms de sommets de G et qui retourneTrue
s'l existe un arc dans G allant du premier au deuxième de ces sommets etFalse
sinon. On vérifiera que l'appelest_un_arc("A", "C")
renvoieTrue
etest_un_arc("C", "A")
renvoieFalse
. - Définir une fonction
est_un_chemin
qui accepte un unique argument que l'on supposera être une liste de noms de sommets de G et qui retourneTrue
si cette liste est un chemin dans le graphe G etFalse
sinon. On vérifiera que l'appelest_un_chemin(["A", "B", "D", "E"])
renvoieTrue
et que l'appelest_un_chemin(["A", "B", "D", "G"])
renvoieFalse
.
- Vérifier que l'appel
Compléter la fonction
produit_matrice
ci-dessous pour- qu'elle accepte deux arguments que l'on nommera
A
etB
, arguments que l'on supposera être des tableaux représentant des matrices multipliables; - et qui retourne le produit matriciel de
A
etB
dans cet ordre.
On pourra s'aider du schéma en-dessous pour se repérer dans les indices de chaque tableau
def produit_matrice(A, B): n = len(A) p = len(B[0]) produit_A_et_B = [None]*n for i in range(n): produit_A_et_B[i] = [None]*p for i in range(n): for j in range(p): produit_A_et_B[i][j] = ... for k in range(len(A[i])): produit_A_et_B[i][j] = produit_A_et_B[i][j] + A[i][...]*B[...][j] return ...
Figure 3 : Schéma de la multiplication matricielle (les indices commençant à 0) - qu'elle accepte deux arguments que l'on nommera
On ajoutera les lignes suivantes en fin de script et on vérifiera que l'affichage correspond à ce que l'on attend de la multiplication matricielle…
A = matrice_de_un(2, 3) B = matrice_de_un(3, 2) print("A fois B:") A_fois_B = produit_matrice(A, B) affiche_matrice(A_fois_B) print("\nB fois A:") B_fois_A = produit_matrice(B, A) affiche_matrice(B_fois_A)
8 Fonctions 2
8.1 Variables 2
8.1.1 Espaces de nom
Jusqu'à présent, nous avons prétendu qu'à chaque identifiant correspondait une unique variable et que ces associations n'évoluaient pas pendant l'exécution d'un programme. Mais en fait:
- les associations entre identifiants et variables sont écrites dans des espaces de noms;
- à chaque instant il peut exister plusieurs espace de noms. Il
faut distinguer
- l'espace de noms global qui est créé en début de programme et détruit à la fin de celui-ci. Les variables qui y résident sont dites globales;
- les espaces de noms locaux qui forment une pile, au sens où ils "s'entassent les uns sur les autres". Ils sont créés puis empilés à chaque appel de fonction et dépilés puis détruits à chaque sorti de fonction. A leur création ils contiennent les associations entre les arguments de la fonction dans laquelle on rentre et les valeurs correpsondantes fournies lors de l'appel de cette fonction. L'espace de nom le plus haut (donc le dernier empilé) masque temporairement (jusqu'à ce qu'il soit dépilé) ceux d'en-dessous si bien qu'à chaque instant au plus un espace de nom local est actif. Les variables qui résident dans un espace de nom local sont dites locales à cette fonction (mais on devrait dire locales à un appel de cette fonction);
- à un instant donné, un identifiant peut se trouver dans plusieurs espaces de noms locaux et aussi dans l'espace de nom global.
8.1.2 Accès aux variables en lecture
lorsque l'on cherche à accéder en lecture à une variable à partir de son identifiant
- on cherche d'abord cette variable dans l'espace de nom local
actif (celui qui est le plus haut sur la pile, donc celui qui
correpond à l'appel de fonction en cours) si la pile n'est pas
vide (autrement dit si on est bien dans une fonction) et si la
variable n'a pas été déclarée avec le mot clef
global
. Si l'on trouve une variable avec cet identifiant dans cet espace de nom alors on utilise cette variable; - sinon (c'est à dire si l'on est en dehors de toute fonction ou si
la variable a été déclarée avec le mot clef
global
) on cherche dans l'espace de nom global et si l'on y trouve une variable avec cet identifiant alors on utilise cette variable; - si l'on n'a alors toujours pas trouvé de variable avec cet
identifiant alors une erreur
NameError
est levée et un message est affiché dans la console.
Considérons le schéma ci-dessous représentant des espaces de nom à un instant donné de l'exécution d'un programme.
- si l'on exécute l'instruction
print(mavar1)
alors l'interpréteur recherche d'abord une variable de nommavar1
dans l'espace de nom local actif, soit dans le dernier espace de nom empilé (celui du haut), et il en trouve une. Cette instruction affiche donc"BTS SIO"
. - si l'on exécute l'instruction
print(mavar1)
et si la variablemavar1
est déclarée avec le mot-clefglobal
dans la fonction courante alors l'interpréteur recherche une variable de nommavar1
dans l'espace de nom global et il en trouve une. Cette instruction affiche donc"123.4"
. - si l'on exécute l'instruction
print(mavar2)
alors l'interpréteur recherche d'abord une variable de nommavar2
dans l'espace de nom local actif, soit dans le dernier espace de nom empilé (celui du haut). Il n'en trouve pas donc il recherche maintenant dans l'espace de nom global où il en trouve une. Cette instruction affiche donc[1,2,0,"a"]
. - si l'on exécute l'instruction
print(mavar3)
alors l'interpréteur recherche d'abord une variable de nommavar3
dans l'espace de nom local actif, soit dans le dernier espace de nom empilé (celui du haut). Il n'en trouve pas donc il recherche maintenant dans l'espace de nom global où il en trouve une. Cette instruction affiche donc[[1,2],[3,4]]
. - si l'on exécute l'instruction
print(mavar4)
alors l'interpréteur recherche d'abord une variable de nommavar4
dans l'espace de nom local actif, soit dans le dernier espace de nom empilé (celui du haut). Il n'en trouve pas donc il recherche maintenant dans l'espace de nom global où il n'en trouve pas non plus. Une erreurNameError
est alors levée (ce qui termine l'exécution du programme) et le message d'erreurNameError: name 'marvar4' is not defined
est affiché dans la console.
8.1.3 Accès aux variables en écriture
lorsque l'on cherche à accéder en écriture à une variable à partir de son identifiant, alors
- si on est en dehors de toute fonction ou si la variable a été déclarée avec le mot-clef global dans le corps de la fonction courante alors on utilise l'espace de nom global: si une variable avec cet identifiant y existe alors on l'utilise sinon on la crée avant de l'utiliser;
- sinon on utilise l'espace de nom local actif (celui qui est en haut de la pile et qui correspond à l'appel de fonction courant): si une variable avec cet identifiant y existe alors on l'utilise sinon on la crée.
Considérons le schéma ci-dessous représentant des espaces de nom à un instant donné de l'exécution d'un programme.
si l'on exécute l'instruction
mavar1 = 12
alors l'interpréteur recherche une variable d'identifiantmavar1
dans l'espace de nom local actif (celui du haut de la pile) et il en trouve une. On se retrouve alors dans la situation suivante:
si l'on exécute l'instruction
mavar2 = 12
et simavar2
n'est pas déclarée avec le mot-clefglobal
dans la fonction courante alors l'interpréteur recherche une variable d'identifiantmavar1
dans l'espace de nom local actif (celui du haut de la pile) et il n'en trouve pas. Il y en crée alors une et on se retrouve alors dans la situation suivante:
si l'on exécute l'instruction
mavar2 = 12
et simavar2
est déclarée avec le mot-clefglobal
dans la fonction courante alors l'interpréteur recherche une variable d'identifiantmavar2
dans l'espace de nom global et en trouve une. On se retrouve alors dans la situation suivante:
si l'on exécute l'instruction
mavar3 = 12
et simavar3
est déclarée avec le mot-clefglobal
dans la fonction courante alors l'interpréteur recherche une variable d'identifiantmavar3
dans l'espace de nom global et n'en trouve pas, et il y en crée alors une. On se retrouve alors dans la situation suivante:
8.1.4 Exemples
Dans l'exemple suivant, l'identifiant a
est utilisé par deux
variables: l'une est globale et l'autre est locale à la fonction
affiche_variable_locale_a
. Dans la fonction
affiche_variable_locale_a
, on observe que c'est bien la variable
locale à cette fonction qui est utilisée alors que hors de toute
fonction c'est bien la variable globale qui est utilisée.
a = 9 def affichevariablelocalea(): a = 20 print("a:", a) affichevariablelocalea() print("a:", a)
a: 20 a: 9
Ligne | Instruction | a (1-6;0) | a (2-4;1) |
---|---|---|---|
1 | 'a = 9' | ||
2 | 'def affichevariablelocalea():' | 9 | |
5 | 'affichevariablelocalea()' | 9 | |
2 | 'def affichevariablelocalea():' | 9 | |
3 | ' a = 20' | 9 | |
4 | ' print("a:", a)' | 9 | 20 |
6 | 'print("a:", a)' | 9 |
Dans l'exemple suivant, l'identifiant b
est utilisé par trois
variables: l'une est globale, une autre est locale à la fonction
ma_premiere_fonction
et l'autre est locale à la fonction
ma_seconde_fonction
.
b = 8 def ma_premiere_fonction(): b = 5 print("Dans ma_premiere_fonction, b =", b) def ma_seconde_fonction(): b = 3 print("Dans ma_seconde_fonction, b =", b) ma_premiere_fonction() ma_seconde_fonction() print("Hors de toute fonction, b = ", b)
Dans ma_premiere_fonction, b = 5 Dans ma_seconde_fonction, b = 3 Hors de toute fonction, b = 8
Ligne | Instruction | b (1-10;0) | b (2-4;1) | b (5-7;1) |
---|---|---|---|---|
1 | 'b = 8' | |||
2 | 'def ma_premiere_fonction():' | 8 | ||
5 | 'def ma_seconde_fonction():' | 8 | ||
8 | 'ma_premiere_fonction()' | 8 | ||
2 | 'def ma_premiere_fonction():' | 8 | ||
3 | ' b = 5' | 8 | ||
4 | ' print("Dans ma_premiere_fonction, b =", b)' | 8 | 5 | |
9 | 'ma_seconde_fonction()' | 8 | ||
5 | 'def ma_seconde_fonction():' | 8 | ||
6 | ' b = 3' | 8 | ||
7 | ' print("Dans ma_seconde_fonction, b =", b)' | 8 | 3 | |
10 | 'print("Hors de toute fonction, b = ", b)' | 8 |
Dans l'exemple suivant, l'identifiant b
n'est utilisé que par
une variable qui est globale.
b = 8 def ma_fonction(): global b b = 5 print("Dans ma_premiere_fonction, b =", b) ma_fonction() print("Hors de toute fonction, b = ", b)
Dans ma_premiere_fonction, b = 5 Hors de toute fonction, b = 5
Ligne | Instruction | b (1-7;0) |
---|---|---|
1 | 'b = 8' | |
2 | 'def ma_fonction():' | 8 |
6 | 'ma_fonction()' | 8 |
2 | 'def ma_fonction():' | 8 |
4 | ' b = 5' | 8 |
5 | ' print("Dans ma_premiere_fonction, b =", b)' | 5 |
7 | 'print("Hors de toute fonction, b = ", b)' | 5 |
8.1.5 TP
Copier-coller le script suivant dans un fichier
foo = 1 bar = 2 def print_global_foo_and_global_bar(): global foo, bar print("foo:", foo,"; bar:", bar) def assign_to_global_foo_and_global_bar(fooval, barval): global foo, var foo = fooval bar = barval def assign_to_global_foo_and_local_bar(fooval, barval): global foo foo = fooval bar = barval def assign_to_local_foo_and_global_bar(fooval, barval): global bar foo = fooval bar = barval print_global_foo_and_global_bar() # Explications: # assign_to_global_foo_and_global_bar(3, 4) print_global_foo_and_global_bar() # Explications: # assign_to_global_foo_and_local_bar(5, 6) print_global_foo_and_global_bar() # Explications: # assign_to_local_foo_and_global_bar(7, 8) print_global_foo_and_global_bar() # Explications: #
- Expliquer les valeurs affichées par chaque appel à la
fonction
print_global_foo_and_global_bar
dans le commentaire prévu en-dessous de ceux-ci. Copier-coller à nouveau le script ci-dessus dans un nouveau fichier puis modifier un seul des arguments parmi les appels aux fonctions
assign_to_global_foo_and_global_bar
,assign_to_global_foo_and_local_bar
, etassign_to_local_foo_and_global_bar
afin que le nouveau script affichefoo: 1 ; bar: 2 foo: 3 ; bar: 2 foo: 11 ; bar: 2 foo: 11 ; bar: 8
- Expliquer les valeurs affichées par chaque appel à la
fonction
Copier-coller le script suivant dans un nouveau fichier
foo = 1 bar = 2 def affecter_3_variable_globale_foo(): global foo foo = 3 def affecter_3_variable_locale_foo(): foo = 3 def affecter_5_variable_globale_bar(): global bar bar = 5 def affecter_5_variable_locale_bar(): bar = 5 print("foo:", foo, "; bar:", bar) glo_ou_loc = None while glo_ou_loc != "g" and glo_ou_loc != "l": glo_ou_loc = input("Affecter 3 à la variable foo globale (g) ou locale (l)? ") if glo_ou_loc != "g" and glo_ou_loc != "l": print("Mauvaise réponse: ni 'g', ni 'l'. Try again.") if glo_ou_loc == "g": affecter_3_variable_globale_foo() else: affecter_3_variable_locale_foo() print("foo:", foo, "; bar:", bar) glo_ou_loc = None while glo_ou_loc != "g" and glo_ou_loc != "l": glo_ou_loc = input("Affecter 3 à la variable foo globale (g) ou locale (l)? ") if glo_ou_loc != "g" and glo_ou_loc != "l": print("Mauvaise réponse: ni 'g', ni 'l'. Try again.") if glo_ou_loc == "g": affecter_3_variable_globale_foo() else: affecter_3_variable_locale_foo() print("foo:", foo, "; bar:", bar) glo_ou_loc = None while glo_ou_loc != "g" and glo_ou_loc != "l": glo_ou_loc = input("Affecter 5 à la variable bar globale (g) ou locale (l)? ") if glo_ou_loc != "g" and glo_ou_loc != "l": print("Mauvaise réponse: ni 'g', ni 'l'. Try again.") if glo_ou_loc == "g": affecter_3_variable_globale_foo() else: affecter_3_variable_locale_foo() print("foo:", foo, "; bar:", bar) glo_ou_loc = None while glo_ou_loc != "g" and glo_ou_loc != "l": glo_ou_loc = input("Affecter 5 à la variable bar globale (g) ou locale (l)? ") if glo_ou_loc != "g" and glo_ou_loc != "l": print("Mauvaise réponse: ni 'g', ni 'l'. Try again.") if glo_ou_loc == "g": affecter_5_variable_globale_bar() else: affecter_5_variable_locale_bar()
Ce programme demande trois fois à l'utilisateur d'entrer une chaîne de caractères qui doit être soit
"g"
, soit"l"
. Si l'utilisateur entre"g"
alors une certaine valeur est affectée à une variable globale sinon s'il rentre"l"
alors cette valeur est affectée à une variable locale de même identifiant.Vérifier que si l'utilisateur entre dans l'ordre
"g"
,"l"
,"g"
,"l"
alors ce programme affichefoo: 1 ; bar: 2 foo: 3 ; bar: 2 foo: 3 ; bar: 2 foo: 3 ; bar: 5
Expliquer cette affichage.
Dire ce que doit entrer l'utilisateur pour que cet algorithme affiche dans l'ordre
foo: 1 ; bar: 2 foo: 1 ; bar: 2 foo: 3 ; bar: 2 foo: 3 ; bar: 2
Recopier le script ci-dessous dans un nouveau fichier
nbr = 0 def nombre_appels_essai1(): global nbr nbr = nbr + 1 print("Fonction 'nombre_appels_essai2' appelée", nbr, "fois") def nombre_appels_essai2(): nbr = nbr + 1 print("Fonction 'nombre_appels_essai1' appelée", nbr, "fois") nombre_appels_essai1() nombre_appels_essai1() nombre_appels_essai1() nombre_appels_essai2() nombre_appels_essai2()
- Vérifier que cet script provoque une erreur
UnboundLocalError
. Cette erreur est-elle provoquée par la fonctionnombre_appels_essai1
ou par la fonctionnombre_appels_essai2
? - Expliquer cette erreur.
- Vérifier que cet script provoque une erreur
Copier-coller le script suivant dans un nouveau fichier
nbr_minutes = 100 def ajoute_une_minute(): # À compléter return def ajoute_dix_minutes(): # À compléter return def afficher_nbr_minutes(): # À compléter return afficher_nbr_minutes() # doit afficher 100 ajoute_une_minute() afficher_nbr_minutes() # doit afficher 101 ajoute_une_minute() afficher_nbr_minutes() # doit afficher 102 ajoute_dix_minute() afficher_nbr_minutes() # doit afficher 112 ajoute_dix_minute() afficher_nbr_minutes() # doit afficher 122
Ce script compte un nombre de minutes dans une variable globale nommée
nbr_minutes
en commençant à100
. Chaque appel à la fonctionajoute_une_minute
doit ajouter une minute à cette variable, chaque appel à la fonctionajoute_dix_minutes
doit en ajouter10
, et la fonctionafficher_nbr_minutes
doit afficher cette variable.- Compléter les définitions des trois fonctions
ajoute_une_minute
,ajoute_dix_minutes
etafficher_nbr_minutes
. - Vérifier que les valeurs alors affichées par ce script sont cohérentes (voir les commentaires dans le fichier).
- Compléter les définitions des trois fonctions
- Si vous avez fini, inscrivez-vous sur le site https://checkio.org/ en cliquant sur Python en haut à gauche (dans la partie "CheckiO" qui est dans la ciel) puis essayez le premier challenge!
8.2 Récursivité
On dit qu'une fonction est récursive si elle s'appelle elle-même.
Par exemple la fonction somme_des_n_premiers_entiers
définie
ci-dessous est une fonction récursive.
n = 7 def somme_des_n_premiers_entiers(n): print("somme_des_n_premiers_entiers", n) if n == 1: return 0 tmp = somme_des_n_premiers_entiers(n-1) return tmp + n somme_des_n_premiers_entiers(3)
somme_des_n_premiers_entiers 3 somme_des_n_premiers_entiers 2 somme_des_n_premiers_entiers 1
Ligne | Instruction | n (1-8;0) | n (2-7;1) | n (2-7;2) | n (2-7;3) | tmp (2-7;1) | tmp (2-7;2) |
---|---|---|---|---|---|---|---|
1 | 'n = 7' | ||||||
2 | 'def somme_des_n_premiers_entiers(n):' | 7 | |||||
8 | 'somme_des_n_premiers_entiers(3)' | 7 | |||||
2 | 'def somme_des_n_premiers_entiers(n):' | 7 | 3 | ||||
3 | ' print("somme_des_n_premiers_entiers", n)' | 7 | 3 | ||||
4 | ' if n == 1:' | 7 | 3 | ||||
6 | ' tmp = somme_des_n_premiers_entiers(n-1)' | 7 | 3 | ||||
2 | 'def somme_des_n_premiers_entiers(n):' | 7 | 3 | 2 | |||
3 | ' print("somme_des_n_premiers_entiers", n)' | 7 | 3 | 2 | |||
4 | ' if n == 1:' | 7 | 3 | 2 | |||
6 | ' tmp = somme_des_n_premiers_entiers(n-1)' | 7 | 3 | 2 | |||
2 | 'def somme_des_n_premiers_entiers(n):' | 7 | 3 | 2 | 1 | ||
3 | ' print("somme_des_n_premiers_entiers", n)' | 7 | 3 | 2 | 1 | ||
4 | ' if n == 1:' | 7 | 3 | 2 | 1 | ||
5 | ' return 0' | 7 | 3 | 2 | 1 | ||
7 | ' return tmp + n' | 7 | 3 | 2 | 0 | ||
7 | ' return tmp + n' | 7 | 3 | 2 |
Dans toute cette partie on utilisera fréquemment le symbol somme \(\sum\) et le symbol produit \(\prod\). Par exemple on a \(\sum_{i=1}^{3}i=1+2+3=6\), \(\prod_{i=1}^{3}i=1\times2\times3=6\), \(\sum_{i=2}^{3}i=2+3=5\), \(\sum_{i=3}^{5}i=3+4+5=12\), \(\sum_{i=3}^{3}i=3\), \(\sum_{i=4}^{4}i=4=4\).
Copier-coller la définition de la fonction
produit_de_1_a_n
ci-dessous puis la compléter afin que l'appelproduit_de_1_a_n(n)
retourne \(\prod_{i=1}^{n}i\) (c'est à dire le produit des entiers de1
àn
). On vérifiera que les appelsproduit_de_1_a_n(3)
etproduit_de_1_a_n(5)
retournent des valeurs cohérentes.def produit_de_1_a_n(n): if n == 1: return ... tmp = produit_de_1_a_n(n-1) return tmp * ...
Copier-coller la définition de la fonction
produit_de_3_a_n
ci-dessous puis la compléter afin que l'appelproduit_de_3_a_n(n)
retourne \(\prod_{i=3}^{n}i\) (c'est à dire le produit des entiers de3
àn
). On vérifiera que les appelsproduit_de_3_a_n(3)
etproduit_de_3_a_n(5)
retournent des valeurs cohérentes.def produit_de_3_a_n(n): if n == ...: return ... tmp = produit_de_3_a_n(n-1) return tmp * ...
Copier-coller la définition de la fonction
somme_de_0_a_n
ci-dessous puis la compléter afin que l'appelsomme_de_0_a_n(n)
retourne \(\sum_{i=0}^{n}i\) (c'est à dire la somme des entiers de0
àn
). On vérifiera que les appelssomme_de_0_a_n(3)
etsomme_de_0_a_n(5)
retournent des valeurs cohérentes.def somme_de_0_a_n(n): if n == ...: return ... tmp = somme_de_0_a_n(n-1) return tmp + ...
Copier-coller la définition de la fonction
somme_de_1_a_n
ci-dessous puis la compléter afin que l'appelsomme_de_1_a_n(n)
retourne \(\sum_{i=1}^{n}i\) (c'est à dire la somme des entiers de1
àn
). On vérifiera que les appelssomme_de_1_a_n(3)
etsomme_de_1_a_n(5)
retournent des valeurs cohérentes.def somme_de_1_a_n(n): if n == ...: return ... tmp = somme_de_1_a_n(n-1) return tmp + ...
Copier-coller la définition de la fonction
somme_des_carres_de_0_a_ncarre
ci-dessous puis la compléter afin que l'appelsomme_des_carres_de_0_a_ncarre(n)
retourne \(\sum_{i=0}^{n}i^2=0^{2}+1^{2}+2^{2}+\cdots+n^{2}\). On vérifiera que les appelssomme_des_carres_de_0_a_ncarre(3)
etsomme_des_carres_de_0_a_ncarre(5)
retournent des valeurs cohérentes.def somme_des_carres_de_0_a_ncarre(n): if n == ...: return ... tmp = somme_des_carres_de_0_a_ncarre(n-1) return tmp * ...
On considère la fonction
fonction_mystere_recursive
récurrente ci-dessous:def fonction_mystere_recursive(a, b): if b==0: return 0 else: return a + fonction_mystere_recursive(a, b-1)
- afficher les valeurs renvoyées par les appels
fonction_mystere_recursive(3, 0)
,fonction_mystere_recursive(3, 1)
,fonction_mystere_recursive(3, 2)
,fonction_mystere_recursive(3, 3)
etfonction_mystere_recursive(3, 10)
. - Plus généralement que renvoit l'appel
fonction_mystere_recursive(a, b)
, sia
etb
sont deux entiers eta
est positif? - Vérifier que l'appel
fonction_mystere_recursive(3, -2)
échoue avec une erreur de typeRecursionError
. Expliquer pourquoi.
- afficher les valeurs renvoyées par les appels
- Écrire une fonction récursive
nbr_elmt_egaux_même_ind
qui accepte deux arguments que l'on suposera être de type liste et qui retourne le nombre d'éléments égaux et aux même indices entre ces deux listes. Ainsinbr_elmt_egaux_même_ind([1,2], [2,1])
doit retourner0
,nbr_elmt_egaux_même_ind([1,2], [1,2])
doit retourner2
etnbr_elmt_egaux_même_ind([1,2,3], [1,4,2])
doit retourner1
. On rappelle que sil
est une liste non vide alorsl[1:]
est la liste constituée des mêmes éléments sauf du premier. - Écrire une fonction récursive
nbr_elmt_en_commun
qui accepte deux arguments que l'on suposera être de type liste et qui retourne le nombre d'éléments commun aux deux listes. Ainsinbr_elmt_en_commun([1,2], [2,1])
doit retourner2
,nbr_elmt_en_commun([1,2], [1,2])
doit retourner2
etnbr_elmt_en_commun([1,2,3], [1,4,2])
doit retourner2
. On rappelle que sil
est une liste non vide alorsl[1:]
est la liste constituée des mêmes éléments sauf du dernier.
- Écrire une fonction récursive
À cette question, on considère les opérations suivantes sur une chaîne de caractère
- la suppression d'une lettre;
- l'insertion d'une lettre;
- le substitution d'une lettre par une autre.
On appelle distance de levenshteim entre deux chaînes le nombre minimal de suppressions, d'insertions ou de substitutions nécessaires en partant de ces deux chaînes pour arriver à une chaîne commune. Le but de cet exercice est d'écrire une fonction récursive
dist_leven
qui accepte deux arguments de type chaîne de caractères et qui retourne la distance de levenshteim entre ces deux chaînes. Ainsi- l'appel
dist_leven("MA", "MAM")
doit renvoyer1
(soit on supprime un caractère de la seconde chaîne de caractères soit on ajoute un caractère à la première chaîne ce qui ne fait dans les deux cas qu'une opération); - l'appel
dist_leven("MAP", "MAM")
doit renvoyer1
(il suffit de substituer la dernière lettre d'une des chaîne en la dernière lettre de l'autre); - l'appel
dist_leven("MAPM", "MAM")
doit renvoyer1
(il suffit de supprimer le"P"
de la première chaîne de caractères).
Les deux premières questions ne nécessitent pas d'écriture de code
- Justifier que l'appel
dist_leven("", "M")
doit renvoyer1
;dist_leven("", "SIO")
doit renvoyer3
;dist_leven("Z", "")
doit renvoyer1
;dist_leven("CAR", "")
doit renvoyer3
.
- Plus généralement, si
c
est une chaîne de caractères, que doit renvoyer l'appeldist_leven("", "c")
?dist_leven("c", "")
?
Rappelons que si
c1
est une chaîne de caractères, alorsc1[:-1]
est la chaîne constituée des même caractères à l'exception du dernier. Ainsi si vous exécuter les instructionc1="SIO"
puisprint(c1[:-1])
dans la console alors vous devriez voir affiché"SI"
. Dans la suite on aura toujoursc1_moins_derniere_lettre=c1[:-1]
;c2_moins_derniere_lettre=c2[:-1]
.
On admettra que pour calculer
dist_leven(c1, c2)
on peut procéder ainsi:- Si
c1
ouc2
est la chaîne vide, renvoyer directement la distance de levenshteim en utilisant la question précédente. - si les deux chaînes ont même dernier caractère (soit si
c1[-1]==c2[-1]
) alors la distance de levenshteim entrec1
etc2
est égale à celle entrec1_moins_derniere_lettre
etc2_moins_derniere_lettre
; - sinon
- on calcule
dist_supr_dern_let_c1 = dist_leven(c1_moins_derniere_lettre, c2)+1
; - on calcule
dist_supr_dern_let_c2 = dist_leven(c1, c2_moins_derniere_lettre)+1
; - on calcule
dist_subst_dern_let = dist_leven(c1_moins_derniere_lettre, c2_moins_derniere_lettre)+1
; - on renvoie le plus petit de ces trois nombres.
- on calcule
Copier-coller la définition de la fonction
dist_leven
ci-dessous puis la la compléter. On vérifiera que les appelsdist_leven("", "SIO")
,dist_leven("SIO", "SIO")
,dist_leven("SIO", "BIO")
,dist_leven("SIO", "PSIO")
etdist_leven("SIO", "SZI")
revoient des valeurs correctes et que l'appeldist_leven("CHIENS", "NICHE")
renvoie5
.def dist_leven(c1, c2): if len(c1) == 0: return ... if len(c2) == 0: return ... c1_moins_derniere_lettre = c1[:-1] c2_moins_derniere_lettre = c2[:-1] if c1[-1] == c2[-1]: return dist_leven(...,...) else: dist_supr_dern_let_c1 = dist_leven(..., ...) + 1 dist_supr_dern_let_c2 = dist_leven(..., ...) + 1 dist_subst_dern_let = dist_leven(..., ...) + 1 dres = min(..., ..., ...) return ...
- On suppose maintenant que le coût d'une substitution est le
double de celui d'une suppression ou d'une insertion (le coût
d'une suppression ou d'une insertion sera toujours de
1
mais le le coût d'unesubstitution
sera de maintenant de2
). Écrire la définition d'une fonctiondist_leven_subst_double
calculant cette nouvelle distance. - On suppose maintenant que le coût d'une substitution est deux
fois moindre que celui d'une suppression ou d'une insertion (le
coût d'une suppression ou d'une insertion sera toujours de
1
mais le le coût d'unesubstitution
sera de maintenant de0.5
). Écrire la définition d'une fonctiondist_leven_suppr_et_ins_double
calculant cette nouvelle distance.