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.
Références
- Nombre premier (wikipedia)
- Crible d'Ératosthène (wikipedia)
- …
Factorisation en nombres premiers
Recherche du PPCM
Problème du sac à dos
Problème des apéritifs
Applications chimiques
- formules CHON(S)
- protéines
- spectro de masse ?