Programmes à connaître

Général

Échanger le contenu de deux variablesEn une ligne

copie = a
a = b
b = copie

a, b = b, a  # création d'un tuple (b, a) puis déballage

Conversion binaireVersion récursive

def binaire(n):
    """ Renvoie l'écriture binaire de l'entier positif n. """
    if n == 0:
        return '0'  # cas particulier
    bits = '' 
    while n > 0:    # algorithme des divisions successives
        reste = n % 2
        bits = str(reste) + bits
        n = n // 2
    return bits

def binaire(n):
    if n <= 1:
        return str(n)
    return binaire(n // 2) + str(n % 2)

Listes

Parcours par indiceParcours par élément

for i in range(len(tab)):
    print(i, tab[i])

for valeur in tab:
    print(valeur)

SommeMoyenneMoyenne pondérée

def somme(tab):
    total = 0
    for valeur in tab:
        total = total + valeur
    return total

def moyenne(tab):
    total = 0
    for valeur in tab:
        total = total + valeur
    return total / len(tab)

def moyenne_ponderee(notes, coeffs):
    total = 0
    total_coeffs = 0
    for i in range(len(notes)):
        total += notes[i] * coeffs[i]
        total_coeffs += coeffs[i]
    return total / total_coeffs

>>> tab = [12, 21, 37, 42]
>>> somme(tab)
112
>>> moyenne(tab)
28.0
>>> moyenne_ponderee(tab, [1, 1, 1, 2])
30.8

Recherche linéaireIndiceTous les indicesNombre d'occurences

def rechercher(tab, x):
    """ Renvoie True si x est présent dans tab, False sinon. """
    for valeur in tab:
        if valeur == x:
            return True
    return False

L'expression rechercher(tab, x) est équivalent à x in tab.

def rechercher_indice(tab, x):
    """ Renvoie l'indice de la 1ère occurence de x s'il est présent dans tab, None sinon. """
    for i in range(len(tab)):
        if tab[i] == x:
            return i
    return None

def rechercher_indices(tab, x):
    """ Renvoie tous les indices où apparaît x dans tab. """
    indices = []
    for i in range(len(tab)):
        if tab[i] == x:
            indices.append(i)
    return indices

def compter(tab, x):
    """ Renvoie le nombre d'occurences de x dans tab. """
    compteur = 0
    for valeur in tab:
        if valeur == x:
            compteur += 1
    return compteur

>>> tab = [12, 42, 21, 37, 42]
>>> rechercher(tab, 42)
True
>>> rechercher_indice(tab, 42)
1
>>> rechercher_indices(tab, 42)
[1, 4]
>>> compter(tab, 42)
2

MinimumIndiceTous les indices

def minimum(tab):
    """ Renvoie le minimum de tab. """
    mini = tab[0]  # minimum courant
    for valeur in tab:
        if valeur < mini:
            mini = valeur
    return mini

def indice_minimum(tab):
    """ Renvoie le 1er indice du minimum de tab. """
    m = 0  # indice du minimum courant
    for i in range(len(tab)):
        if tab[i] < tab[m]:
            m = i
    return m

def indices_minimum(tab):
    """ Renvoie les indices où apparaît le minimum de tab. """
    indices = [0] # indices du minimum courant
    for i in range(len(tab)):
        if tab[i] < tab[indices[0]]:
            indices = [i]
        elif tab[i] == tab[indices[0]]:
            indices.append(i)
    return indices

>>> tab = [21, 37, 7, 42, 7]
>>> minimum(tab)
7
>>> minimum_indice(tab)
2
>>> minimum_indices(tab)
[2, 4]

Tri par sélectionTri par insertionTri fusion

Complexité $O(n^2)$

def tri_selection(tab):
    for i in range(len(tab) - 1):
        # Détermine l'indice du minimum à partir de l'indice i
        m = i
        for j in range(i + 1, len(tab)):
            if tab[j] < tab[m]:
                m = j
        # Échange le contenu de tab[i] et tab[m]
        tab[i], tab[m] = tab[m], tab[i] 

Complexité $O(n^2)$

def tab_insertion(tab):
    for i in range(len(tab)):
        valeur = tab[i]  # valeur à insérer
        # Décale tant que la valeur précédent est plus grand
        j = i
        while j > 0 and tab[j] > valeur:
            tab[j] = tab[j - 1]
            j -= 1
        tab[j] = valeur  # insertion

Complexité $O(n \log n)$

def fusionner(A, B):
    """ Fusionne deux listes triées en une seule liste triée. """
    F = []
    a, b = 0, 0  # indices pour parcourir A et B
    while a < len(A) and b < len(B):
        if A[a] < B[b]:
            F.append(A[a])
            a += 1
        else:
            F.append(B[b])
            b += 1
    return F + A[a:] + B[b:]  # ajoute les éléments restants

def tri_fusion(tab):
    if len(tab) <= 1:  # cas de base
        return tab
    m = len(tab) // 2
    G, D = tab[:m], tab[m:]              # Étape 1. Diviser
    G, D = tri_fusion(G), tri_fusion(D)  # Étape 2. Régner 
    return fusionner(G, D)               # Étape 3. Combiner

Recherche dichotomiqueVersion récursive

Complexité $O(\log n)$

def dichotomie(tab, x):
    """ Recherche l'élément x dans la liste triée tab par dichotomie
        et retourne son indice s'il existe, None sinon. """
    i, j = 0, len(tab) - 1  # indices de la fenêtre de recherche
    while j >= i:  # tant qu'il reste des éléments dans la fenêtre
        m = (i + j) // 2
        if tab[m] == x:
            return m
        elif tab[m] < x:
            i = m + 1
        else:
            j = m - 1
    return None

Complexité $O(\log n)$

def dichotomie_bornes(tab, x, i, j):
    if i > j:  # cas de base, si la fenêtre de recherche est vide
        return None
    m = (i + j) // 2
    if tab[m] == x:
        return m
    elif tab[m] < x:
        return dichotomie_bornes(tab, x, m + 1, j)
    else:
        return dichotomie_bornes(tab, x, i, m - 1)

def dichotomie(tab, x):
    return dichotomie_bornes(tab, x, 0, len(tab) - 1)

>>> dichotomie([12, 21, 37, 42], 37)
2
>>> dichotomie([12, 21, 37, 42], 90)
None

Chaînes

Une chaîne de caractères est une liste de caractères, tous les algorithmes précédents peuvent s'y appliquer.

Dictionnaires

Parcours par cléParcours par valeurParcours par clé et valeur

for cle in dico:
    print(cle)

for valeur in dico.values():
    print(valeur)

for cle, valeur in dico.items():
    print(cle, valeur)

Utilisation comme compteur

def compter(tab):
    compteurs = {}
    for valeur in tab:
        if valeur in compteurs:
            compteurs[valeur] += 1
        else:
            compteurs[valeur] = 1
    return compteurs

Arbres

class Noeud:
    def __init__(self, v, g, d):
        self.valeur = v
        self.gauche = g  # sous-arbre gauche
        self.droit  = d  # sous-arbre droit

Insertion fonctionnelleInsertion en place

def inserer(arbre, x):
    """ Insère la valeur x dans l'ABR arbre et renvoie l'arbre modifié. """
    if arbre is None:
        return Noeud(x, None, None)
    if x < arbre.valeur:
        arbre.gauche = inserer(arbre.gauche, x)
    else:
        arbre.droit  = inserer(arbre.droit,  x)
    return arbre

def inserer(arbre, x):
    """ Insère la valeur x dans l'ABR arbre. """
    if x < arbre.valeur:
        if arbre.gauche is None:
            arbre.gauche = Noeud(x, None, None)
        else:
            inserer(arbre.gauche, x)
    else:
        if arbre.droit is None:
            arbre.droit = Noeud(x, None, None)
        else:
            inserer(arbre.droit, x)