Discussion :

[adabeno]

Bonjour,
Je cherche un algo qui va m'aider à trouver toutes les sommes possible pour un nombre.
Par exemple:
1+1+1+1=4
1+1+2=4
1+3=4
2+2=4
...

Merci d'avance.

[progfou]

Je ne vois pas bien l'utilité, mais bon, un principe (naïf, car trouvé en 30 secondes) :

• Tu décomposes en somme de 1
• Chaque 1 constitue la feuille extrème d'un arbre
• tu additionnes chaque feuille avec l'une des autres, tu as un premier niveau avec des sommes de 2
• tu recommences en prenant ce second niveau avec le précédent et lui-même, tu as les sommes des 1 et des 2
• etc. => algo récursif

Extrèmement coûteux en terme de calculs, mais dans le principe, ça doit à peu près faire ce que tu veux.

[10_GOTO_10]

Ca dépend: est-ce que l'ordre des termes a une importance ? Est-ce que "3 + 1" et "1 + 3" constituent deux réponses ou une seule ?

L'algo de progfou va donner les deux réponses distinctes

[progfou]

Ah ben oui, j'ai dit "naïf" .
Mais à priori ça fonctionne.

[Trap D]

On peut peut-être le faire en récursif quitte à péter la pile rapidement

Code :

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

1
2
3
4
trouver toutes les sommes formant n c'est
	trouver toutes les sommes formant n-1
	ajouter 1 à toutes les combinaisons obtenues
	faire le tri pour éliminer les doublons

exemple

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
trouver toutes les sommes formant 4
	trouver toutes les sommes formant 3
		trouver toutes les sommes formant 2
			trouver toutes les sommes formant 1
			renvoie ((1))
		((1)) recu
		on ajoute 1 de toutes les façons différentes 
			(1+1) et (1,1) donc ((2), (1 ,1))
		pas de doublon
		renvoie ((2), (1,1))
	((2),(1,1)) recu
	on ajoute 1 de toutes les façons différentes
		((3) ,(2,1), (1,2) ,(1,1,1), (1,1,1) (on ajoute 1 entre les 1 et 1 en fin de liste)
	on vire le doublon
	renvoie ((3),(2,1),(1,2),(1,1,1))
((3),(2,1),(1,2),(1,1,1)) reçu
on ajoute 1 de toutes les façons différentes
	(4) (3,1) (2,2), (2,1,1), (2,1,1), (2,2), (1,3),(1,1,2) (1,2,1) ,(2,1,1), (1,2,1), (1,1,2), (1,1,1,1), (1,1,1,1),(1,1,1,1),
on vire les doublons
((4),(3,1),(2,2),(2,1,1),(1,3),(1,2,1),(1,1,2),(1,1,1,1))
renvoie ((4),(3,1),(2,2),(2,1,1),(1,3),(1,2,1),(1,1,2),(1,1,1,1))

Le nettoyage des doublons peut-être plus puissant si on décide que l'ordre n'a pas d'importance.
J'ai laissé les nombres seuls, ça ne ma paraît pas illogique.