Version imprimable
Bonjour,
Existe-t-il un algo qui permet de calculer le nombre de décomposition additives possible sur K termes d'un nombre N, ou chaque terme est unique, par exemple:
N = 9, K = 3; d'ou N = a + b + c
cas 1: 9 = 1 + 2 + 6
cas 2: 9 = 1 + 3 + 5
cas 3: 9 = 2 + 3 + 4
Dans ce cas, il n'y a que 3 possibilités.
Merci pour vos réponses,
A+
Bonjour,
Vu comment tu présente le problème, tu pourrais toi même faire cet algo..
tu dois faire une maxi boucle..
1ere boucle
tu commencerai a faire la somme des nombres succesif jusqu'à K-1, puis le Keme prendrai la valeur pour compléter la somme avec les conditions suivantes:
- la somme des K-1 premiers termes est inférieur à N, et que la valeur pour K est inférieur au K-1 eme valeur.
dans ton exemple, cas 1: 9 = 1 + 2 + 6
on a bien 1+2<9 (somme K-1 element < N)
et 6>2 ( Ke > K-1e)
ensuite il faut que tu t'arrete à K-2 et que tu fasse les même condition.
et si tu suis la logique, je pense que avec ça t'as une bonne partie de l'algo à implémenter.
Je verrais plutôt une solution récursive :
Si on note https://chart.googleapis.com/chart?cht=tx&chl=E_{k,n} l'ensemble des solutions du problème, alors on peut le décomposer de la sorte :
https://chart.googleapis.com/chart?c...}\,E_{k-i,n-1}
Ton problème se simplifie donc beaucoup : il te faut savoir repérer que les cas dégénérés (pour quels couple (k,n) n'y a-t-il pas de solution ?) et les cas simples (pour quels (k,n) y a-t-il une solution unique ?).
Cdlt,
Merci pour vos réponses.
@Davly, c'est effectivement la solution que je commençais à imaginer, mais j'ai un peu l'impression que c'est de la force brute...
J'aurais voulu savoir si il n'y avait un système d'équations pour résoudre le problème.
@prgasp77, je crois que mes cours de math remontent à trop longtemps... en fait tu proposes de formaliser l'écriture de chaque solution, mais je ne vois pas comment connaitre réellement chaque couple de solution ?
Je ne fais que mettre en avant le fait que si tu sais résoudre ton problème pour n, alors tu sais le résoudre pour n+1. Sais-tu le résoudre pour 1 ? Donc aussi pour 2, pour 3 ... Pour plus de renseignements sur la programmation récursive, consulter par exemple la page Algorithme récursif - Wikipedia.
Cdlt,
Merci prgasp je sais ce qu'est une récursion, j'ai juste du mal à la formaliser algorithmiquement...
cf, exmple suivant ou le reste vaut 15 et le nombre de termes et de 9.
...Code:
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
J'ai du mal à définir le critère de recherche de minimum afin de valider le décrémentation du terme Vk.
Salut,
Je crois qu'il y a la solution à ton problème sur wikipédia : Partition d'un entier il y est question aussi bien de la construction de ces partitions que de de leur dénombrement...
Tu trouvera également un post sur le forum de developpez.com : Décomposition en somme de n entiers
Parfait Bertry, c'est exactement ce qu'il me fallait... Je me disais bien que je ne devais pas être le premier à me poser cette question ! :ccool:
==> RESOLU