TP3 IPT : complexité

##############
#
# SUJET 0 CCP 2015
#
###################
from functools import reduce
 
# Q.1
 
def fact(n) :
    assert n >= 0, 'factorielle définie sur N'
    acc = 1
    for k in range(1, n+1) :
        acc *= k
    return acc
    
def fact2(n) :
    assert n >= 0, 'factorielle définie sur N'
    if n == 0 :
        return 1
    return n*fact2(n - 1)
    
def fact3(n) :
    assert n >= 0, 'factorielle définie sur N'
    return reduce(lambda acc, k: acc*k, range(1, n + 1), 1)
    
# Q.2 
def seuil(M) : # à éviter car bcp de calculs inutiles : quadratique
    n = 0
    while fact(n) <=  M :
        n += 1
    return n
    
def seuil2(M) : # plus efficace : linéaire
    f, n = 1, 0
    while f <= M :
        n += 1
        f *= n
    return n
    
# Q.3
 
def est_divisible(n) :
    return fact(n) % (n + 1) == 0
    
# Q.4
 
def mystere_plus(n) :
    s = 0
    f = 1
    for k in range(1, n+1) :
        f *= k
        s += f
    return s
 
 
 
##################
##  CCP 2015 MATH II 
######################
 
#Q.4
 
def somme_chiffres(n) :
    s = 0
    while n > 0 :
        c = n % 10
        s += c
        n //= 10
    return s
    
def somme_chiffres_rec(n) :
    if n < 10 :
        return n
    return n%10 + somme_chiffres_rec(n // 10)
 
 
############################
#
# PAYSAN RUSSE
#
##############################
 
def russky_moujik(x,y) :
    def moujikchou(a,b,acc) :
        if a == 0 : 
            return acc
        return moujikchou(a//2, b*2, acc + b*(a % 2))
    return moujikchou(x, y, 0)
    
def russian_peasant(x,y) :
    a, b, acc = x, y, 0
    while a > 0 :
        acc += b*(a % 2)
        b *= 2
        a //= 2
        print(a*b + acc) # c'est l'invariant de boucle
    return acc
 
 
 
 
 
########################
##
## HORNER
##
##########################"
 
def horner(P,t) :
    """ bit de poids faible à gauche"""
    acc = 0
    for coeff in P[-1::-1] :
        acc = coeff + t*acc
    return acc
 
def horn(P,t) :
    if P == [] :
        return 0
    return P[0] + t*horn(P[1:],t)