Nombre de problèmes mathématiques et les algorithmes associés tournent autour des entiers. Bien souvent ces algorithmes sont simples et accessibles à des développeurs débutants.

PGCD

Explications

Le calcul du plus grand commun diviseur est un classique des mathématiques. L’une des méthodes pour le calculer est tiré du lemme d’Euclide :

Soit un couple d'entiers naturels non nuls (a,b), si des entiers naturels q

et r, avec r ≠ 0, sont tels que a = bq + r , alors : PGCD(a,b) = PGCD(b,r).

Pratiquons quelques exemples afin d’en déduire l’algorithme :

PGCD( 782, 221 )

• 782 = 3 × 221 + 119

• 221 = 1 × 119 + 102

• 119 = 1 × 102 + 17

• 102 = 6 x 17 + 0

PGCD( 17, 13 )

• 17 = 1 x 13 + 4

• 13 = 3 x 4 + 1

• 4 = 4 x 1 + 0

Algorithme Python récursif

L’algorithme que l’on en déduit est :

Cet algorithme est dit récursif car la fonction PGCD utilise dans son implémentation un appel à elle-même. Ecrit en algorithme Python, cela nous donne :

Le caractère ‘%’, qui sert à obtenir le reste de la division entière a par b, nécessite une petite astuce pour l’obtenir via le clavier de la calculatrice Numworks. Il faut presser la touche Toolbox

Puis accéder au menu « Catalogue » pour trouver le caractère.

Algorithme Python non-récursif

La récursivité, en programmation, est souvent inefficace en termes de performance. Heureusement, nous pouvons dé-récursifier l’algorithme grâce à une boucle tant que :

Le packing, au sens des tuples, consiste à construire un tuple à partir de plusieurs valeurs (empaqueter), ce qui se traduit par les exemples suivants :

• t=(2, 3, 4)

• u=2, 3, 4

L’unpacking ou la sortie du paquetage consiste à extraire les données du tuple en les affectant à des variables comme dans l’exemple suivant :

• x, y, z = t

• a, b, c = 2, 6, 7

En profitant de cette astuce sur les tuples ainsi que sur l’évaluation des calculs, nous pouvons écrire en Python :

Algorithme Python sans modulo

Une variante de l’algorithme existe et permet d’éviter les modulos au profit de soustractions dont voici l’algorithme :

Ce qui nous donne en algorithme Python :

Le crible d’Eratosthène

Un peu d'histoire

Eratosthène de Cyrène est un grand scientifique grec né en -276 et mort en -194 à Alexandrie dont il fut directeur de la grande bibliothèque. Ce scientifique fut le premier à calculer le diamètre de la Terre. Il inventa et nomma une discipline : la géographie (souvent difficile pour les élèves 😉).  

Il a travaillé notamment sur les nombres premiers succédant ainsi à Pythagore. Voici comment on définit les nombres premiers :

Un nombre premier est un entier naturel non-nul qui est seulement divisible par 2 entiers distincts : 1 et lui-même.

Il a décrit l’algorithme du crible qui porte son nom et qui permet, facilement, de trouver tous les nombres premiers entre 1 et n. Cet algorithme ne nécessite pas de compétence particulière en mathématiques pour être mis en œuvre : il ne fait appel qu’aux additions sur les entiers.

Exemple :

Nous allons mettre en application le crible pour trouver les nombres premiers compris entre 1 et n=99 inclus. Pour cela nous aurons besoin d’une grille :

Cette grille représente une case pour chaque nombre de 0 à 99 inclus, nous y avons placé les unités en colonnes et les dizaines en lignes. Au démarrage de l’algorithme, toutes les cases sont vides et les cases auront 2 états :

• Vide (fond blanc) : indique un nombre premier

• Pleine (fond gris) : indique un nombre multiple d’un nombre premier

Étape 1 :

Éliminez 0 et 1 qui ne sont pas des nombres premiers en grisant les cases correspondantes. La case pour ‘0’ est sur la ligne pour 0 dizaine et sur la colonne ‘0’ unité.

Étape 2 :

Nous allons parcourir les cases dans l’ordre à partir de 2. La case ‘2’ est vide : c’est donc un nombre premier. Il nous faut donc éliminer tous les multiples de 2.

Étape 3 :

Nous passons à la case suivante ‘3’. La case est vide c’est donc un nombre premier ! Eliminons tous les multiples.

Étape 4 :

