TP 2: Conditionnement, boucles et fonctions¶
Dans ce cours, on peut utiliser Spyder ou le notebook Jupyter. Vous choisirez ce qui vous convient le mieux. On pourra tout de même utiliser la console pour effectuer des tests rapides, ou obtenir de l'aide (essayer help(len) dans la console).
Quelques remarque sur la rédaction d'un script. Il est important d'écrire des scripts qui soient lisible, par vous même, mais aussi par n'importe quelle personne qui voudrait utiliser votre code.
- Tout ce qui est écrit après un # ne sera pas interprété lors de l’exécution d'un script. Ceci permet de commenter un script et expliquer le fonctionnement de blocs d'instructions.
- Des standards de rédaction de script ont été réalisés. En voici deux exemples importants \begin{enumerate}
- Le PEP 8 développé par la communauté Python: https://www.python.org/dev/peps/pep-0008/
- mais aussi par Google: https://github.com/google/styleguide/blob/gh-pages/pyguide.md
def premier_1(n):
for j in range(2,n): # variable qui va parcourir les diviseurs possibles
if n%j == 0:
print("%s n'est pas premier, divisible pas %s" % (n,j))
break # On sort de la boucle si on a trouvé un diviseur de n
if j == n-1: # Si on n'en a pas trouvé,
# on arrive à cette condition et donc n est premier.
print("%s est premier" % n)
premier_1(5)
premier_1(14)
premier_1(25)
premier_1(37)
5 est premier 14 n'est pas premier, divisible pas 2 25 n'est pas premier, divisible pas 5 37 est premier
En fait Python permet une syntaxe plus élégante. Il s'agit des boucles for...else.
def premier_2(n):
for j in range(2,n):
if n%j == 0:
print("%s n'est pas premier, divisible pas %s" % (n,j))
break
else: # Si rien n'a été executé dans la boucle for,
# les instructions de else s'appliquent.
print("%s est premier" % n)
premier_2(5)
premier_2(14)
premier_2(25)
premier_2(37)
5 est premier 14 n'est pas premier, divisible pas 2 25 n'est pas premier, divisible pas 5 37 est premier
On peut tout à fait utiliser des boucles while. Voici plusiuers propositions similaires.
def premier_3(n):
div = 2 # variable qui va parcourir les diviseurs possibles
while div < n:
if n % div != 0 and div < n-1:
div += 1
elif n % div != 0 and div == n-1:
print("%s est premier" % n)
break
else:
print("%s n'est pas premier, divisible pas %s" % (n, div))
break
premier_3(5)
premier_3(14)
premier_3(25)
premier_3(37)
5 est premier 14 n'est pas premier, divisible pas 2 25 n'est pas premier, divisible pas 5 37 est premier
Comme pour les boucles for, il existe en Python des boucles while...else qui permettent une syntaxe plus élégante.
def premier_4(n):
div = 2
while div <= n-1:
if n % div == 0:
print("%s n'est pas premier, divible par %s" % (n, div))
break
div += 1
else:
print("%s est premier" % n)
premier_4(5)
premier_4(14)
premier_4(25)
premier_4(37)
5 est premier 14 n'est pas premier, divible par 2 25 n'est pas premier, divible par 5 37 est premier
Pour finir, en réalité, on n'a pas besoin d'effectuer le test jusqu'à n. Aller jusqu'à n//2 suffit, car le quotient avec un diviseur est plus grand que 2!
def premier_5(n):
div = 2
n_max = n//2
while div <= n_max-1:
if n % div == 0:
print("%s n'est pas premier, divible par %s" % (n, div))
break
div += 1
else:
print("%s est premier" % n)
premier_5(5)
premier_5(14)
premier_5(25)
premier_5(37)
5 est premier 14 n'est pas premier, divible par 2 25 n'est pas premier, divible par 5 37 est premier
Exercice 2¶
Écrire une fonction qui renvoie la décomposition binaire d'un entier naturel. Par exemple $5 = \mathbf{1}\times 2^2 +\mathbf{0}\times 2^1+ \mathbf{1}\times 2^0$ et donc $5_{(2)}=101$. On mettra le résultat sous forme de liste ($[1,0,1]$ pour notre exemple).¶
Pour un entier $n$ qu'on décompose de la manière suivante, $$n=\sum_{j=0}^M a_j 2^j,\qquad a_j\in\{0,1\}$$ son écriture en base 2 correspond à la collection des coefficients $a_j$: $$ n_{(2)}=a_Ma_{M-1}\dots a_0.$$
Le but est donc de déterminer ses coefficients. Pour cela on remarque que $$ n = \sum_{j=1}^M a_j 2^j + a_0\times2^0 = 2\Big(\sum_{j=0}^{M-1} a_{j+1} 2^j\Big)+ a_0\times2^0$$
Donc si on prend le reste de la division de $n$ par $2$, on obtient $a_0$. Ensuite, pour obtenir les autres coeffients, on répéte l'opération avec $$ (n-r)//2 = \sum_{j=0}^{M-1} a_{j+1} 2^j, $$ et ainsi de suite pour obtenir successivement $a_1$, $a_2$, jusqu'à $a_M$.
def binaire1(n):
n_temp = n
ans = []
while n_temp > 0:
r = n_temp % 2
ans.insert(0,r)
n_temp = (n_temp - r)//2
print('le codage bianaire de %s est %s' % (n, ans))
binaire1(5)
binaire1(14)
binaire1(25)
binaire1(37)
le codage bianaire de 5 est [1, 0, 1] le codage bianaire de 14 est [1, 1, 1, 0] le codage bianaire de 25 est [1, 1, 0, 0, 1] le codage bianaire de 37 est [1, 0, 0, 1, 0, 1]
On peut comparer ces résultats avec ceux de la fonction Python.
print(bin(5))
print(bin(14))
print(bin(25))
print(bin(37))
0b101 0b1110 0b11001 0b100101
La version récursive de la fonction factoriel se base sur la relation $n!=n\times (n-1)!$
def factoriel_rec(n):
if n == 1:
return n
else:
return n*factoriel_rec(n-1)
factoriel_rec(2)
2
factoriel_rec(3)
6
factoriel_rec(5)
120
factoriel_rec(7)
5040
Les deux versions non récursive suivantes calcul $n!$ suivant $n\times(n-1)\times \dots\times1$ et $1\times\dots\times (n-1)\times n$.
def factoriel(n):
x = n
for j in range(n-1,1,-1):
x *= j
return x
def factoriel_bis(n):
if n == 1: # utilise un if en plus
return n
else:
x = 1
for j in range(1,n+1):
x *= j
return x
factoriel(2), factoriel_bis(2)
(2, 2)
factoriel_rec(3), factoriel_bis(3)
(6, 6)
factoriel_rec(5), factoriel_bis(5)
(120, 120)
factoriel_rec(7), factoriel_bis(7)
(5040, 5040)
On rapelle qu'on peut créer un dictionnaire par compréhension de dictionnaire
compt_voyelles = {x:0 for x in 'aeiouy'}
On va rentrer une phrase
phrase = input("Rentrer une phrase:")
Pour transformer les majuscules en minuscule, on utilise la méthode .lower, et ce sera sur cette chaine de caractere qu'on va compter les voyelles.
phrase.lower()
'bienvenue a tous'
for x in compt_voyelles.keys():
compt_voyelles[x] = phrase.lower().count(x)
compt_voyelles
{'a': 1, 'e': 3, 'i': 1, 'o': 1, 'u': 2, 'y': 0}
On peut résumer tout cela sous forme de fonction.
def compt_voyelle():
compt_voyelles = {x:0 for x in 'aeiouy'}
phrase = input("Rentrer une phrase:")
for x in compt_voyelles.keys():
compt_voyelles[x] = phrase.lower().count(x)
return compt_voyelles
compt_voyelle()
{'a': 1, 'e': 3, 'i': 1, 'o': 1, 'u': 2, 'y': 0}
ans = [ ] # initialisation avec la liste vide
for x in range(10):
if x % 2 == 0:
ans.append(x**2) # ajout de $\texttt{x}^2$ si $\texttt{x}$ est pair
else:
ans.append(x**3) # ajout de $\texttt{x}^3$ si $\texttt{x}$ est impair
print(ans)
[0, 1, 4, 27, 16, 125, 36, 343, 64, 729]
Pour les compréhensions de liste (ou autres), il faut un peu d'entrainement, mais après ça devient assez naturel.
[x**2 if x%2 == 0 else x**3 for x in range(10)]
[0, 1, 4, 27, 16, 125, 36, 343, 64, 729]
ans = [ ] # initialisation avec la liste vide
for i in range(3):
for j in range(4):
ans.append((i, j)) # ajout du couple à la liste chaque itération
print(ans)
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3)]
[(i, j) for i in range(3) for j in range(4)]
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3)]
Exercice 7¶
Soit $n$ un entier naturel non nul de décomposition en base $10$ $$ n = \sum_{k=0}^{p-1}\alpha_k 10^k,$$ avec $\alpha_k \in\{0,\dots,9\}$ pour $k\in\{0,\dots,p-2\}$ et $\alpha_{p-1}\neq 0$. On dit que $n$ est un nombre d'Armstrong si $$ n = \sum_{k=0}^{p-1}\alpha_k ^p.$$
Par exemple :
- $153 = 1\times 10^2 + 5\times 10^1 + 3\times 10^0 = 1^3 + 5^3 + 3^3$
- $1634 = 1\times 10^3 + 6\times 10^2 + 3\times 10^1 + 4\times 10^0 = 1^4 + 6^4 + 3^4 + 4^4 $
- Écrire une fonction qui test si un entier est d'Armstrong.
- Écrire une fonction qui renvoie tous les nombres d'Armstrong plus petit qu'un entier $m$ donné.
Une astuce pour tester un nombre est de considérer son écriture comme une chaine de caractère. On pourra alors itérer sur les différentes décimal du nombre.
def test_armstrong(n):
n_str = str(n) # conversion de l'entier en chaine de caractère
len_n = len(n_str) # on détermine le nombre de décimale de l'entier
n_test = 0
for x in n_str: # On itère sur les décimales qu'on éleve à une certaine puissance
n_test += int(x)**len_n # Chaque décimale est reconvertie
# en entier pour effectuer le calcul numérique
if n_test == n: # Et enfin on teste si la relation a bien lieu.
print("%s est un nombre d'Armstrong" % n)
else:
print("%s n'est pas un nombre d'Armstrong" % n)
test_armstrong(153)
153 est un nombre d'Armstrong
test_armstrong(1634)
1634 est un nombre d'Armstrong
test_armstrong(23)
23 n'est pas un nombre d'Armstrong
Pour retourner la liste des entiers d'Armstrong plus petit qu'un entier $N$, on procède de la même manière, sauf que quand on en a un, on l'enregistre dans une liste.
def list_armstrong(N):
list_arm = []
for n in range(0,N+1):
n_str = str(n)
len_n = len(n_str)
n_test = 0
for x in n_str:
n_test += int(x)**len_n
if n_test == n:
list_arm.append(n)
return list_arm
list_armstrong(1634)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634]
Ici, le principe est le suivant. Au lieu d'appliquer la définition et de calculer plein de factoriel qui peuvent couter cher en temps calcul, on utilise la relation
$\begin{pmatrix} n \\ k \end{pmatrix} =\begin{pmatrix} n-1 \\ k \end{pmatrix} + \begin{pmatrix} n-1 \\ k-1 \end{pmatrix},$
pour $k\in\{1,\dots,n-1\}$. Ce qui revient à dire que pour passer de la ligne $n-1$ à la ligne $n$, il faut sommer le $k$ième coeficient et le $k-1$ième de la ligne $n-1$ pour obtenir le $k$ième coefficient de la $n$ième ligne.
Enfin, pour $k=0$ et $k=n$, autrement dit pour le premier et le dernier coefficient de chaque ligne, les coefficient binomiaux valent $1$.
def tri_pascal(n):
if n==1:
return [1]
elif n==2:
return [1, 1]
else:
l_upper = [1,1]
for j in range(2,n):
l_lower = [l_upper[k-1]+l_upper[k] for k in range(1,j)]
# compréhension de liste
l_lower.insert(0,1) # on rajoute 1 au début de la liste
l_lower.append(1) # et à la fin
l_upper = l_lower
return l_lower
tri_pascal(3)
[1, 2, 1]
tri_pascal(4)
[1, 3, 3, 1]
tri_pascal(5)
[1, 4, 6, 4, 1]
tri_pascal(6)
[1, 5, 10, 10, 5, 1]