def u_itera(n) :
    u = 2          # Initialisation : u0 = 2
    i = 1
    while i <= n :
        u = 3*u-1
        i += 1
    return u


def u_rec(n) :
    if n == 0 :
        u = 2
    else :
        u = 3*u_rec(n-1)-1
    
    return u

################################################################################

def somme_itera(n) :
    S = 0
    for k in range(1,n+1) :   # Pour k allant de 1 à n
        S = S + 1/(k*(k+1))
    return S
    
# La programmation récursive s'appuie sur le fait que 
# S(n) = S(n-1) + 1/( n*(n+1) )

def somme_rec(n) :
    if n == 1 :   # Placer cas terminal en début de fonction
        return 0.5
    else :
        s = 1/(n*(n+1)) + somme_rec(n-1)
        return s

################################################################################
################   Approche itérative de la suite de Fibonnacci   ##############
################################################################################

def fibo_itera(n) :
    if n == 0 :
        u = 0       # u = u_n : terme d'ordre n de la suite
    elif n == 1 :
        u = 1
    else :
        u_1 = 1         # u_1 désigne u_(n-1)
        u_2 = 0         # u_2 désigne u_(n-2)
        for i in range(2, n+1) :     # pour i allant de 2 à n
            u = u_1 + u_2            
            u_2 = u_1   # Préparation de la boucle suivante
            u_1 = u
    return u
    
# On peut aussi utiliser une liste pour gérer la récurrence.
# Cela donne la deuxième version ci-dessous

def fibo_itera2(n) :
    if n == 0 :
        u = 0           # u = u_n : terme d'ordre n de la suite
    elif n == 1 :
        u = 1
    else :
        ListU = [0,1]   # Liste des différents termes de la suite. 
        for i in range(2, n+1) :     # Pour i allant de 2 à n
            u = ListU[i-1] + ListU[i-2]           
            ListU.append(u)
    return u
        
################################################################################
######################      Approche récursive      ############################
################################################################################

cmpt = 0     # Compteur, défini comme une variable globale

def fibo_rec(n) :
    global cmpt
    cmpt += 1       # Chaque appel de fibo_rec augmente cmpt de 1
    
    if n == 0 :
        u = 0
    elif n == 1 :
        u = 1
    else :
        u = fibo_rec(n-1) + fibo_rec(n-2)
    return u

################################################################################

def pgcd(a,b) :
    if b == 0 :
        return a
    else :
        r = a%b
        res = pgcd(b,r)
        return res


################################################################################

def expo(x,n) :
    if n == 0 :   # Cas terminal au début de la fonction
        return 1
    else :
        if (n%2 == 0 ) :  # n pair
            y = expo(x,n//2)  #  n // 2 est la division entière de n par 2
            return y*y
        else :            # Dans ce cas n est impair
            y = expo(x, (n-1)//2)
            return x*y*y  # division entière de n-1 par 2


################################################################################
#######################    Les tours de Hanoi    ###############################
################################################################################

n = 5       # Nombre de disques
L = n*[0]   # Liste de 0

for i in range(1,n+1) :  # Pour i allant de 1 à n
    L[i-1] = n+1-i           # Attention : l'indice dans L va de 0 à n-1

piquets = [ L, [], [] ] 

def deplace(p,q) :
    print(piquets)
    input("Appuyer sur une touche")
    x = piquets[p].pop()  # On récupère le disque au sommet du piquet n°p -> x
    piquets[q].append(x)  # On le place au sommet du piquet n°q
    

def Hanoi(n,p,q,r) :
    if n == 1 :
        deplace(p,r) 
    else :
        Hanoi(n-1,p,r,q)  # On déplace n-1 disques de p --> q en passant par r
        deplace(p,r)      # On déplace le dernier disque de p --> r
        Hanoi(n-1,q,p,r)  # On déplace les n-1 disques de q --> r en passant par p


#Hanoi(5,0,1,2)