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
    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
    if n > 0 : # Si n = 0, il n'y a aucun calcul à faire
        # Rang 1
        f = 1
        f_prev = 0
        rang = 1
        # Calcul du rang n en calculant chaque rang i successivement
        while rang != n :
            f_suivant = f + f_prev
            f_prev = f
            f = f_suivant
            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 :
        rang = rang + 1
        if s % 2 == 0 :
            s = s // 2
        else :
            s = 3 * s + 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 not l :
        return -1
    i_max = 0
    maxi = l[0]
    for i,x in enumerate(l) :
        if x > maxi :
            maxi = x
            i_max = i
    return i_max

2.3. Minimum

Entrées : une liste d’entiers L
Sortie : l’indice du minimum de la liste 

def imin(l) :
    if not l :
        return -1
    i_min = 0
    mini = l[0]
    for i,x in enumerate(l) :
        if x < mini :
            mini = x
            i_min = i
    return i_min

2.4. Moyenne

Entrées : une liste d’entiers L
Sortie : la moyenne des valeurs de la liste l 

def moyenne(l) :
    somme = 0
    for x in l :
        somme = somme + x
    return somme / len(l)

2.5. Recherche linéaire - version while

Entrées : Liste l et un élément x
Sortie : L’indice de la première occurence de x dans l, ou -1 si x n’est pas dans l 

def recherche_lineaire(l, x) :
    i_x = -1
    i = 0
    n = len(l)
    while i < n and i_x == -1 :
        if l[i] == x :
            i_x = i
        i = i + 1
    return i_x

2.6. Recherche linéaire - version for dans fonction

Entrées : Liste l et un élément x
Sortie : L’indice de la première occurence de x dans l, ou -1 si x n’est pas dans l 

def recherche_lineaire(l, x) :
    for i, y in enumerate(l) :
        if y == x :
            return i
    return -1

2.7. 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.8. 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 x in l[2:] :
        if x < m :
            second_m = m
            m = x
        elif x < second_m :
            second_m = x
    return second_m

3. Double Boucles

3.1. Algorithme de la Fenêtre Glissante

Entrées : s, w deux chaînes de caractères non vides.
Sortie : i >= 0, le plus petit indice de s tel que w est une sous-chaîne de s à la position i. 

def rechercher(s,w) :
    for i in range(0,len(s)-len(w)+1) :
        j = 0
        while j < len(w) and w[j] == s[i+j] :
            j += 1
        if j == len(w) :
            return i
    return -1

3.2. Création d’une matrice \(n \times m\)

Entrées : n, m deux entiers positifs non nuls
Sortie : Une matrice de dimension \(n \times m\) remplie de None 

def matrice(n,m) :
    M = []
    for i in range(n) :
        L = [ None ] * m
        M.append(L)
    return M

ou 

def matrice(n,m) :
    return [ [ None ] * m for i in range(n) ]

3.3. Copie d’une matrice

Entrées : M une matrice
Sortie : Une copie de M 

def copie(M) :
    M_copie = []
    for L in M : # Pour chaque ligne de M
        L_copie = []
        for x in L : # Pour chaque élément de la ligne
            L_copie.append(x)
        M_copie.append(L_copie)
    return M_copie

ou 

def copie(M) :
    return [ [ x for x in L ] for L in M ]

4. Algorithmes Glouton

4.1. Rendu de monnaie

On suppose que le système monétaire choisi permet toujours de rendre la monnaie.
Entrées : Un liste, L, de billets (entiers) dans l’ordre croissant et un montant, m, (entier).

Sortie : Une liste de billet de L dont la somme vaut m de taille minimale. 

def rendu(L,m) :
    R = []
    reste = m
    i = len(L)-1 # i représente le plus gros billet éventuellement utilisable.
    while reste > 0 :
        if L[i] <= reste : # si on peux utiliser le plus gros billet, on l'utilise
            R.append(L[i])
            reste = reste - L[i]
        else : # sinon on considère le billet d'en dessous.
            i = i-1
    return R

5. Algorithmes Dichotomiques

5.1. Exponentiation rapide

Entrées : \(a\) un entier et \(b\) un entiers positifs.
Sortie : \(a^b\) 

def exponentiation_rapide(a,b) :
    r = 1
    u = a
    v = b
    while v > 0 :
        if v % 2 == 1 :
            r = r * u
        u = u * u
        v = v // 2
    return r

5.2. Recherche de 0 d’une fonction

Entrées : \(a < b\) deux flottants, \(e > 0\) un flottant et \(f\) une fonction continue sur \([a,b]\) telle que \(f(a)f(b) < 0\)
Sortie : un flottant \(x\) telle \(\exists x - e \leq c \leq x + e, f(c) = 0\) 

def recherche_dichotomique_zero(a,b,e,f) :
    debut = a
    fin = b
    while fin - debut > e :
        milieu = (debut + fin ) / 2
        if f(milieu) == 0 :
            return milieu
        elif f(milieu) * f(debut) > 0 :
            debut = milieu
        else :
            fin = milieu
    return debut

5.3. Recherche dichotomique dans une liste triée

Entrées : Une liste d’entiers triés dans l’ordre croissant et un entier x.

Sortie : L’indice de x dans L, -1 si x n’est pas dans L 

def recherche_dichotomique(L,x) :
    debut = 0
    fin = len(L)
    while fin - debut > 0 :
        milieu = (debut + fin) // 2
        if L[milieu] == x :
            return milieu
        elif L[milieu] < x :
            debut = milieu
        else :
            fin = milieu
    return -1

6. Algorithmes récursifs

6.1. Maximum

Entrées : une liste d’entiers positifs.
Sortie : le maximum de la liste 

def maximum(L) :
    if not L :
        return -1
    else :
        a = L[0]
        b = maximum(L[1:])
        if a < b :
            return b
        return a

6.2. Somme

Entrées : une liste d’entiers relatifs
Sortie : la somme des entiers de la liste 

def somme(L) :
    if not L :
        return 0
    else :
        return L[0] + somme(L[1:])

6.3. Exponentiation rapide

Entrées : \(a\) un entier et \(b\) un entiers positifs.
Sortie : \(a^b\) 

def exp(a,b) :
    if b == 0 :
        return 1
    elif b % 2 == 0 :
        return exp(a * a , b // 2)
    else :
        return a * exp( a * a, b // 2)

6.4. Recherche Dichotomique

Entrées : Une liste d’entiers triés dans l’ordre croissant et un entier x.
Sortie : L’indice de x dans L, -1 si x n’est pas dans L 

def recherche_dichotomique(L,x) :
    if not L :
        return -1
    else :
        m = len(L) // 2
        if L[m] == x :
            return m
        elif L[m] > x :
            return recherche_dichotomique(L[:m],x)
        else :
            return m + 1 + recherche_dichotomique(L[m+1:],x)

6.5. Tri Fusion

Entrées : Une liste d’entiers
Sortie : Une copie de cette liste triée dans l’ordre croissant.

On suppose qu’il existe une fonction ayant la spécification suivante : 

def fusion(l1 : list[int], l2 : list[int]) -> list[int] :
    """
    Entrées : deux listes d'entiers triés.
    Sortie: une liste triée contenant les éléments des deux listes en entrée.
    """

def tri_fusion(l) :
    n = len(l)
    if n < 2 :
        return l[:]
    l1 = tri_fusion(l[:n//2])
    l2 = tri_fusion(l[n//2:])
    return fusion(l1,l2)

Author: Samy Jaziri

Created: 2023-06-01 Thu 22:56