Discussion :

[gronaze]

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+

[davly]

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.

[prgasp77]

Je verrais plutôt une solution récursive :

Si on note l'ensemble des solutions du problème, alors on peut le décomposer de la sorte :


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,

[gronaze]

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 ?

[prgasp77]

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,

[gronaze]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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
	v1	v2	v3	v4	v5	v6	v7	vk-1	vk
u0									15
u1								1	14
u2								2	13
u3							1	1	13
u4								3	12
u5							1	2	12
u6						1	1	1	12
u7								4	11
u8							1	3	11
u9							2	2	11
u10						1	1	2	11
u11					1	1	1	1	11
u12								5	10
u13							1	4	10
u14							2	3	10
u15						1	1	3	10
u16					1	1	1	2	10
u17					1	1	1	1	10
u18								6	9
u19							1	5	9
u20							2	4	9
u21						1	1	4	9
u22							3	3	9
u23						1	2	3	9
u24					1	1	1	3	9
u25						2	2	2	9
u26					1	1	2	2	9
u27				1	1	1	1	2	9
u28			1	1	1	1	1	1	9

...

J'ai du mal à définir le critère de recherche de minimum afin de valider le décrémentation du terme Vk.