TP3 IPT : complexité

Proposez des solutions pour les exercices 2-3 à 2-10 en postant un commentaire ci-dessous.

Python
##############
#
# 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)

Pour la suite du TP HOrner, c'est ici

Commentaires

Bonjour!
J'ai essayé la fin de la recherche 2.6 (multiplication russe en utilisant des opérations bit à bit).

On peut montrer en utilisant l'écriture en base 2 de x que x>>1 effectue l'opération x//2 , que x<<1 effectue l'opération 2*x et que 1&x effectue l'opération x%2 .

Ainsi, si x est pair : 1&x = 00000 donc ~(1&x) = 11111 et donc (~(1&x))+1 = (1)00000 et finalement ((~(1&x))+1)&y = 0
A l'inverse, si x est impair : 1&x = 00001 donc ~(1&x) = 11110 et donc (~(1&x))+1 = 11111 et finalement ((~(1&x))+1)&y = y

En s'inspirant de la version récursive du programme, on obtient donc :

Python
def mul(a,b):  # cette fonction empêche à l'utilisateur de rentrer un x négatif (python râle sinon) 
    assert type(a)==int and type(b)==int and a>0 and b>0 , "Multiplication d'entiers naturels"
    def MULRUSSE_bit(x,y,accu): #la fonction demandée est là
        if x==0 :
            return accu
        return MULRUSSE_bit(x>>1,y<<1,accu+(((~(1&x))+1)&y))
    return MULRUSSE_bit(a,b,0)

Voilà! (après je ne sais pas si c'est ça qui était demandé)

Bien joué Valentin !

Programme Horner

Python
def Horner(P,t):
    def aux(P,acc):
        if len(P)==1:
            return acc+P[0]
        else:
            return aux(P[1:],(acc+P[0])*t)
    return aux(P[1:],P[0]*t)
  

Y a de l'idée...Il y a quand même un problème pour les monômes:

Python
In [7]: Horner([1],1)
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
 
<ipython-input-6-a379fd4047a6> in aux(P, acc)
      4             return acc+P[0]
      5         else:
----> 6             return aux(P[1:],(acc+P[0])*t)
      7     return aux(P[1:],P[0]*t)
 
IndexError: list index out of range

OK par ailleurs : on s'aperçoit qu'on n'a pas besoin de retourner la liste.

courtesy of webmatter.de