Cherche nom Algorithme Somme

[Anonyme]

Salut !

Je voudrais simplement savoir si quelqu'un connait l'algorithme recursif ou le Nom de l'algorithme qui consiste a faire ce genre de sommes :

Somme de 3 :
resultats : 3+2+1, 3+2, 3+1, 2+1, 3, 2, 1.

En gros, il me faut tous les resultats possibles avec pour maximum la somme de 1 a 3 (ou N si on considere le truc en algorithme).

Il me semblait que cette somme etait en fait la somme de Zdersky mais le bonhomme n'existe pas sur Internet donc je soupconne l'erreur de nom...

[Chimerade]

Ben, je ne sais pas si l'algorithme qui suit est suffisamment difficile pour recevoir un nom !

Les différentes possibilités de ta somme sont :



Les sont indépendants et prennent chacun deux valeurs possibles : 0 ou 1. Donc le nombre des termes de ta somme est . Si tu exclus la somme vide, il suffit d'ôter le cas (0,0,...,0), et ça te fait cas !

Donc comme algorithme, je te propose de faire varier un indice l de 0 à (ou de 1 à , si tu veux exclure le cas de la somme vide) et pour chaque valeur de l, d'écrire l en binaire, ce qui revient à le décomposer en somme de puissances de 2 successives :



Puis de prendre les ainsi trouvés pour calculer l'expression ci-dessus.

P.S. Je sais que cet algorithme n'est pas récursif ! C'est exprès ; la récursivité est la plus grande amie des programmeurs paresseux, mais c'est aussi la plus grande ennemie des performances ; alors, moi j'aime pas !

[GaussFutur]

Ce que tu demande c'est très proche de l'ensemble des parties d'un ensemble !!!

Ta as (n;k) nombres de somme à k termes pour n élements pris au début !
toi c'est trois donc tu as (3;k).... PS (n;k) c'est la combinaison !!!

Et on a la somme de toutes les sommes engendrées qui est de 2^n-1

Voilà m'sieur !!