In [ ]:
from __future__ import division, print_function # Python 3
On a vu dans les chapitres précédents comment définir des fonctions avec def, des boucles avec while et for et des tests avec if ainsi que quelques exemples sur chaque notion mais indépendants des autres. Très souvent en programmation, on a besoin d'utiliser plus tous ces outils à la fois. C'est leur utilisation simultanée qui permet de résoudre des problèmes très divers et de les exprimer en quelques lignes de code.
Dans ce chapitre, nous allons voir quelques exemples qui utilisent les fonctions, les boucles et les conditions dans un même programme.
La suite de Syracuse une suite d'entiers naturels définie de la manière suivante. On part d'un nombre entier plus grand que zéro ; s’il est pair, on le divise par 2 ; s’il est impair, on le multiplie par 3 et on ajoute 1. En répétant l’opération, on obtient une suite d'entiers positifs dont chacun ne dépend que de son prédécesseur. Par exemple, la suite de Syracuse du nombre 23 est:
23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ...
Après que le nombre 1 a été atteint, la suite des valeurs (1, 4, 2, 1, 4, 2, ...) se répète indéfiniment en un cycle de longueur 3, appelé cycle trivial.
La conjecture de Syracuse est l'hypothèse selon laquelle la suite de Syracuse de n'importe quel entier strictement positif atteint 1. En dépit de la simplicité de son énoncé, cette conjecture défie depuis de nombreuses années les mathématiciens. Paul Erdos a dit à propos de la conjecture de Syracuse : "les mathématiques ne sont pas encore prêtes pour de tels problèmes".
In [ ]:
def syracuse(n):
while n != 1:
print(n, end=' ')
if n % 2 == 0:
n = n//2
else:
n = 3*n+1
In [ ]:
syracuse(23)
Out[ ]:
In [ ]:
syracuse(245)
Out[ ]:
In [ ]:
syracuse(245154)
Out[ ]:
In [ ]:
def diviseurs(n):
L = []
for i in range(1, n+1):
if n % i == 0:
L.append(i)
return L
On vérifie que la fonction marche bien:
In [ ]:
diviseurs(12)
Out[ ]:
In [ ]:
diviseurs(13)
Out[ ]:
In [ ]:
diviseurs(15)
Out[ ]:
In [ ]:
diviseurs(24)
Out[ ]:
In [ ]:
def est_premier_1(n):
L = diviseurs(n)
return len(L) == 2
In [ ]:
est_premier_1(12)
Out[ ]:
In [ ]:
est_premier_1(13)
Out[ ]:
In [ ]:
[n for n in range(20) if est_premier_1(n)]
Out[ ]:
On pourrait faire plus efficace, car il suffit de vérifier la non-existence de diviseurs inférieurs à la racine carrée de n.
In [ ]:
from math import sqrt
def est_premier(n):
sq = int(sqrt(n))
for i in range(2, sq):
if n % i == 0:
return False
return True
En utilisant cette fonciton, on trouve que la liste des premiers nombres premiers inférieurs à 20 est:
In [ ]:
[n for n in range(20) if est_premier(n)]
Out[ ]:
Le résulat est erroné! Pourquoi?
La fonction est_premier(8) retourne True en ce moment, car la racine carrée de 8 vaut 2.828 et donc sq=int(2.828) est égal à 2 et la boucle ne teste pas la valeur i=2, car range(2,2) retourne une liste vide. On peut corriger de la façon suivante en ajoutant un +1 au bon endroit:
In [ ]:
from math import sqrt
def est_premier(n):
sq = int(sqrt(n))
for i in range(2, sq+1):
if n % i == 0:
return False
return True
On vérifie que la fonction retourne bien que 4 et 8 ne sont pas des nombres premiers:
In [ ]:
[n for n in range(20) if est_premier(n)]
Out[ ]:
Mais il y a encore une erreur, car 0 et 1 ne devraient pas faire partie de la liste. Une solution est de traiter ces deux cas de base à part:
In [ ]:
from math import sqrt
def est_premier(n):
if n == 0 or n == 1:
return False
sq = int(sqrt(n))
for i in range(2, sq+1):
if n % i == 0:
return False
return True
On vérifie que tout marche bien maintenant:
In [ ]:
[n for n in range(50) if est_premier(n)]
Out[ ]: