Programme interro_rapide_30_minutes_2012_10_2.py

# coding: latin-1

# question 1

def factorielle (n) :
    res = 1
    while n > 1 : 
        res *= n
        n -= 1
    return res
    
print factorielle (3)
    
# voici la version récursive qui n'était pas demandée :    
def factorielle_recursive (n) :
    return n*factorielle_recursive (n-1) if n > 1 else 1
        
# question 2

def f(a,b) :
    
    # f(a,b) = f(a-1,b) + f(a,b-1)
    # la formule implique de calculer toutes les valeurs f(i,j)
    # avec (i,j) dans [[0,a]] x [[0,b]]
    # un moyen afin d'éviter de trop nombreux calculs est de 
    # stocker les valeurs intermédiaires de f dans une matrice
    # il faut ensuite s'assurer que f(a-1,b) et f(a,b-1) 
    # ont déjà été calculées avant de calculer f(a,b)
    # pour cela, on parcourt la matrice dans le sens des i et j croissants
    # il ne faut pas oublier les a+1,b+1 car range (a) est égal à [ 0,1, ..., a-1 ]
    
    mat = [ [ 0 for i in range (b+1) ] for j in range (a+1) ]
    for i in range (a+1) :
        for j in range (b+1) :
                if i == 0 or j == 0 :
                    mat [i][j] = max (i,j)
                else :
                    mat [i][j] = mat [i-1][j] + mat[i][j-1]
    return mat [a][b]

# on teste pour des valeurs simples
print f(0,5) # affiche 5
print f(1,1) # affiche 2
# on vérifie en suite que cela marche pour a < b et b > a
print f (4,5)  # affiche 210
print f (5,4)  # affiche 210

# autres variantes

# la version récursive ci-dessous est juste beaucoup plus longue, elle appelle
# la fonction f_recursive autant de fois que la valeur retournée 
# par la fonction cout_recursive alors que la fonction précédente 
# effectue de l'ordre de O(a*b) calculs
def f_recursive(a,b) :
    return f_recursive(a-1,b) + f_recursive(a,b-1) if a > 0 and b > 0 else max(a,b)

def cout_recursive(a,b) :
    return cout_recursive(a-1,b) + cout_recursive(a,b-1) if a > 0 and b > 0 else 1

# une autre version non récursive
def f(a,b) :
    mat = { }
    for i in range (a+1) :
        for j in range (b+1) :
                mat [i,j] = mat [i-1,j] + mat[i,j-1] if i > 0 and j > 0 else max (i,j)
    return mat [a,b]