On passe à la case suivante : ‘4’. Elle est grisée : c’est donc un multiple…

Étape 5 :

On passe à la case ‘5’, elle est vide : c’est donc un nombre premier. Eliminons tous les multiples !

Étape 6 :

La case ‘6’ est grisée, c’est donc un multiple.

Étape 7 :

La case ‘7’ est vide : c’est donc un nombre premier. Eliminons tous les multiples !

Étape 8 :

On passe à la prochaine case non grisée : ‘11’. Eliminons les multiples.

Mais réfléchissons un peu, les multiples de 11 sont :

• 22 = 2 x 11

• 33 = 3 x 11

• 44 = 4 x 11 = 2 x 2 x 11

• 55 = 5 x 11

• 66 = 6 x 11 = 2 x 3 x 11

• 77 = 7 x 11

• 88 = 8 x 11 = 2 x 2 x 2 x 11

• 99 = 9 x 11 = 3 x 3 x 11

Nous avions déjà éliminé les multiples de 2, 3, 5 et 7. En fait le premier multiple de 11 que nous n’avons pas encore éliminé est 11x11 qui est en dehors de notre espace de recherche. Lorsque l’on est en train de travailler sur le nombre premier p, partant du principe que nous avons traité tous les nombres premiers plus petits que p, le premier multiple à éliminer est donc p². On peut donc arrêter l’algorithme dès lors que l’on a passé la case correspondante à la racine carrée de n (n=99). Donc, une fois passé la case 10, nous avons déjà éliminé tous les multiples entre 1 et 99 !

Choix des structures de données

Bien choisir les types des données ainsi que les structures dont nous aurons besoin fera une grosse différence entre un algorithme simple à écrire ou un algorithme (inutilement) complexe. Notre grille est, en fait, un tableau numéroté de 0 à 99 inclus : la forme de la grille (2 dimensions) était plus pour faciliter la représentation dans un article (les feuilles ne sont pas très larges).

Les cases ont 2 états : vide (blanche) ou cochée (grisée). En gros, elles sont soit vraies (le nombre est premier) soit fausses (le nombre n’est pas premier). Le type adéquat en Python est donc le type ‘bool’ pour les valeurs booléennes (True et False).

L'algorithme

Voici l'algorithme :

fonction ListePremiers ( n )
  # initialisation
  n + 1 → N
  tableau de N éléments initialisés à Vrai  t
  Faux → t[ 0 ]
  Faux → t[ 1 ]
  Racine carrée de N convertit en entier  last
  # boucle d’élimination
  pour i de 2 à last
    si t[ i ] est vrai alors
      pour j de i*i à N avec un pas de i
        faux → t[ j ]
      fin pour 
    fin si
  fin Pour
  # récupération du résultat
  tableau vide → resultat
  pour i de 2 à N
    si t[ i ]

Cela peut sembler long et compliqué mais, en Python, on peut l’écrire de façon plus concise grâce aux astuces syntaxiques du langage. En effet, la création d’un tableau de n valeurs initialisé à une valeur simple x (booléen, entier, flottants, par exemple) s’écrit en Python : [x]*n. Cela permet d’éviter une boucle d’initialisation.

De même, une fois les éliminations des multiples effectuées, le filtrage pour récupérer les nombres premiers est simplifié par l’usage d’une liste par compréhension [i for i in range(2, N) if t[i]].

