Livre_silo 30 août 2013 16:32 Page 109
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
109
4 – Instructions : langage minimal de l’algorithmique
On considère par exemple un programme qui détermine si l’entier n est premier : il faut
a priori parcourir les entiers entre 2 et
n
2 et vérifier qu’aucun d’entre eux ne divise n.
En réalité, on peut s’arrêter à
√
n car si n = p × q avec p >
√
n alors q est un diviseur
de n inférieur à
√
n. On peut donc écrire le programme suivant :
import math
premier = True
for i in range(2, int(math.sqrt(n))+1):
if n % i == 0:
premier = False
La racine carrée est calculée à l’aide de la fonction math.sqrt. On n’oubliera pas l’instruction
import math pour y avoir accès.
Cependant, on s’aperçoit vite que lorsque n n’est pas premier, ce programme effectue des
calculs inutiles, puisqu’ on pourrait arrêter la boucle dès qu’on a trouvé un diviseur. Une
première solution consiste à réécrire la boucle for en une boucle while, ce qui est toujours
possible. On peut alors préciser dans la condition du while qu’il faut s’arrêter dès qu’un
diviseur est trouvé, autrement dit dès que premier prend la valeur False.
premier = True
i = 2
while i <= int(math.sqrt(n)) and premier:
if n % i == 0:
premier = False
i = i + 1
Une autre approche est de conserver la boucle for et d’en sortir au moyen de l’instruction
break dès qu’ on rencontre un diviseur.
premier = True
for i in range(2, int(math.sqrt(n))+1):
if n % i == 0:
premier = False
break
Ainsi, il n’ est pas nécessaire de gérer le compteur de boucle à la main. Cette méthode reste à
utiliser avec parcimonie, car dans des programmes plus conséquents, elle peut compliquer
la compréhension des différents cas de sortie de la boucle.
4.4.5 Boucles imbriquées
Quand l’instruction à exécuter à l’intérieur d’une boucle est elle aussi répétitive, le corps
de cette boucle contient une seconde boucle et on dit qu’elles sont imbriquées. Les bornes
de la boucle interne dépendent souvent du compteur de la boucle externe.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
109
4 – Instructions : langage minimal de l’algorithmique
On considère par exemple un programme qui détermine si l’entier n est premier : il faut
a priori parcourir les entiers entre 2 et
n
2 et vérifier qu’aucun d’entre eux ne divise n.
En réalité, on peut s’arrêter à
√
n car si n = p × q avec p >
√
n alors q est un diviseur
de n inférieur à
√
n. On peut donc écrire le programme suivant :
import math
premier = True
for i in range(2, int(math.sqrt(n))+1):
if n % i == 0:
premier = False
La racine carrée est calculée à l’aide de la fonction math.sqrt. On n’oubliera pas l’instruction
import math pour y avoir accès.
Cependant, on s’aperçoit vite que lorsque n n’est pas premier, ce programme effectue des
calculs inutiles, puisqu’ on pourrait arrêter la boucle dès qu’on a trouvé un diviseur. Une
première solution consiste à réécrire la boucle for en une boucle while, ce qui est toujours
possible. On peut alors préciser dans la condition du while qu’il faut s’arrêter dès qu’un
diviseur est trouvé, autrement dit dès que premier prend la valeur False.
premier = True
i = 2
while i <= int(math.sqrt(n)) and premier:
if n % i == 0:
premier = False
i = i + 1
Une autre approche est de conserver la boucle for et d’en sortir au moyen de l’instruction
break dès qu’ on rencontre un diviseur.
premier = True
for i in range(2, int(math.sqrt(n))+1):
if n % i == 0:
premier = False
break
Ainsi, il n’ est pas nécessaire de gérer le compteur de boucle à la main. Cette méthode reste à
utiliser avec parcimonie, car dans des programmes plus conséquents, elle peut compliquer
la compréhension des différents cas de sortie de la boucle.
4.4.5 Boucles imbriquées
Quand l’instruction à exécuter à l’intérieur d’une boucle est elle aussi répétitive, le corps
de cette boucle contient une seconde boucle et on dit qu’elles sont imbriquées. Les bornes
de la boucle interne dépendent souvent du compteur de la boucle externe.