################################################################################
#             Exercices à rendre au plus tard le 01/11/2026 à 20h              #
#                                  Correction                                  #
################################################################################

###########################################
# Exercice 7. Coefficients binomiaux
###########################################

################
### Question 1
################

### 20, 4, 1 et 0

################
### Question 2
################

def binomExplicite(n,k):
    """binomExplicite(n: int, k: int) -> int"""
    if n < k:
        return 0
    res = 1
    for i in range(n-k+1, n+1):
        res *= i
    for i in range(1,k+1):
        res //= i
    return res

### Tests:

# print(binomExplicite(6,3))
# print(binomExplicite(4,1))
# print(binomExplicite(5,0))
# print(binomExplicite(3,4))

################
### Question 3
################

### La ligne d'indice n = 7 est 1,7,21,35,35,21,7,1
### La ligne d'indice n = 8 est 1,8,28,56,70,56,28,8,1

################
### Question 4
################

def ligneSuivante(L):
    """ligneSuivante(L: int list) -> int list"""
    M = [1]*(len(L)+1)
    for i in range(1,len(M)-1):
        M[i] = L[i-1] + L[i]
    return M

### Tests:

# L = []
# for i in range(10):
#     L = ligneSuivante(L)
#     print(L)

################
### Question 5
################

def binomPascal(n,k):
    """binomPascal(n: int,k: int) -> int"""
    L = []
    for i in range(n+1):
        L = ligneSuivante(L)
    return L[k]

### Tests:

# print(binomPascal(6,3))
# print(binomPascal(4,1))
# print(binomPascal(5,0))

################
### Question 6
################

import random

def milleComparaisons():
    """milleComparaisons() -> bool"""
    for _ in range(1000):
        n = random.randint(0,123)
        k = random.randint(0,n)
        if binomExplicite(n,k) != binomPascal(n,k):
            return False
    return True

### Tests:

# print(milleComparaisons())

################
### Question 7
################

def test1(L):
    """test1(L: int list) -> bool"""
    return L[0] == 1 and L[-1] == 1

### Tests:

# L = []
# for i in range(10):
#     L = ligneSuivante(L)
#     print(test1(L))

# L = [0,1,2,0]
# print(test1(L))

################
### Question 8
################

def test2(L, a, b):
    """test2(L: int list, a: float, b: float)"""
    somme = 0
    n = len(L) - 1
    for k in range(0,n+1):
        somme += a**k * b**(n-k) * L[k]
    return somme == (a+b)**n

### Tests:

# L = []
# for i in range(10):
#     L = ligneSuivante(L)
#     print(test2(L, 2, 4))
#     print(test2(L, -4, 6))

# L = [0,1,2,0]
# print(test2(L, 2 ,4))

################
### Question 9
################

def test3(L):
    """test3(L: int list) -> bool"""
    for i in range(len(L)//2):
        if L[i] != L[-i-1]:
            return False
    return True

### Tests:

# L = []
# for i in range(10):
#     L = ligneSuivante(L)
#     print(test3(L))

# L = [0,1,2,0]
# print(test3(L))

################
### Question 10
################

def test4(L):
    """test4(L: int list) -> bool"""
    for i in range((len(L)-1)//2):
        if L[i] >= L[i+1]:
            return False
    for i in range(len(L)//2, len(L)-1):
        if L[i] <= L[i+1]:
            return False
    return True

### Tests:

# L = []
# for i in range(10):
#     L = ligneSuivante(L)
#     print(test4(L))

# print(test4([0,1,2,0]))
# print(test4([0,1,1,1,0]))
# print(test4([0,1,2,2,2,0]))

# print(test4([1,4,6,4,1]))
# print(test4([4,4,6,4,1]))
# print(test4([1,4,6,4,4]))

# print(test4([]))

###########################################
# Exercice 8. Sous-ensembles de [|0; n-1|] (exercice facultatif)
###########################################

# (*) On note L_{n,k} la liste que doit renvoyer sous_ensembles(n,k). Par
# exemple: L_{4,2} = [[0,1], [0,2], [0,3], [1,2], [1,3], [2,3]].
# (*) On commence par écrire une fonction 'etape' qui prend en entrée l'entier n
# ainsi qu'une des listes L_{n,k} et renvoie la liste L_{n,k+1}.  Par exemple,
# etape(4, [[0,1], [0,2], [0,3], [1,2], [1,3], [2,3]]) doit renvoyer [[0,1,2],
# [0,1,3], [0,2,3], [1,2,3]]. Dans cet exemple, la fonction prend donc en entrée
# L_{4,2} et renvoie L_{4,3}.  Pour cela, on parcourt toutes les sous-listes de
# L_{n,k}, et pour chacune de ces sous-listes on construit certaines des
# sous-listes de L_{n, k+1}.  Pour l'exemple précédent, voici pour chacune des
# sous-listes de L_{n,k} les sous-listes de L_{n,k+1} associées:
#   [0,1] -> [0,1,2], [0,1,3],
#   [0,2] -> [0,2,3]
#   [0,3] -> aucune sous-liste
#   [1,2] -> [1,2,3]
#   [1,3] -> aucune sous-liste
#   [2,3] -> aucune sous-liste
# Finalement, on obtient [[0,1,2], [0,1,3], [0,2,3], [1,2,3]] qui est bien
# L_{n,k+1}.
# (*) Une fois que le fonction etape est écrite, il suffit de partir de L_{n,1}
# et d'appliquer 'etape' le bon nombre de fois pour obtenir L_{n,k}.

def etape(n, L):
    M = []
    for ss_ens in L:
        for j in range(ss_ens[-1]+1, n):
            M.append(ss_ens + [j])
    return M

def sous_ensembles(n, k):
    if k == 0:
        return  [[]]
    L = [[i] for i in range(n)]
    for j in range(1, k):
        L = etape(n, L)
    return L

### Tests:

# n = 5
# for k in range(n+3):
#     print(k, sous_ensembles(n, k))