Comment trouver la somme de n cartes?? Résolu/Fermé

Question

Bonjour,

Ma question est simple, mais pourtant je n'arrive pas à la mettre en pratique.

Supposons 3 cartes:

C1 = 1
C2 = 2
C3 = 3

Comment mettre en place des boucles afin de trouver toutes les combinaisons possibles?
En sortie j'aurais donc:

// combinaison de 3 cartes
C1 + C2 + C3 = 6

// combinaisons de 2 cartes
C1 + C2 = 3
C1 + C3 = 4
C2 + C3 = 5

// combinaisons d'1 carte
C1 = 1
C2 = 2
C3 = 3

J'ai volontairement omis les doublons (C1 + C2 = C2 + C1)

Voila, j'éspere que c'est clair et qu'une personne serra en mesure de m'aider

Merci

Sacabouffe · Answer

Salut BK-93

Soient n cartes et cherchons toutes les combinaisons possibles de p cartes.

Alors tu obtiens toutes les combinaisons possibles en bouclant de cette manière (i1, i2, ..., ip sont des indices). i(p-1) c'est le p-1 ième indice, pas moyen de le noter autrement ici...


for i1=1:n-p+1
for i2=i1+1:n-p+2
for i3=i2+1:n-p+3
...
...
...
for ip=i(p-1)+1:n

La somme

end
...
...
...
end
end
end


Par contre deux combinaisons totalement différentes peuvent donner la même somme. Exemple pour des combinaisons de 2 cartes choisies parmi 4 (1,2,3,4):
1+4=2+3
Voilà, c'est ça que tu voulais ou je suis à côté de la plaque?

BK-93 · Answer

Pour commencer, merci  Sacabouffe d'avoir pris le temps de répondre.

Je ne comprend pas trop la méthode que tu as utilisé, si je crois conprendre tu utilise une double boucle par combinaisons?

En fait j'ai donné l'exemple de 3 cartes pour avoir une base, mais il s'avère que l'on peut se retrouver avec 1,2 ou 10 cartes

Supposons:

Je possède une carte en main: [10]

Grâce à cette carte, je peux prendre autant de cartes disponnible sur le tapis tant que le total fait 10

Sur la tapis j'ai:

[1] [2] [3] [4] [5]

Je peux donc prendre:

[10] = [1] [2] [3] [4]
[10] = [1] [4] [5]
[10] = [2] [3] [5]

Si ma carte en main avait été [7] et que celles sur le tapis reste les mêmes:

[7] = [1] [2] [4]
[7] = [4] [3]
[7] = [5] [2]

La méthode, que je pense, la plus simple pour trouver les bonnes combinaisons et de toutes les trouver puis de sortir celles que je veux, en l'occurence celles qui font 7 quand j'ai un [7] ect...

A moins d'avoir une autre solution, je suis toujours la-dessus.

Merci

PS:  Sacabouffe, si tu as le temps de mieux m'expliquer ton idée, je suis preneur

Sacabouffe · Answer

Je vais essayer de t'expliquer mes boucles mais comme ça par écrit c'est pas facile, facile...

Sacabouffe · Answer

J'y vais.
On va prendre des chiffres pour que ce soit plus simple parce que se trimbaler des lettres ça va être la misère, donc par exemple 5 cartes, et chercher toutes les combinaisons possibles de 3 cartes par exemple. Si on fait le lien avec ce que j'ai écrit avant : n=5 et p=3.

Par contre pour l'instant on va pas tenir compte de la valeur des cartes sinon ça rajoute des chiffres et c'est le bordel.
Et fonctionner de cette manière c'est justifié puisqu'au départ tu veux juste un moyen de connaître toutes les combinaisons de cartes possibles sans répéter plusieurs fois les mêmes et seulement ensuite voir lesquelles ont une somme égale à celle que tu t'es fixée au départ.
Donc appelons les cartes : A, B, C, D, E 

