Algorithmes Classiques

1. Numériques
2. Séquences
3. Boucles imbriquées

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 = 0
    # 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 objet 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 objet 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 objet 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

3. Boucles imbriquées

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) :
    n = len(s)
    m = len(w)
    # Recherche linéaire (for) d'une fenetre qui contient w
    for i in range(0,n-m+1) :
        # Recherche linéaire (while) d'un caractère différent
        # dans la fenêtre.
        j = 0
        i_diff = -1
        while j < m :
            if w[j] != s[i+j] :
                i_diff = j
            j += 1
        # Si on n'a pas trouvé de caractère dans la fenêtre
        # c'est la bonne fenêtre.
        if i_diff == -1 :
            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

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

3.3. Copie d’une matrice

Entrées : m une matrice \(p\times q\)
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

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