from math import sqrt
def ListePremiers( n ):
  # initialisation
  N=n+1
  last=int(sqrt(N))
  t=[True]*N
  # boucle d'elimination
  for i in range(2, last):
    if t[i]:
      for j in range(i*i, N, i):
        t[j]=False
  # retourne le resultat
  return [i for i in range(2, N) if t[i]

Décomposer en produit de nombres premiers

Tout nombre entier peut se décomposer en un produit de nombres premiers. Si Euclide en avait jeté les bases, c’est Carl Friedrich Gauss qui en finalisa la démonstration. Par une méthode de force brute (on va parcourir tous les entiers inférieurs au nombre à décomposer), il est assez facile d’extraire les facteurs. En premier lieu, il nous faut savoir si un nombre entier est divisible, au sens euclidien du terme, par un autre entier.

Théorème de la division euclidienne

Le théorème de la division euclidienne dans les entiers naturels (les nombres entiers pris à partir de 0) s'énonce ainsi :

À deux entiers naturels a et b, b ≠ 0, on associe de façon unique deux entiers naturels, le quotient q et le reste r, qui vérifient :

• a = bq + r

• r < b

L'unicité du reste se déduit de ce que le seul multiple de b strictement inférieur à b est 0, or la différence de deux restes vérifiant les deux conditions est un tel entier. L'unicité du quotient se déduit de celle du reste.

Est divisible par

Etant donné deux entiers a et b, en Python les résultats de la division euclidienne peuvent s’obtenir de différentes façons :

• q = a // b retourne le quotient de la division euclidienne

• r = a%b retourne le reste de la division euclidienne

• q, r = divmod(a, b) retourne en même temps le quotient et le reste

Déterminer si a est divisible par b consiste donc à vérifier que le reste r de la division euclidienne de a par b est nul. Ce qui se traduit en Python par : a % b == 0.

Diviser pour régner

La décomposition va se faire par la méthode de la force brute : nous essayerons tous les nombres premiers dans l’ordre croissant en partant de 2. Pour des raisons pratiques, nous ne décomposerons que des nombres entiers positifs ; nous mettons une sécurité pour éliminer les nombres négatifs en retournant None. Nous allons tester toutes les valeurs comprises entre 2 et √n si n est supérieur ou égal à 2. A chaque fois que l’on trouve un diviseur, on l’ajoutera dans le tableau résultat puis on mettra à jour la valeur de n et cela « déplacera » mécaniquement la condition d’arrêt de l’algorithme Python.

La dernière condition « si n est strictement supérieur à 1 » est là pour gérer le cas n=3 et donc √n=1.73… Lors i=2 on sort de la boucle « tant que » mais « n » est toujours égal à 3. Vu que la valeur n’a pas été divisée par les nombres premiers plus petit que n c’est que celle-ci est un nombre premier. D’où le ramasse-miette avec le test « si n est strictement plus grand que 1 » pour ajouter la dernière valeur à la liste résultat.

Triangle de Pascal

Explication

Bien qu’associé en occident aux travaux de Pascal, il fut étudié bien avant par d’autres mathématiciens notamment en Chine où il est appelé triangle de Yang Hui. Il permet de calculer facilement les coefficients de (x+1)n. Voici un exemple des premières lignes de ce triangle :

Donc, comment lire ce tableau, si je veux calculer (x+1)4, je vais lire la ligne commençant par un 4 et en déduire que :  (x+1)4=1.x0 + 4.x1 + 6.x² + 4.x3 + x4 = 1 + 4.x + 6x² + 4x3 + x4

Dans sa démonstration (celle de Pascal), si nous appelons Cn,k les coefficients de la ligne n et de la colonne k, ils se déduisent en suivant les règles suivantes :

• Cn,0 = 1

• Cn,n = 1

• Cn,k = Cn-1,k-1 + Cn-1,k

Algorithme de calcul

Nous allons créer une fonction qui calculera tous les coefficients pour une valeur de n donné. Et pour se faire, nous calculerons toutes les lignes depuis la ligne 0 jusqu’à la ligne n. Dans cet algorithme t sera un tableau qui contiendra les Cn,k déjà calculés et newT servira à calculer les Cn+1, k.

fonction PascalCoefficients( n )
  [1] → t
  pour i de 1 à n
    tableau de i+1 valeurs initialisées à 1 → newT
    on ajoute 0 à la fin de t
    pour j de 1 à i-1
      t[ j – 1 ] + t[ j ] → newT[ j ]

En transformant cet algorithme sans se poser de question, on obtiendrait :

def PascalCoefficients0( n ):
  t = [ 1 ]
  for i in range( 1, n + 1 ):
    newT = [ 1 ]
    t.append( 0 )
    for j in range( 1, i ):
      newT.append( t[ j - 1 ] + t[ j ]

L’un des intérêts de Python est sa syntaxe évoluée et « très » compacte. Nous allons grâce aux fonctionnalités des listes (et notamment des listes par compréhension et de la concaténation des listes) écrire l’algorithme de la manière la plus compacte possible :

def PascalCoefficients( n ):
  t = [ 1 ]
  for i in range( 1, n + 1 ):
    t = [ 1 ] + [ t[ j - 1 ] + t[ j ] for j in range( 1, i ) ] + [ 1 ]

Si vous voulez continuer à découvrir l'univers des calculatrices programmables en Python, vous pouvez consulter cet article : Algorithme & Définition