On commence par fixer la première carte (le i1 qui allait de 1 à n-p+1). Tu vas voir pourquoi le n-p+1...

Première carte on prend A

En rajoutant une deuxième carte on obtient:
AB
AC
AD
AE

Puis à chaque combinaison il faut en rajouter une troisième :

ABC
ABD
ABE

ACD
ACE

ADE


Et c'est tout, en ajoutant une carte à la combinaison AE juste avant on retombe obligatoirement sur une déjà faite.

Donc tu vois que pour i1=1 (première carte=A), le i2 (choix de la deuxième carte) va de i1+1 à 4 (cartes B,C,D) et le i3 (choix de la troisième carte) va de i2+1 à 5 (cartes C,D,E mais ça dépend du choix de la deuxième)


Première carte on prend B
En rajoutant une deuxième carte (sans A sinon on retombera obligatoirement sur une combinaison déjà faite) on obtient :
BC
BD
BE

Puis à chaque combinaison il faut en rajouter une troisième (sans refaire celles déjà faites) :

BCD
BCE

BDE


Et c'est tout, en ajoutant une carte à la combinaison BE juste avant on retombe obligatoirement sur une déjà faite.

Donc tu vois que pour i1=2 (première carte=B), le i2 (choix de la deuxième carte) va de i1+1 à 4 (cartes C,D) et le i3 (choix de la troisième carte) va de i2+1 à 5 (cartes D,E mais ça dépend du choix de la deuxième)

Première carte on prend C
En rajoutant une deuxième carte (sans A ni B sinon on retombera obligatoirement sur une combinaison déjà faire) on obtient :
CD
CE

Puis à chaque combinaison il faut en rajouter une troisième (sans refaire celles déjà faites) :
CDE

Et c'est tout, en ajoutant une carte à la combinaison CE juste avant on retombe obligatoirement sur une déjà faite.

Donc tu vois que pour i1=3 (première carte=C), le i2 (choix de la deuxième carte) va de i1+1 à 4 (cartes D seulement) et le i3 (choix de la troisième carte) va de i2+1 à 5 (carte E seulement)

Et enfin tu remarqueras que si on essaie maintenant de faire une combinaison en partant de D ou de E on retombera obligatoirement sur une combinaison déjà faite.

Morale de l'hitoire :

Pour i1 variant de 1 à 3 (choix de la première carte)
Pour i2 variant de i1+1 à 4 (choix de la deuxième carte)
Pour i3 variant de i2+1 à 5 (choix de la troisième carte)
On obtient toutes les combinaisons possibles...

Et après tu peux faire les sommes pour toutes les combinaisons que t'as obtenues.

OUI je sais :-D les combinatoires c'est prise de tête...
Mais si t'arrives à voir le truc, la généralisation pour des combinaisons de p cartes choisies parmi n t'apparaitra peut-être plus clairement.

Essaie de méditer un peu là-dessus et s'il y a des trucs que tu comprends pas dis-moi.
Par contre là c'est juste pour des combinaisons de 3 cartes donc après faut faire la même chose pour des combinaisons de 2 ou de 4 (1 et 5 ça va c'est pas trop fatiguant...)

Je t'avais dit... pas facile d'expliquer correctement par écrit.
J'espère aussi que j'ai pas raconté trop de conneries et ni laissé trop de coquilles dans tout le foutoir juste au-dessus.

PS : Si t'es prêt à accepter éventuellement des boucles qui te sortiront plusieurs fois la même combinaison (du genre ABC, ACB BAC, BCA, CAB, CBA) ce sera un tout petit peu plus simple...

BK-93 · Answer

Bonjour,

C'est marrant, mais chaque fois que je lis ta réponse je me dis, c'est ça !!! et puis au moment de le mettre en pratique...je bloque, je ne comprend plus rien.

Ce qui me fait défaut, c'est la construction des boucles...je ne vois vraiment pas comment traduire en programmation ce que tu me dis?

