Algorithmes Classiques

def euclide(a, b) :
    while a != b :
        if a > b :
            a = a - b
        else :
            b = b - a
    return a

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

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

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

def somme_liste(l) :
    somme = 0
    for x in l  :
        somme = somme + x
    return somme

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

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

def recherche_lineaire(l, x) :
    for i in range(len(l)) :
        if l[i] == x :
            return i
    return -1

def compter(l, x) :
    c = 0
    for e in l :
        if e == x :
            c = c + 1
    return c

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

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

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) ]

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 ]

def histogramme(m) :
    h = [0]*256
    for l in m : # Pour chaque ligne de M
        for x in l : # Pour chaque élément de la ligne
            h[x] += 1
    return h

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 + 1
        else :
            fin = milieu
    return -1

def somme_rec(L, i) :
    """
    Entrées : L une liste d'entier, $0 \leq i \leq \symtt{len}(L)$.
    Sorties : \symtt{sum(L[:i])
    """
    if i == 0 :
        return 0
    s = somme_rec(L,i-1)
    return s + L[i-1]
 
def somme(L) :
    return somme_rec(L,len(L))

def maximum_rec(L, i) :
    """
    Entrées : L une liste d'entier, $0 \leq i \leq \symtt{len}(L)$.
    Sorties : \symtt{max(L[:i])
    """
    if i == 0 :
        return -float('inf')
    m = maximum_rec(L,i-1)
    if m > L[i-1] :
        return m
    return L[i-1]
 
def maximum(L) :
    return maximum_rec(L,len(L))

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)

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)

def nb_occ(s) :
    d = {}
    for c in s :
        if c  in d :
            d[c] += 1
        else :
            d[c] = 1
    return d

def degre(g) :
    deg = [ len(g[s]) for s in range(len(g)) ]
    for s in range(len(g)) :
        for v in g[s] :
            deg[v] += 1
    return deg

from collections import deque

# Utilisation d'une file : fifo pour avoir la bonne complexité.

def parcours_largeur(g, source) :
    n = len(g)
    marquage = [False] * n
    fifo = deque()
    fifo.append(source)
    marquage[source] = True
    # Traiter source ...
    while len(fifo) > 0 :
        s = fifo.popleft()
        for v in g[s] :
            if not marquage[v] :
                fifo.append(v)
                marquage[v] = True
                # Traiter v ...
    return # Quelque chose peut-être

# Utilisation d'une pile : lifo pour avoir la bonne complexité.
def parcours_profondeur(g, source) :
    n = len(g)
    marquage = [False] * n
    lifo = []
    lifo.append(source)
    while len(lifo) > 0 :
        s = lifo.pop()
        if not marquage[s] :
            marquage[s] = True
            # Traiter s ...
            for v in g[s] :
                if not marquage[v] :
                    lifo.append(v)
    return # Quelque chose peut-être

def visiter(g, s, marquage) :
    marquage[s] = True
    # Traitement de source
    for v in g[s] :
        if marquage[v] != True :
            visiter(g, v, marquage)
            # ou ; r = visiter(g, v, marquage)
    return # Quelque chose peut-être
 
def parcours_profondeur(g, source) :
    n = len(g)
    marquage = [False] * n
    visiter(g,source,marquage)
    # ou ; r = visiter(g, source, marquage)
    return # Quelque chose peut-être

def dijkstra(g,source) :
    n = len(g)
    # Structures
    distances = [float(inf)]*n
    parents = [None]*n
    file_prio = creer()
    # Initialisation
    distances[source] = 0
    ajoute(file_prio, source, 0)
    # Algorithme
    while not est_vide(file_prio) :
        # On récupère le sommet non visité à distance minimale
        s = enleve_min(file_prio)
        # On relache tous les voisins
        for voisin, poids in g[s] :
            distance_par_s = distances[s] + poids
            if distance_par_s < distances[voisins] :
                distances[voisins] = distance_par_s
                parents[voisin] = s
                ajoute(file_prio, voisin, distances[voisins])
    return distances, parents

def creer() : # $\O(1)$
    return {}
 
def est_vide(file_prio) : # $\O(1)$
    return len(file_prio) == 0
 
def ajoute(file_prio, x, prio) : # $\O(1)$
    file_prio[x] = prio
 
def enleve_min(file_prio) : # $\O(\symtt{len(file_prio)})$
    min_key, min_prio = None, float('inf')
    for x, prio in file_prio.items() :
        if prio < min_prio :
            min_key, min_prio = x, prio
    file_prio.pop(min_key)
    return min_key

def astar(g, heuristique, source, destination) :
    n = len(g)
    # Structures
    distances = [float(inf)]*n
    parents = [None]*n
    file_prio = creer()
    # Initialisation
    distances[source] = 0
    ajoute(file_prio, source, 0)
    # Algorithme
    while not est_vide(file_prio) :
        # On récupère le sommet non visité à distance minimale
        s = enleve_min(file_prio)
        # ***** Une différence est ici *****
        if s == destination :
            break
        # On relache tous les voisins
        for voisin, poids in g[s] :
            distance_par_s = distances[s] + poids
            if distance_par_s < distances[voisins] :
                distances[voisins] = distance_par_s
                parents[voisin] = s
                ajoute(file_prio, voisin,
                       # ***** Une autre différence est ici *****
                       distances[voisins]+h(g,source,destination,voisin))
    return distances, parents