Algorithmes Classiques
Table of Contents
1. Numériques
1.1. Algorithme d’Euclide
Entrées : Deux entiers \(a\) et \(b\)
Sortie : \(\mathtt{pgcd}(a,b)\)
def euclide(a, b) : while a != b : if a >= b : a = a - b else : b = b - a return a
1.2. Test de Primalité
Entrées : un entier \(n \geq 2\)
Sortie : True ssi \(n\) est premier
def premier(n) : p = True d = 2 # Recherche d'un diviseur entre 2 et la racine carré de n while d * d <= n : if n % d == 0 : p = False d = d + 1 return p
1.3. Suite de Fibonacci
La suite de Fibonacci est définie par récurrence double :
\[ F_0 = 0 ,\, F_1 = 1 ,\, F_{n+2} = F_{n+1} + F_{n} \]
Entrées : un entier \(n \geq 0\)
Sortie : \(F_n\)
def fibonacci(n) : f = 0 f_suivant = 1 rang = 1 # Calcul du rang n en calculant chaque rang i successivement while rang != n : f_suivant2 = f + f_suivant f = f_suivant f_suivant = f_suivant2 rang = rang + 1 return f
1.4. Suite de Syracuse
La suite de Syracuse est définie par récurrence :
\[S_{{n+1}}={\begin{cases}{\dfrac {S_{n}}{2}}&{\mbox{si }}S_{n}{\mbox{ est pair,}}\\3S_{n}+1&{\mbox{si }}S_{n}{\mbox{ est impair.}}\end{cases}} \]
Entrées : un entier \(s \geq 1\)
Sortie : Le premier entier \(n \geq 0\) tel que \(S_n = 1\)
def syracuse(s0) : # Rang 0 s = s0 rang = 0 # Calcul du rang suivant dans s, jusqu'à ce que s == 1 while s != 1 : if s % 2 == 0 : s = s // 2 else : s = 3 * s + 1 rang = rang + 1 return rang
2. Séquences
2.1. Somme des éléments d’une liste
Entrées : une liste d’entiers relatifs.
Sortie : la somme des entiers de la liste.
def somme_liste(l) : somme = 0 for x in l : somme = somme + x return somme
2.2. Maximum
Entrées : une liste d’entiers L
Sortie : l’indice du maximum de la liste
def imax(l) : if len(l) == 0 : return -1 i_max = 0 maxi = l[0] for i in range(1,len(l)) : if l[i] > maxi : maxi = l[i] i_max = i return i_max
2.3. Recherche linéaire - version while
Entrées : Liste l et un élément x
Sortie : L’indice de la première occurrence de x dans l, ou -1 si x n’est pas dans l
def recherche_lineaire(l, x) : n = len(l) i_x = -1 i = 0 while i < n and i_x == -1 : if l[i] == x : i_x = i i = i + 1 return i_x
2.4. Recherche linéaire - version for
Entrées : Liste l et un élément x
Sortie : L’indice de la première occurrence de x dans l, ou -1 si x n’est pas dans l
def recherche_lineaire(l, x) : for i in range(len(l)) : if l[i] == x : return i return -1
2.5. Comptage
Entrées : Liste l et un élément x
Sortie : Le nombre de fois que x apparaît dans l
def compter(l, x) : c = 0 for e in l : if e == x : c = c + 1 return c
2.6. Second Minimum
Entrées : Liste d’entiers positifs, disjoints, l de taille supérieure à 2
Sortie : Le second minimum de l
def deuxieme_minimum(l) : if l[0] < l[1] : m = l[0] second_m = l[1] else : m = l[1] second_m = l[0] for i in range(2,len(l)) : x = l[i] if x < m : second_m = m m = x elif x < second_m : second_m = x return second_m