j'avais déjà pensé à cette histoire de carte + 1, mais je n'ai jamais été capable de la reproduire via des boucles.

Je te met le début de mon code de test, c'est de l'Action Script car il permet une plus grand maniabilité au niveau des tableaux:

var Tableau = new Array ();
Tableau[0] = {Nom:"C1", Valeur:"1"};
Tableau[1] = {Nom:"C2", Valeur:"2"};
Tableau[2] = {Nom:"C3", Valeur:"3"};

trace ("Les cartes disponibles sont:");
for (i = 0; i < Tableau.length; i++) {
	trace (Tableau[i].Nom+" - Valeur: "+Tableau[i].Valeur);
}

Voila, pour sortir les combinaisons de 1 carte c'est pas vraiment sorcier:

// Combinaisons 1 Carte
trace ("Combinaisons 1 Carte:");
for (i = 0; i < Tableau.length ; i++) {
	trace (Tableau[i].Nom);
}

Mais pour la suite... :-~

Merci encore.

PS: Ca ne me dérange pas de resortir les même combinaisons

Sacabouffe · Answer

Salut BK-93
Pour le moment je vais pas pouvoir t'aider, désolé... Je te reprends ce soir ou demain.
A plus tard

Sacabouffe · Answer

Salut BK-93
Alors voilà... Action Script : jamais entendu parler... Oui je sais... faudrait que je sorte de ma grotte. Quand j'aurai le temps... :-D
Donc je vais essayer de faire avec la syntaxe que j'ai comprise en lisant ton petit bout de programme et Wikipédia, tu corrigeras les fautes.

// Combinaisons 2 Cartes
trace ("Combinaisons 2 Cartes:");
for (i = 0; i < Tableau.length-1; i++) {
for (j = i+1; j < Tableau.length; j++) {
trace (Tableau[i].Nom + Tableau[j].Nom);
} 
}

Normalement ça t'affichera toutes les combinaisons possibles de 2 cartes choisies parmi 3.

Mais bon là on voit pas trop ce qui se passe donc je te fais le même avec les combinaisons de 3 cartes choisies parmi 5 (de valeurs 2,5,7,4,11 mais pas d'importance ici puisqu'on calcule pas les sommes) 

var Tableau = new Array ();
Tableau[0] = {Nom:"C1", Valeur:"2"};
Tableau[1] = {Nom:"C2", Valeur:"5"};
Tableau[2] = {Nom:"C3", Valeur:"7"}; 
Tableau[3] = {Nom:"C4", Valeur:"4"};
Tableau[4] = {Nom:"C5", Valeur:"11"}; 

// Combinaisons 3 Cartes parmi 5
trace ("Combinaisons 3 Cartes parmi 5 : ");
for (i = 0; i < Tableau.length-2; i++) {
for (j = i+1; j < Tableau.length-1; j++) {
for (k = j+1; k < Tableau.length; k++) {
trace (Tableau[i].Nom + Tableau[j].Nom + Tableau[k].Nom);
} 
}
}

Bon après si tu veux effectivement écrire le programme qui cherche toutes les combinaisons possibles et qui calcule les sommes, le mieux pour gagner un peu de mémoire (quoiqu'avec même 10 cartes c'est pas la mer à boire : 1023 combinaisons) c'est de calculer les sommes au fur et à mesure plutôt que de stocker toutes les combinaisons et ensuite de calculer les sommes.
Pour gagner du temps tu peux aussi virer dès le départ les cartes qui ont une valeur supérieure à celle que "t'as dans les mains".
Etc, etc...

Si t'as encore des problèmes dis-moi.
A plus.

BK-93 · Answer

Merci  Sacabouffe,

C'est exactement ce que j'avais en tête, mais la ou ça bloquait vraiment était dans le N cartes, c'est à dire combien de boucles.

A moins de toutes les taper jusqu'a 10...je voulais faire des boucles automatiques.

