Algorithmes Classiques

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

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

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(len(l)) :
        if l[i] > maxi :
            maxi = l[i]
            i_max = i
    return i_max

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

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

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

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

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

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 bin(n) :
    if n == 0 :
        return ""
    bin_quot = bin(n//2)
    if n % 2 == 0 :
        return bin_quot + "0"
    return bin_quot + "1"

def bin2(n, k) :
    if n == 0 :
        return "0"*k
    if n < 0 :
        return bin2(2**k + n, k)
    bin_quot = bin2(n//2)
    if n % 2 == 0 :
        return bin_quot + "0"
    return bin_quot + "1"

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