Algorithmes sur entiers

Cette page reprend quelques grands algorithmes classiques sur les nombres entiers, et introduit quelques algorithmes ayant des applications en chimie.

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 : gcd.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.

• Algorithme d'Euclide
• http://stackoverflow.com/questions/11175131/code-for-greatest-common-divisor-in-python
• 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 !)

• http://xkcd.com/287/
• http://paternault.fr/informatique/jouets/aperitif.html et ici

• http://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos

• formules CHON
• protéines
• spectro de masse ?

• http://www.mi.fu-berlin.de/wiki/pub/ABI/QuantProtP4/isotope-distribution.pdf
• https://www.biostars.org/p/66772/