Algorithme Somme

Version imprimable

04/12/2005, 01h19
chateau_dur

Algorithme Somme

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...

Merci !
04/12/2005, 11h32
Trap D

Je ne connais pas cet algo, mais j'ai l'impresson il ressemble un peu à l'algo qui consiste à obtenir toutes les combinaisons de n nombres, non ?

Ce petit code récurssif devrait sous reserve de vérification repondre au probleme.
Code:

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 void MUL ( AnsiString S, AnsiString D[] ) { // recherche d'1 'antériorité' int i = -1; do { i++; } while (( D[i] !="" ) && ( D[i] != S)); if ( D[i] == S ) return;// si non il y a de la redondance D[i] = S; // on ajoute ce string à ceux traités AnsiString A = ""; // uniquement pour reporter la multiplication consernée long U = 1; // résultat de la multiplication for ( short j=0; j < S.Length(); j++) { U *= (int ( S[j+1])-48); // valeur de la X A = A + S[j+1] + " * "; // commentaire sur la X en cours } A.Delete(A.Length()-2,3); // suppression du dernier ' * ' Form1->ListBox1->Items->Add(A + " = " + IntToStr(U)); // ajout du résultat dans 1 list box for ( i=0; i < S.Length(); i++) { // ici commence la récurence à partir du string courrant. AnsiString An=""; for ( short j=0; j < S.Length(); j++) if (j != i ) An = An + S[j+1]; MUL(An,D); } } void __fastcall TForm1::Button1Click(TObject *Sender) { int n = Edit1->Text.Length(); // entrer ici 1 12 123 1234 12345 .. int m=1; for (short j=1; j <= n; j++) m *= 2; // 2^n AnsiString *A = new AnsiString[m]; // en fait 2^n - 1 suffirait car on elimine l'ensemble vide for ( int j =0; j < m; j++ ) A[j] =""; // afin d'initialiser les AnsiString ListBox1->Clear(); MUL(Edit1->Text,A); delete [] A; }
je n'ai pas trouvé, mais pas vraiment cherché non plus, un moyen d'éviter le test
int i = -1;
do
{
i++;
} while (( D[i] !="" ) && ( D[i] != S));
if ( D[i] == S ) return;// si non il y a de la redondance
On doit sûrement y arriver!

Bien entendu, afin de répondre à une critique comme quoi la réponse était en C++, je propose ici un moyen d'atteindre l'objectif. Il serait absolument evident d'en faire un equivalant C, VBC++, Delphi, (Turbo)Pascal, fortran, ...
Il m'a semblé plus facile et + parlant de donner 1 petit code en C (++ ici ne represente rien) avec quelques comments.
Par contre ce petit soft a été écrit 'à la volée' => peut-être des problèmes de capacité de codage si n devient trop grand & optimisation non garantie

04/12/2005, 15h18
Arvulis

Cet Algo me dit quelquechose mais impossible de me rappeler.

Cependant, je crois qu'il n'y a pas d iteration (pas de for).

Tout doit pouvoir se faire avec des tests... mais comment ?
je me creuse la tete mai c pas evident.

Peut etre faut il voir une suite recurente ?
04/12/2005, 19h05
chateau_dur

Premierement, Merci j.p.mignot ! Ton algo est interessant mais comme le disait Arvulis, les boucles sont inutiles, il existe une solution recursive pure, c'est assez delicat on dirait.

Je pensais en plus a stocker les resu dans une Hashmap (je vais le coder en Java) ou la clef serais le nombre de base (somme de 4, donc la clef est 4) et les valeurs toutes les possiblites de cette somme.

L'algo ne depasse pas les 15 instructions a mon avis, mais ca fait un moment que je cherche et cest assez delicat. Ne serait-ce que de considerer la somme sous une espece de polynome :

4 + 3 + 2 + 1 on decrement le le degre faible a chaque appelle recursif :

4 + 3 + 2 + 0

4 + 3 + 1 + 0 etc... Cette technique ne donne pas toutes les solutions !

Franchement je ne sais pu trop comment aborder le probleme.

Merci de votre aide en tout cas, et si vous avec l'idee de genie pdt la soiree, n'hesitez pas a poster ;)
04/12/2005, 19h37
Wavyx

