Discussion :

[chateau_dur]

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 !

[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 ?

[j.p.mignot]

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

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

[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 ?

[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

[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

[Jean-Marc.Bourguet]

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.

[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 :

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

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

Merci a vous tous et particulierement a Monsieur Bourguet !

[2Eurocents]

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 :

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

[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

[Jean-Marc.Bourguet]

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.

[Trap D]

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

Code :

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

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.

[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

[chateau_dur]

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

Code :

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

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.

[random]

en ce qui concerne la somme
je pense à
(2^(n-1))*n*(n+1)/2 soit
(2^(n-2))*n*(n+1)

[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

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