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() |
