1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| # -*- coding: latin-1 -*-
# La liste initiale des nombres que vous donnez en exemple
ListeNombres=[1,2,3,4,5]
# restitue la décomposition de n en système binaire sous forme de liste
# exemple si n=32
# la valeur retournée est [1,0,0,0,0]
def binaire (n):
L=[]
while n:
L.insert(0,n%2)
n=n/2
return L
#même chose que précédemment mais avec normalisation sur p chiffres
# en rajoutant au besoin des 0 devant
# exemple si n=32 et p = 7
# la valeur retournée est [0,0,1,0,0,0,0]
def normalise (n, p):
return [0]*(p-len(binaire(n)))+binaire(n)
# fournit la liste des décompositions binaires
# des nombres de 0 à n-1
def enumbase2 (n):
return [normalise(i,len(binaire(n))-1) for i in range(0,n)]
# retourne la liste de toutes les parties de l'ensemble L (implémenté comme liste)
def parties (L):
k=1
n=len(L)
for i in range(0,n):# calcule le cardinal de l'ensemble des parties de n
k=k*2
FoncCar=enumbase2(k) # toutes les fonctions caractéristiques
m=len(FoncCar)
Parties=[]
for i in range (0,m):
F=FoncCar[i]
P=[L[j] for j in range(0,len(F)) if F[j]!=0 ]
Parties.append(P)
return Parties
# retourne la liste de toutes les parties à p éléments de L
def partiesp (L,p):
return [x for x in parties(L) if len(x)==p]
# calcule la somme des éléments d'une liste
def somme (L):
def add(x,y): return x+y
return reduce(add,L,0)
# recherche les possibilités d'obtenir la somme k
# avec p termes pris dans la liste donnée au début
def recherche (p,k):
L=partiesp(ListeNombres,p)
Sol=[x for x in L if somme(x)==k]
print Sol
def main():
# effectue la recherche que vous donnez en exemple
recherche(3,10)
if __name__ == '__main__':
main() |
Partager