Table des matières
Ceci est une ancienne révision du document !
Algorithmes sur entiers
Cette page reprend quelques grands algorithmes classiques sur les nombres entiers, et introduit quelques algorithmes ayant des applications en chimie.
Recherche du PGCD (plus grand commun diviseur)
Explication géométrique : en comprenant un nombre entier comme une longueur et un couple d'entiers (a,b) comme un rectangle, leur PGCD est la longueur du côté du plus grand carré permettant de carreler entièrement ce rectangle. L'algorithme d'Euclide décompose ce rectangle en carrés, de plus en plus petits, par divisions euclidiennes successives, de la longueur par la largeur, puis de la largeur par le reste, jusqu'à un reste nul (observez bien ici !). Cela donne ceci en Python : <sxh python; title : pgcd.py> #!/usr/bin/env python # -*- coding: UTF-8 -*- def gcd(a, b):
"""Calculate the Greatest Common Divisor of a and b.
Unless b==0, the result will have the same sign as b (so that when b is divided by it, the result comes out positive). """ while b: a, b = b, a%b return a
n1=210 n2=126 print gcd(n1, n2) </sxh>
Si on dispose des décompositions en facteurs premiers d'un nombre entier, on peut aussi établir la valeur du PGCD en effectuant le produit de tous les facteurs communs.
Références
- https://docs.python.org/dev/library/fractions.html#fractions.gcd (version incluse dans le langage)
- http://en.literateprograms.org/Euclidean_algorithm_%28Python%29 (améliorable !)
Nombres premiers
Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs (qui sont alors 1 et lui-même) : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, …
Pour lister les nombres premiers strictement inférieur à un nombre N donné, un algorithme naïf (appelés tests de primalité) consiste à considérer les naturels un par un, en essayant de le diviser par tous les nombres inférieurs à sa racine carrée : s'il est divisible par l'un d'entre eux, il est composé, et sinon, il est premier. Voici une implémentation en Python de cette idée.
<sxh python; title : nombres_premiers-01.py> #!/usr/bin/env python # -*- coding: UTF-8 -*- “”“ Liste de nombres premiers strictement inférieurs à un entier donné ”“” def isprime(n):
for x in range(2,int(n**0.5)+1): if n % x == 0: return False return True
def primelist(n):
return [a for a in range(2,n) if isprime(a)]
p=primelist(1000) print p </sxh>
L'algorithme peut être rendu plus efficace : il suggère beaucoup de divisions inutiles, par exemple, si un nombre n'est pas divisible par 2, il est inutile de tester s'il est divisible par 4. En fait, il suffit de tester sa divisibilité par tous les nombres premiers inférieurs à sa racine carrée. Le crible d'Ératosthène est une méthode, reposant sur cette idée, qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. En supprimant tous les multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier, et qui sont donc les nombres premiers. Voici une implémentation en Python du crible d'Ératosthène :
<sxh python; title : nombres_premiers-03.py> #!/usr/bin/env python # -*- coding: UTF-8 -*- “”“ Liste de nombres premiers strictement inférieurs à un entier donné ”“” def primelist(n):
""" Version avec crible d'Eratosthenes """ li = range(n+1) # création d'une liste d'entiers jusque n li[1] = 0 # 0 (déjà à 0) et 1 ne sont pas premiers ncur = 2 # prochain nombre à tester while ncur ** 2 <= n: # tant que ncur est inférieur à sqrt(n) li[ncur*2::ncur] = [0] * (n // ncur - 1) # éliminer (mettre à 0) # les multiples de ncur # ncur suivant (il ne doit pas être déjà mis à zéro) ncur += 1 while not li[ncur]: ncur += 1 return [a for a in li if a != 0] # renvoie une liste avec les élements non nuls
p=primelist(1000) print p </sxh>
Références
- Nombre premier (wikipedia)
- Crible d'Ératosthène (wikipedia)
Factorisation en nombres premiers
Références
- http://anh.cs.luc.edu/331/code/factoring.py (intéressant)
Recherche du PPCM
Problème du sac à dos
Problème des apéritifs
Applications chimiques
- formules CHON(S)
- protéines
- spectro de masse ?