Mais je pense que je m'y prend mal...il y a un autre moyen (j'en suis sur !!) et je vais plutot chercher dans cette direction, sinon cette méthode reste applicable (à condition de ne pas dépasser 10 cartes sur le tapis)

Dés que j'ai fait une petite application qui fonctionne, je t'en ferrais parvenir un exemplaire afin que tu puisse admirer le résultat de tes conseils !!

Merci encore

Sacabouffe · Answer

De rien BK-93
Effectivement je veux bien voir ce que ça donne au final.

J'aurais peut-être dû le dire avant (j'y ai pas pensé, désolé...), mais peut-être que tu t'en es rendu compte. En fait pour p cartes choisies parmi n, toutes les boucles emboîtées que j'ai écrites s'écrivent de manière plus compacte (mais pas sûr que ce soit exploitable dans un code) :
1 <= i1 < i2 < ... < ip <= n

Voilà, de mon côté si j'ai d'autres idées pour simplifier le truc je te préviens parce que c'est vrai que tout taper c'est un peu lourdingue.
A plus

Sacabouffe · Answer

J'ai quand même jeté un œil sous Google et je t'ai trouvé ça : https://forum.hardware.fr/hfr/Programmation/challenge-lister-elements-sujet_11138_1.htm

Un type (le penseur fou) a écrit un tout petit truc en VB pour énumérer toutes les parties d'un ensemble. Mais évidemment il y a de la récursivité là-dessous.

Dis-moi si ça t'aide dans ta quête...

Scalpweb · Answer

Pour réussir à calculer cette somme pour n cartes, je pense qu'il faut utiliser une fonction récursive. Ca donnerai quelque chose comme :

function Combinaison(int i, int max, int nbCartes, int maxCartes)
{
   for(r = i+1; r<max; r++)
   {
      if(nbCartes<maxCartes)
         return r+Combinaison(r, max, nbCartes+1, maxCartes);
      else
         return r;
   }
}

Scalpweb · Answer

Autant pour moi, voici une fonction  affichant la liste des valeurs possibles :

function Combinaison(int i, int max, int nbCartes, int maxCartes, int cumul)
{
for(r = i+1; r<max; r++)
{
if(nbCartes<maxCartes)
   return Combinaison(r, max, nbCartes+1, maxCartes, cumul+r);
else
   trace(cumul+r);
}
}


Et tu appelles cette fonction avec une ligne du genre :
Combinaison(-1,10,0,10,0);

Note : max et maxCartes sont les mêmes si pour 10 cartes le score maximum est de 10.

BK-93 · Answer

Bonjour,

Merci Sacabouffe pour le lien, effectivement j'ai testé le programme du "Penseur Fou" sous excell et c'est exactement ce que je veux !!!!

Il ne me reste plus qu'a traduire le VB en ActionScript (ou Java au pire...allez même en C) c'est pour cette raison que je vais essayer d'entrer en contatc avec lui afin qu'il m'expique la procédure !!

Merci aussi à  Scalpweb, j'ai corrigé ton programme (il manquait des { }...) mais je ne comprend pas trop ce qu'il fait ???

//---- PROG

function Combinaison(i, max, nbCartes, maxCartes, cumul) {
	for(r = i+1; r < max; r++) {
		if(nbCartes < maxCartes) {
			trace("Result: R:"+r+" Max:"+max+" NbCartes:"+nbCartes+1+" MaxCartes:"+maxCartes+" Cumul+R:"+cumul+r);
		} else {
			trace("_Cumul+R: "+cumul+r);
		}
	}
}

Combinaison(-1,10,0,10,0); 

PROG ---- //

Encore merci, je continue de chercher !!!

BK-93 · Answer

OK !!

Encore merci Sacabouffe, je vais donc poster un nouveau message pour la traduction de ce code.

Je ferme donc le sujet !!

Merci

Comment trouver la somme de n cartes??

14 réponses

Discussions similaires