je dis ça comme ça (mais j'ai un peu de mal a saisir ton énoncé)
si tu décrémentais le "degré fort - 1" plutot ?
4 + 3 + 2 + 1
4 + 2 + 1

etc.. en imposant que le nombre i-1 < nombre i
enfin je suis un peu brouillon là :S
04/12/2005, 20h31
Jean-Marc.Bourguet

Re: Algorithme Somme

Citation:

Envoyé par chateau_dur

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

Je ne suis pas sûr de comprendre. Est-ce que tu cherches les résultats des sommes? Ou bien un algo pour te donner toutes les expressions?

Dans le premier cas, c'est simplement les nombres de 1 à n*(n+1)/2. La démonstration se fait simplement par récurrence.

Dans le second cas, je vais simplement changer l'ordre de tes résultats:
1, 2 2+1, 3 3+1 3+2 3+2+1, 4 4+1 4+2 4+2+1 4+3 4+3+1 4+3+2 4+3+2+1
et la manière de les générer devrait te sauter aux yeux.
04/12/2005, 20h54
chateau_dur

Je cherche un algo me donnant toutes les expressions et toutes les sommes en fait.

Je refais un exemple plus clair, car je ne l'ai pas ete vraiment en effet. Alors :

on somme 3, je vais donc stocker la fois la somme et l'expression

3 + 2 + 1 = 6
3 + 2 = 5
3 + 1 = 4
2 + 1 = 3
3, 2, et 1.

Et je suis un gros boulet car oui :

Citation:

Envoyé par Jean-Marc.Bourguet

Dans le premier cas, c'est simplement les nombres de 1 à n*(n+1)/2. La démonstration se fait simplement par récurrence.

Et j'y avais trop pas pense :oops: :? :wink:

Et merci beaucoup, j'ai limite honte haha :D en tout cas j'adore ce forum, on a toujours les bonnes reponses :wink:

Merci a vous tous et particulierement a Monsieur Bourguet !

Sinon, pour le cas où les valeurs à combiner dans l'expression ne sont pas des valeurs consécutives, mais des valeurs connue, dans une liste, je vous propose l'algorithme du bourrin ... pas récursif du tout et qui donne toutes les solutions ...

On stocke tous les éléments possibles à utiliser dans les sommes dans un tableau T, indicé de 0 à n.

On fait ensuite une boucle indicée de 0 à ((n+1)**2) - 1.

A chaque itération de la boucle, c'est une nouvelle somme.

Les éléments à prendre en compte dans cette somme sont ceux dont l'indice dans le tableau T sert à composer la valeur de l'indice de boucle courant.

En voici une petite implémentation en Perl, juste pour voir ...
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #!perl use strict; use warnings; my @tab=qw(1 2 3 4); for (my $i=0 ; $i < (2 ** ($#tab+1)); $i++) { my @somme = (); for (my $test = 0 ; $test < $#tab+1 ; $test++) { if (($i & (1 << $test)) != 0) { push (@somme, $tab[$test]); } } $, = ", "; print "Composantes : "; print @somme; print "\n"; }
En gros, les composants de la somme sont indicés par leur puissance de 2 ...

04/12/2005, 21h46
chateau_dur

Je reviens faire un tour ici car, si jppllique la suite n*(n+1)/2 le probleme est que je ne vais pas avoir tous les nombres...

si on reprend toujours et encore le chiffre 3 :

3 + 2 + 1 = 6
3 + 2 = 5
3 + 1 = 4
2 + 1 = 3
3, 2, et 1.

Je ne vois pas comment obtenir ceux notes en vert :(

Si quelqu'un a une idee, je suis prenneur !

Merci
04/12/2005, 22h08
Jean-Marc.Bourguet

Citation:

Envoyé par chateau_dur

si on reprend toujours et encore le chiffre 3 :

3 + 2 + 1 = 6
3 + 2 = 5
3 + 1 = 4
2 + 1 = 3
3, 2, et 1.

Je ne vois pas comment obtenir ceux notes en vert :(

Tous les nombres entre 1 et n*(n+1)/2 sont présents, pas uniquement ceux de la forme n*(n+1)/2.

J'ai une idée avec une file, l'algo serait de ce type :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
i <- 1
enfiler 0 // c'est une valeur indiquant qu'il faut arréter de défiler
tant que i <= n faire
  enfiler i
  k <- défiler()
  tant que k <> 0 faire
    enfiler k
    enfiler k + i
  fin tant que
  enfiler 0
  i < i+1
fin tant que

A la fin, dans ta file tu as toutes les valeurs possibles.

04/12/2005, 22h27
chateau_dur

En effet cette suite donne bien tous les resultats, mais les combinaisons sont assez dures a recuperer.

Je ne peux pas voir la combinaison 2+3 et 1+3 intuitivement et recursivement, les resultats oui, mais lexpression non :cry:

Citation:
Envoyé par Trap D
J'ai une idée avec une file, l'algo serait de ce type :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 i <- 1 enfiler 0 // c'est une valeur indiquant qu'il faut arréter de défiler tant que i <= n faire enfiler i k <- défiler() tant que k <> 0 faire enfiler k enfiler k + i fin tant que enfiler 0 i < i+1 fin tant que
A la fin, dans ta file tu as toutes les valeurs possibles.
En effet, mais je dois le passer en recursif ce probleme, en iteratif cest assez direct egalement. :cry:

06/12/2005, 14h48
random

en ce qui concerne la somme
je pense à
(2^(n-1))*n*(n+1)/2 soit
(2^(n-2))*n*(n+1)
06/12/2005, 16h44
10_GOTO_10

La solution est bien plus simple: pour une somme, chaque nombre y est ou n'y est pas. Donc le nombre de combinaisons est 2^n.

Pour chaque nombre I de 0 à 2^n - 1
Exprimer I en binaire
pour chaque bit b de I
si b = 1 ajouter le nombre correspondant dans la somme
fin pour
fin pour

exemple:
I en binaire Somme
000 Rien
001 1
010 2
011 2 + 1
100 3
101 3 + 1
110 3 + 2
111 3 + 2 + 1
07/12/2005, 07h32
chateau_dur

Merci a tous, j'ai enfin fini par trouver la solution pour avoir les combinaisons recursivement, c'est assez chaud a trouver... Perso j'aurais pas trouver sans google :)

La solution est la

Pour ce a qui ca pourrait servir... Probleme de permutation, combinaison, ordre, recursif, java. (avec ca, le mec qui fait une recherche devrait tomber sur le topic)

Edit : jviens de voir ton post GOTO, en effet l'approche par tableau de booleen est vraiment pratique, recursivement c'est traite avec 2 appels recursifs.