# EXERCICE 1

# Piles : liste de taille choisie à la création (capacité de la pile + 1),
# dont le premier élément donne à tout moment la taille de la pile

def creer_pile (c): # c = taille
    p = [None] * (c+1)
    p[0] = 0
    return p

def empiler(p,element):
    assert p[0] < len(p)-1, "Plus de place dans la pile !"
    p[0] += 1
    p[p[0]] = element

def depiler(p):
    assert p[0] > 0, "Pile vide !"
    p[0] -= 1
    return p[p[0]+1]

# EXERCICE 2

# On a besoin de deux piles supplémentaires,
# car avec une seule pile on ne peut que transférer des objets
# pour accéder à un élément quelconque sans pouvoir perturber l'ordre.

# L'algorithme est simple : vider la pile dans une pile supplémentaire,
# puis vider cette dernière dans la dernière pile,
# puis vider celle-ci dans la pile de départ, elle sera alors « retournée ».
# Cela fait donc trois fois autant d'empilements et dépilements
# que d'éléments dans la pile au départ.

def est_vide(p):
    return p[0] == 0

def est_vide2(p):
    try:
        empiler(p,depiler(p))
        return False
    except:
        return True

def sommet(p):
    assert p[0] > 0, "pile vide !"
    return p[p[0]]

def sommet2(p):
    x = depiler(p)
    empiler(p,x)
    return x

def retourne(p):
    p1 = creer_pile(len(p)-1)
    p2 = creer_pile(len(p)-1)
    while not (est_vide(p)):
        empiler(p1,depiler(p))
    while not (est_vide(p1)):
        empiler(p2,depiler(p1))
    while not (est_vide(p2)):
        empiler(p,depiler(p2))
    # return p # (accepté, mais ce n'est pas dans la spécification)

# EXERCICE 3

# Cette fois-ci, on suppose que l'implémentation se fait à l'aide de listes
# et que les primitives sont écrites en utilisant append et pop.

def additionne_1(p,n): # une pile et un entier relatif
    if n == 0:
        return p
    elif n > 0:
        for i in range(n):
            if est_vide(p) or sommet(p) == '+':
                empiler(p,'+')
            else:
                _ = depiler(p)
    else:
        for i in range(-n):
            if est_vide(p) or sommet(p) == '-':
                empiler(p,'-')
            else:
                _ = depiler(p)
    return p

import copy

def additionne_2(p1,p_2): # deux piles
    p2 = copy.copy(p_2) # précaution au cas où p1 et p_2 sont la même variable
    while (not est_vide(p2)):
        if depiler(p2) == '+':
            if est_vide(p1) or sommet(p1) == '+':
                empiler(p1,'+')
            else:
                _ = depiler(p1)
        else:
            if est_vide(p1) or sommet(p1) == '-':
                empiler(p1,'-')
            else:
                _ = depiler(p1)
    return p1


# EXERCICE 4

def puiss(a,n):
    if n < 0:
        return 1 / puiss(a,-n)
    if n == 0:
        return 1
    elif n % 2 == 1:
        return a * puiss(a*a,n//2)
    else:
        return puiss(a*a,n//2)

def puiss_lin(a,n):
    if n > 0: # l'ordre est choisi de sorte qu'on minimise le nombre de tests effectués 
        return a * puiss(a,n-1)
    if n == 0:
        return 1
    return 1 / puiss(a,-n)

def puiss_n(n):
    return puiss(n,n)

# EXERCICE 5

# D'après la formule du cours, c(2n) = c(n) + n,
# donc c(2^k) = 2^(k-1) + 2^(k-2) + … + 2 + 1 + 1 = 2^k,
# d'où c(n) = O(n) pour un n quelconque.

def fonction_artificielle(n):
    def artif(n,cptr):
        assert n > 0, "n non strictement positif"
        if n == 1:
            return cptr ** 2
        else:
            for i in range(n//2,n):
                cptr += 42
            return artif(n//2,cptr)
    return artif(n,0)

# Vous l'aurez deviné, cette fonction renvoie (42*(n-1))²

# EXERCICE 6

def euclide(p,q):
    p = abs(p)
    q = abs(q)
    if p == 0 and q == 0:
        raise ValueError("p et q sont tous les deux nuls")
    elif p < q:
        return euclide(q,p)
    elif q == 0:
        return p
    else:
        return euclide(q,p % q)

def bezout(p,q):
    if p < 0:
        (u,v) = bezout(-p,q)
        return (-u,v)
    if q < 0:
        (u,v) = bezout(p,-q)
        return (u,-v)
    if p == 0 and q == 0:
        raise ValueError("p et q sont tous les deux nuls")
    elif p < q: # ceci n'arrive qu'une fois au plus, tout au début
        u,v = bezout(q,p)
        return v,u
    elif q == 0:
        return (1,0)
    else:
        (u,v) = bezout(q, p % q) # u q + v (p mod q) = pgcd(p,q)
        r = p // q # u q + v (p - rq) = pgcd(p,q)
        return (v,u-v*r) # v p + (u-vr) q = pgcd(p,q)

# EXERCICE 7

blague_comprise = False

def exo7():
    while not (blague_comprise):
        print("Poisson volant !")
    print("Hahahahaha !")