## Exercice 1

# 1)

def double(x):
    return 2*x


# 2)

def est_pair(n):
    if n %2 == 0:
        return True
    else:
        return False

# ou simplement

def est_pair(n):
    return n % 2 == 0


# 3)

def somme_des_multiples(a, b, n):
    somme = 0
    for k in range(a, b+1):
        if k % n == 0:
            somme = somme + k
    return somme


## Exercice 2

# 1) En itérant sur un range :

def somme(L):
    s = 0
    for i in range(len(L)):
        s = s + L[i]
    return s

# On peut aussi itérer directement sur L :

def somme(L):
    s = 0
    for x in L:
        s = s + x
    return s


# 2)

def nb_occurrences(L, x):
    nb = 0
    for i in range(len(L)):
        if L[i] == x:
            nb = nb + 1
    return nb

# ou :

def nb_occurrences(L, x):
    nb = 0
    for y in L:
        if y == x:
            nb = nb + 1
    return nb


# 3)

def maximum(L):
    m = L[0]
    for i in range(1, len(L)):
        if L[i] > m:
            m = L[i]
    return m


# 4) On ne peut renvoyer True qu'à la fin :

def tous_pairs(L):
    for x in L:
        if x % 2 == 1:
            return False
    return True


# 5)

def compris_entre(L, a, b):
    resultat = []
    for i in range(len(L)):
        if a <= L[i] <= b:
            resultat.append(L[i])
    return resultat


# 6)

def multiples(a, b, n):
    mult = []
    for k in range(a, b+1):
        if k % n == 0:
            mult.append(k)
    return mult


## Exercice 3

# 1)

def mot_le_plus_long(mots):
    mot_max = mots[0]
    for i in range(1, len(mots)):
        if len(mots[i]) > len(mot_max):
            mot_max = mots[i]
    return mot_max


# 2)

def enchevetrer(mot1, mot2):
    resultat = ""
    for i in range(len(mot1)):
        resultat = resultat + mot1[i] + mot2[i]
    return resultat


# 3) Il y a de nombreuses manières de faire. Une solution naïve en O(n^2) :

def doublons(chaine):
    vus = []
    dblons = []
    for caractere in chaine:
        if caractere in vus:
            dblons.append(caractere)
        else:
            vus.append(caractere)
    return dblons

# Avec un dictionnaire d'occurrences on peut avoir une complexité en O(n) :

def doublons(chaine):
    occurrences = {}
    for caractere in chaine:
        if caractere in occurrences:
            occurrences[caractere] += 1
        else:
            occurrences[caractere] = 1
    dblons = []
    for caractere in occurrences:
        if occurrences[caractere] > 1:
            dblons.append(caractere)
    return dblons


## Exercice 4

# 1)

def selection(prix, a, b):
    L = []
    for article in prix:
        if a <= prix[article] <= b:
            L.append(article)
    return L

# ou avec une liste par compréhension :

def selection(prix, a, b):
    return [article for article in prix if a <= prix[article] <= b]


# 2)

def fusion(d1, d2):
    d = {}
    for cle in d1:
        d[cle] = d1[cle]
    for cle in d2:
        d[cle] = d2[cle]
    return d


## Exercice 5

# 1)

def somme_tableau(t):
    s = 0
    for i in range(len(t)):
        for j in range(len(t[0])):
            s = s + t[i][j]
    return s


# 2)

def carre_tableau(t):
    tcarre = []
    for i in range(len(t)):
        ligne = []
        for j in range(len(t[0])):
            ligne.append(t[i][j]**2)
        tcarre.append(ligne)
    return tcarre


# 3)

def transposee(m):
    t = []
    for j in range(len(m[0])):
        ligne = []
        for i in range(len(m)):
            ligne.append(m[i][j])
        t.append(ligne)
    return t


## Exercice 6

# 92 -> 1011100

# -92 :
# 92 sur 8 bits -> 01011100
# complément à 1 : 10100011
# complément à 2 : 10100100

# 101110 -> 46


## Exercice 7

# 1)

# C1 = C0*C0 = 1
# C2 = C0*C1 + C1*C0 = 2
# C3 = C0*C2 + C1*C1 + C2*C0 = 5
# C4 = C0*C3 + C1*C2 + C2*C1 + C3*C0 = 14
# C5 = C0*C4 + C1*C3 + C2*C2 + C3*C1 + C4*C0 = 42


# 2)

# Sans mémoïsation :

def catalan(n):
    if n == 0:
        return 1
    s = 0
    for i in range(n):
        s += catalan(i)*catalan(n-1-i)
    return s

# Avec mémoïsation :

memo = {0: 1}

def catalan(n):
    if n not in memo:
        s = 0
        for i in range(n):
            s += catalan(i)*catalan(n-1-i)
        memo[n] = s
    return memo[n]


## Exercice 8

graphe = {'A': ['B', 'C'],
          'B': ['A', 'D', 'E'],
          'C': ['A', 'F'],
          'D': ['B'],
          'E': ['B', 'F'],
          'F': ['C', 'E']}

# 1)

def nombre_aretes(graphe):
	nb = 0
	for sommet in graphe:
		nb += len(graphe[sommet])
	return nb // 2


# 2)

def complementaire(graphe):
    compl = {}
    for s in graphe:
        compl[s] = []
        for t in graphe:
            if t != s and t not in graphe[s]:
                compl[s].append(t)
    return compl


# 3)

matrice = [[0, 1, 1, 0, 0, 0],
           [1, 0, 0, 1, 1, 0],
           [1, 0, 0, 0, 0, 1],
           [0, 1, 0, 0, 0, 0],
           [0, 1, 0, 0, 0, 1],
           [0, 0, 1, 0, 1, 0]]

def nombre_aretes(matrice):
    nb = 0
    for ligne in matrice:
        for elt in ligne:
            nb += elt
    return nb // 2

def complementaire(matrice):
    n = len(matrice)
    mat = [[0]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            if i != j and matrice[i][j] == 0:
                mat[i][j] = 1
    return mat