## Question 1

def est_present(L,x) :
    for elt in L :
        if x == elt :
            return True
    return False

## Question 2

def compte(L,x) :
    rep = 0
    for elt in L :
        if elt == x :
            rep += 1
    return rep

## Question 3

def max(L) :
    assert len(L) > 0

    rep = L[0]
    for elt in L :
        if elt > rep :
            rep = elt
    return rep

## Question 4

def indice_max(L) :
    assert len(L) > 0

    rep = [0]
    for i in range (1,len(L)) :
        if L[i] > L[ rep[0] ] :
            rep = [i]
        elif L[i] == L[ rep[0] ] :
            rep.append(i)
    return rep

## Question 5

def fact(n) :
    assert n >= 0

    if n == 0 :
        return 1
    else :
        return n * fact(n-1)

def binom(n,p) :
    return fact(n) / (fact(p)*fact(n-p))

## Question 6

def binom2(n,p) :
    if p == 0 :
        return 1
    if p == n :
        return 1
    else :
        return binom2(n-1,p-1) + binom2(n-1,p)

## Question 7

L = [1,2,3,4,5,6,7,8,9]
L_inv1 = L[::-1]

# On peut aussi le faire en plusieurs instructions
L_inv2 = []
for i in range (len(L)) :
    L_inv2.append(L[len(L)-1-i])

## Question 8

def PGCD(a,b) :
    assert a > 0 or b > 0
    if a == 0 :
        return b
    elif b == 0 :
        return a

    for i in range (min(a,b),0,-1) :
        if a%i == 0 and b%i == 0 :
            return i

    assert False # Normalement non atteignable

def PGCD2(a,b) :
    assert a > 0 or b > 0

    if b > a :
        return PGCD2(b,a)

    while b != 0 :
        a, b = b, a%b
    return a

## Question 9

def base2to10(L) :
    """
    En O(len(L)*log(len(L)))
    Attention à la puissance de 2
    """
    rep = 0
    for i in range(len(L)) :
        if L[i] == 1 :
            rep += 2**i
    return rep

def base2to10opti(L) :
    """
    Meilleur complexité : en O(len(L))
    """
    rep = 0
    puiss2 = 1
    for i in range(len(L)) :
        if L[i] == 1 :
            rep += puiss2
        puiss2 = puiss2 * 2
    return rep

## Question 10

def base10to2(x) :
    rep = []
    while x != 0 :
        if x % 2 == 1 :
            rep.append(1)
        else :
            rep.append(0)
        x = x // 2
    return rep

## Question 11

def max_deux(L) :
    assert len(L) >= 2

    max1 = L[0]
    max2 = L[1]
    if max2 > max1 :
        max2, max1 = max1, max2
    for i in range(2,len(L)) :
        elt = L[i]

        if elt > max1 :
            max1, max2 = elt, max1
        elif elt > max2 :
            max2 = elt
    return max2

## Question 12

def dicho(f,a,b,eps) :
    assert b > a # Intervalle défini
    assert f(b) * f(a) < 0 # Existence d'un zéro

    while b-a> eps :
        m = (b+a)/2

        if f(m) * f(a) < 0 :
            b = m
        elif f(m) * f(b) < 0 :
            a = m
        else :
            return m
    return m

# Pour tester :

def racine_carre(n) :
    def f(x) :
        return x * x - n
    return dicho(f,0,n,0.001)

print("La racine carré de 4 est", round(racine_carre(4), 4))
print("La racine carré de 81 est : ", round(racine_carre(81), 4))

## Question 13

def dicho_liste(L,x) :
    a = 0
    b = len(L) - 1
    while b-a >= 1 :
        m = (b+a)//2
        if x > L[m] :
            a = m + 1
        else :
            b = m
    return L[a] == x

## Question 14

def suite_succes(L) :
    rep = []
    ind = 0

    while ind < len(L) :
        suite = 0
        while ind < len(L) and L[ind] :
            suite += 1
            ind +=1
        if suite != 0 :
            rep.append(suite)
        ind += 1
    return rep

## Question 15

def injective(L,p) :
    """
    Possible sans dico mais optimisée avec
    """
    dico_presence = {}
    for elt in L :
        if elt in dico_presence :
            return False
        else :
            dico_presence[elt] = True
    return True

def surjective(L,p) :
    liste_cherche = [False for i in range(p)]
    for elt in L :
        pos_elt = elt - 1
        liste_cherche[pos_elt] = True

    return not (False in elt)

def bijective(L,p) :
    return injective(L,p) and surjective(L,p)

## Question 16

def plus_proche(L) :
    assert len(L) >= 2

    ecart = abs(L[0] - L[1])
    elem = (L[0],L[1])
    for i in range (len(L)) :
        for j in range (i+1,len(L)) :
            if abs( L[i] - L[j] ) < ecart :
                ecart = abs(L[i] - L[j])
                elem = ( L[i] , L[j] )
    return elem

## Question 17

def occurences_lettres(s) :
    dic = {}
    for c in s :
        if not c in dic :
            dic[c] = 0

        dic[c] += 1
    return dic

def occurences_mot(s) :
    dic = {}
    ind = 0
    while ind < len(s) :
        mot = ""
        while ind < len(s) and s[ind] != " " :
            mot += s[ind]
            ind += 1
        if len(mot) > 0 :
            if not mot in dic :
                dic[mot] = 0
            dic[mot] += 1
        ind += 1
    return dic

## Question 18

from random import random # Importation du module random()

def generer_terrain(N,min,max) :
    return [[round(min + random()*(max-min)) for _ in range (N)] for _ in range (N)]
    """
        La fonction round n'est pas nécessaire pour avoir la bonne réponse.
        Elle permet cependant une meilleur visualisation du résultat
    """

## Question 19

def lissage(M) :
    rep = [[0 for i in range (len(M))] for i in range (len(M))]
    for i in range (0,len(M)) :
        for j in range (0, len(M)) :
            somme = 0
            for ki in range (-1,2) :
                for kj in range(-1,2) :
                    if ki == 0 or kj == 0 :
                        i_vois = (i + ki) % len(M)
                        j_vois = (j + kj) % len(M)
                        somme += M[i_vois][j_vois]
            rep[i][j] = somme / 5
    return rep

## Question 20

def voisins1(N,x,y,k) :
    """
    Il manquait l'entrée N à la première version
    """
    rep = []
    for kx in range (-k,k+1) :
        for ky in range (-k,k+1) :
            if abs(kx) + abs(ky) <= k :
                x_vois = (x + kx) % N
                y_vois = (y + ky) % N
                rep.append((x_vois,y_vois))
    return rep

def voisins2(N,x,y,k) :
    """
    Il manquait l'entrée N à la première version
    """
    rep = []
    for kx in range (-k,k+1) :
        for ky in range (-(k-abs(kx)),k+1-abs(kx)) :
            x_vois = (x + kx) % N
            y_vois = (y + ky) % N
            rep.append((x_vois,y_vois))
    return rep