# importer factorial de la bibliotheque des fonctions mathematiques
from math import factorial
# importer time de la bibliotheque des fonctions temporelles
from time import time


def factorielle(n : int = 0) -> int :
# renvoie l entier n! avec
# n parametre entier en entree
# definition par recurrence (i. e. implantation recursive) de n!

    if not isinstance(n, int) : # si appel avec type =/= entier alors remonter
                                # une exception
        raise TypeError
    elif n == 0 :
        return 1 # 0! = 1
    else :
        return n*factorielle(n - 1) # (n+1)! = (n+1).n!


def binome1(n : int = 0, k : int = 0) -> int :
# Renvoie C(n,k) = n!/((n-k)!k!)
# nombre de combinaisons (i. e. parties) de k elements parmi n
# implantation naive
# n cardinal de l ensemble ambiant
# k cardinal d une combinaison/partie/sous-ensemble

    if k < 0 or k > n :
        raise ValueError
    else :
        # divison entiere
        return factorielle(n) // (factorielle(n-k)*factorielle(k))


def binome2(n : int = 0, k : int = 0) -> int :
# Renvoie C(n,k) = n!/((n-k)!k!)
# nombre de combinaisons (i. e. parties) de k elements parmi n
# C(n,k) = n(n-1)(n-2)...(n-k+1)/k!

    if n == 0 or k == 0 or k == n :
        return 1
    elif k > n//2 :
            k = n - k
    numerateur = n
    for l in range(n - k + 1,n) :
        numerateur = numerateur*l
    denominateur = k
    for l in range(2,k) :
        denominateur = denominateur*l
    return numerateur//denominateur


def binome3(n : int = 0, k : int = 0) -> int :
# Renvoie C(n,k) = n!/((n-k)!k!)
# nombre de combinaisons (i. e. parties) de k elements parmi n
# implantation recursive
# C(n,0) = 1 = C(n,n)
# C(n+1,k+1) = C(n,k) + C(n,k+1)

    if n < 0 or k < 0 or k > n :
        raise ValueError
    elif k == 0 or k == n :
        return 1
    elif k > n//2 :
        k = n - k
        #print('n =', n, 'k=',k)
    return binome3(n - 1, k - 1) + binome3(n - 1, k)


def binome4(n: int = 0, k : int = 0) -> int :
    # En descendant le triangle de Pascal : implantation iterative
    # en deux boucles a l aide d une variable list double (tableau) locale
    # C(i,0) = 1 = C(i,i)
    # C(i+1,j+1) = C(i,j) + C(i,j+1)
    # Attention : il faut declarer (en l intialisant) C
    if k > n//2 :
        k = n - k
    C =[[0 for i in range(n+1)] for j in range(n+1)]
    for i in range(n+1) : # indice de ligne
        for j in range(min(i,k)+1) : # indice de colonne
            if (j == 0 or j == i) :
                C[i][j] = 1
            else:
                C[i][j] = C[i-1][j-1] + C[i-1][j]
            #endif
        #endfor
    #endfor
    return C[n][k]


# Saisir l entier dont on prendra la factorielle
# convertir la chaine de caractere (str) en entier d emblee
m = int(input('Entrer un premier entier naturel : '))

# Saisir le cardinal d une combinaison (sans passer a la ligne)
print('Entrer un second entier naturel <= ',m,': ',end='')
k = int(input())

# sauter une ligne
print()

# prendre t_0
t_0 = time()

try: # executer un bloc qui generera une eventuelle exception
     # calculer la factorielle a l aide de la fonction recursive
     print('****************')
     print('On lance le test')
     print('****************')
     print(m,'! =', factorielle(m))

except TypeError: # traiter l exception TypeError generee
    print("Erreur de type à l'appel de factoriel.\n")

# temps de calcul
duree_du_calcul = time() - t_0
print("Temps de calcul : " + str(duree_du_calcul) + ' s\n')

print()

# prendre t_0
t_0 = time()

# calculer la factorielle a l aide de la fonction native (importee)
print('math.factorial(',m,') =', factorial(m))

duree_du_calcul = time() - t_0
print("Temps de calcul : " + str(duree_du_calcul) + ' s')

print()

print('binome1(',m,',',k,') = ',binome1(m,k), sep='')

print()

print('binome2(',m,',',k,') = ',binome2(m,k), sep='')

print()

print('binome3(',m,',',k,') = ',binome3(m,k), sep='')

print()

print('binome4(',m,',',k,') = ',binome4(m,k), sep='')