[RESOLU][C++] faire toutes les sommes possibles de i entiers

Bon voilà, j’appelle la grande force de la zone, pour ce problème.
Je ne vous cache pas que c’est pour un projet (scolaire), mais ça fait plusieurs jours que j’y réfléchi et je n’y arrive pas. Voilà le problème:

je dois effectuer toutes les sommes possibles avec des combinaisons de 3 entiers compris entre 1 et 9 parmis X éléments (9 normalement, mais avec un algo ça devrait facilement s’adapter à d’autres quantités). En effet je dois vérifier que leur somme fasse 15. Alors je peux prendre le problème à l’envers, et vérifier que tout les éléments à vérifier (qui se trouvent dans un tableau) sont dans un liste (j’ai listé 7 combinaisons possibles pour arriver à 15 avec 3 chiffres).
Mais voilà, je trouve ça laid, pas beau, inesthétique et c’est pas du tout ce que je veux :cry: . Je me doute qu’il faut des boucles (for probablement) imbriquées, mais ça s’arrête là.

Je sais qu’il y a des grand manitous ici, et si vous pouviez me mettre sur la bonne piste (je ne demande pas un algo tout prêt même si je ne serais pas contre :P), ça serait sympa, parce que j’ai du mal là :slight_smile: .

Merci :crying:

Je dirais un truc comme ça ?

Ca a l’air d’y ressembler, sauf que moi je ne dois utiliser que 3 éléments. Ca a déjà l’air complexe sans cette contrainte :/.
Enfin merci pour le lien :), y’a de quoi faire j’ai l’impression.

Je pencherai pour ce un fonctionnement du type de celui de Prolog (je ne connais que partiellement le fonctionnement de ce dernier donc si je dis de la merd%& faites le moi savoir!) alias un fonctionnement bourrin amélioré. Pour cela, on va construire une structure arborescente en implémentant un « backtracking/forward checking/look ahead » (le nom diffère suivant la littérature) avec l’aide d’un fonctionnement « fail-first ». Oui je sais ca fait deux mots compliqués mais c’est en fait simple.

Construire un arbre de solutions c’est aller de manière bourrine dans ton ensemble de solutions. Tester toutes les possibilités et voir si chacune d’elles marche ou pas. On est d’accord, c’est moche, même si dans le cas [1,9] ca ne pose aucun problème vu la vitesse actuelle des machines… mais c’est moche alors pour améliorer ca on va ajouter un brin « d’intelligence ».

L’idée du backtracking, c’est de revenir à chaque fois que tu trouves une solution pourrite sur un état stable en évitant ainsi d’aller plus loin. Tu as choisi de faire « 9 + 9 » et ca foire donc tu reviens a « 9 + » sans passer par les cases « 9 + 9 + 1 », « 9 + 9 + 2 » etc. on vient pas d’inventer la roue, c’est évident mon cher Dawson, mais on vient tout de même d’ajouter une certaine logique et de s’éviter une bonne quantité de tests.

En fait, là ou on ajoute vraiment de la logique c’est dans le fail-first. L’idée du fail-first c’est justement de parcourir un ensemble de solutions et de tester en priorité les cas qui vont justement foirer. Si tu commence par tester « 9 + », et en te rendant compte que « 9 + 6 » = 15 donc toutes les branches appartenant à [6,9] vont foirer, tu t’épargne une trippotée de tests qui vont de toute facon aller au tapis. Avec cette méthode, tu t’assures « d’apprendre » de tes erreurs et de ne pas aller plus loin sans réfléchir en réalisant un élagage de l’arbre.

Enfin tu n’en as explicitement pas parlé mais dans ton cas les solutions « 3 + 5 + 7 » et « 7 + 5 + 3 » par exemple sont identiques. Donc tu peux opérer un autre élagage à chaque fois que tu trouves une solution en supprimant les combinaisons de cette dernière.

En faisant ainsi, tu évalues « théoriquement » tout l’ensemble de solutions (c’est donc une solution exacte, aucun triplet n’est laissé dans son coin) mais sans effectivement évaluer tous les triplets ce qui est bien mieux que la solution brutale. Ca demande un peu de finesse pour programmer tout ca pour ne pas passer finalement plus de temps a jouer avec ta structure de données qu’a vraiment trouver des solutions mais c’est l’idée.

Voila :slight_smile:

J’ai en gros compris (repérer ce qui ne va pas marcher pour éliminer ces cas sans autre calcul inutile), mais je suis pas sur de pouvoir faire (c’est faisable simplement avec 2-3 boucles ?).
Parce que, j’ai pas précisé mais je débute hein. On fait du C++, mais on utilise que des trucs de “base” (on a même pas encore vu les pointeurs), et il faudrait une méthode simple (si ça existe?). Mais surtout ça me parait bizarre que les profs aient pondu un truc aussi “poussé” alors qu’on débute (et encore je m’en sors très bien par rapport à pas mal d’autres qui ont vraiment du mal).

Oui, donc un sous ensemble du même problème.

C’est en cours de prog que tu vois ça ou dans un autre cours ? je me rappelle avoir étudié ces problèmes dans un cours intitulé “recherche opérationnelle et aide à la décision”, qui était beaucoup plus un cours d’algo que de code …

[quote=« astrojojo, post:1, topic: 46421 »]je dois effectuer toutes les sommes possibles avec des combinaisons de 3 entiers compris entre 1 et 9 parmis X éléments (9 normalement, mais avec un algo ça devrait facilement s’adapter à d’autres quantités). En effet je dois vérifier que leur somme fasse 15. Alors je peux prendre le problème à l’envers, et vérifier que tout les éléments à vérifier (qui se trouvent dans un tableau) sont dans un liste (j’ai listé 7 combinaisons possibles pour arriver à 15 avec 3 chiffres).
Mais voilà, je trouve ça laid, pas beau, inesthétique et c’est pas du tout ce que je veux :cry: . Je me doute qu’il faut des boucles (for probablement) imbriquées, mais ça s’arrête là.

Je sais qu’il y a des grand manitous ici, et si vous pouviez me mettre sur la bonne piste (je ne demande pas un algo tout prêt même si je ne serais pas contre :P), ça serait sympa, parce que j’ai du mal là :slight_smile: .

Merci :crying:[/quote]

je comprend pas à quoi fait référence les « X éléments ».

A un ensemble tout simplement :slight_smile: . Là j’ai 9 chiffres, mais ce nombre devrait pouvoir varier avec un algo.

Juste pour vérifier… parce que la j’ai un affreux doute.

Tu as un tableau d’éléments compris entre 1 et 9. Tu cherche toutes les combinaisons X + Y + Z = 15 avec X,Y et Z des éléments de ton tableau ? La solution que tu proposes c’est de faire toi même une liste de toutes les combinaisons possible te donnant 15 et de tester si ces éléments appartiennent bien au tableau ?

[quote=“JakeGrafton, post:9, topic: 46421”]Juste pour vérifier… parce que la j’ai un affreux doute.
Tu as un tableau d’éléments compris entre 1 et 9. Tu cherche toutes les combinaisons X + Y + Z = 15 avec X,Y et Z des éléments de ton tableau ?[/quote]

Je cherche pas vraiment les combinaison( y’en a 8 si je ne me trompe pas, ca se trouve assez vite à la main). Je cherche plutôt à faire la somme de 3 éléments parmis plusieurs (3, 4 ou 5 normalement) pour trouver si oui ou non il y 3 éléments dans le tableau qui font 15 (s’il y a 9, 8, 5 et 2, j’ai 8, 5 et 2 qui font 15).

Voilà je pensais faire ça, mais je trouve pas ça très “propre”, alors je me demandais s’il était possible de trouver un algo, ce qui serait plus “propre”, par exemple en faisant toutes les sommes possibles (et à la fin y’a juste à vérifier si elle fait 15).

[quote=“astrojojo, post:10, topic: 46421”]Je cherche pas vraiment les combinaison( y’en a 8 si je ne me trompe pas, ca se trouve assez vite à la main). Je cherche plutôt à faire la somme de 3 éléments parmis plusieurs (3, 4 ou 5 normalement) pour trouver si oui ou non il y 3 éléments dans le tableau qui font 15 (s’il y a 9, 8, 5 et 2, j’ai 8, 5 et 2 qui font 15).

Voilà je pensais faire ça, mais je trouve pas ça très “propre”, alors je me demandais s’il était possible de trouver un algo, ce qui serait plus “propre”, par exemple en faisant toutes les sommes possibles (et à la fin y’a juste à vérifier si elle fait 15).[/quote] Ok, donc t’as même pas a retourner toutes les combinaisons mais juste la première que tu trouves si tu en trouves une ?

Effectivement c’est pas super propre comme solution. Dans ce cas alors ca se fait simplement avec 3 boucles “for” :

[quote]int solution[3];
for (int indice1 = 0 ; indice1 < nbr_elements ; indice1 ++) {
for (int indice2 = 0 ; indice2 < nbr_elements ; indice2 ++) {
for (int indice3 = 0 ; indice3 < nbr_elements ; indice3 ++) {
if (tableau[indice1]+tableau[indice2]+tableau[indice3] == valeur && indice1 <> indice2 && indice1 <> indice3 && indice2 <> indice3) {
solution[0] = tableau[indice1];
solution[1] = tableau[indice2];
solution[2] = tableau[indice3];
return solution;
}}}}[/quote]

Un truc du genre…

Sinon tu fais quoi comme études ?

Je me demande ce que ton prof veut que tu fasses. Vu ton niveau ça serait plutôt une solution comme celle proposée par JakeGrafton plutôt qu’un truc générique qui gère un nombre variable d’éléments dans les combinaisons, tu ne dois pas encore avoir les connaissances pour faire ça.

Oulah je dois avoir Alzheimer, je pensais avoir répondu ^^
.

[quote=« JakeGrafton, post:11, topic: 46421 »]Ok, donc t’as même pas a retourner toutes les combinaisons mais juste la première que tu trouves si tu en trouves une ?

Effectivement c’est pas super propre comme solution. Dans ce cas alors ca se fait simplement avec 3 boucles « for » :

Un truc du genre…

Sinon tu fais quoi comme études ?[/quote]

Je viens de tester et ça a l’air de fonctionner. Je vais essayer un peu tout les cas histoire de tester plus longuement.
Merci beaucoup en tout cas, je me sens tout bête de ne pas avoir trouvé ça :slight_smile: .

La solution avec les 3 boucles for reste simple :crying:. Et je sais pas ce que veux les profs en fait (juste que ça soit correct, bien écrit et pensé).
Mais si je voulais éviter la solution « vérifier qu’une des combinaisons possible est présente », c’était juste pour moi, pour faire quelque chose de « propre » :cry:.

[quote=“astrojojo, post:13, topic: 46421”]Oulah je dois avoir Alzheimer, je pensais avoir répondu ^^[/quote]La reformulation ne fais jamais de mal pour être certain qu’on parle bien de la même chaussette. Après effectivement on peut faire générique et bien plus joli/propre mais je pense pas que ce soit ce que tes profs attendent.

Non les 3 boucles for me conviennent parfaitement, c’est exactement ce à quoi je pensais :). (J’ai juste rajouté en condition que les indices sont != 0 car sinon 7+8+0 = 15 mais moi je veux 3 chiffres joues, et 0 correspond a une case non jouee).
Bon voilà, me reste plus qu’à m’amuser avec le mode 1 joueur :cry:.

J’édite la balise!

Merci beaucoup JakeGrafton (et les autres aussi) :crying: ,

Hint 1 : the cake is a lie L’addition est commutative.
Hint 2 : Tu peux faire beaucoup mieux que du O(n^3)

[quote=“astrojojo, post:15, topic: 46421”]Non les 3 boucles for me conviennent parfaitement, c’est exactement ce à quoi je pensais :). (J’ai juste rajouté en condition que les indices sont != 0 car sinon 7+8+0 = 15 mais moi je veux 3 chiffres joues, et 0 correspond a une case non jouee).[/quote]Attention, les indices d’un tableau commencent à 0! Si tu spécifie un int tableau[3] tes éléments sont accessibles aux indices 0,1,2! Ce sont les valeurs de ton tableau qui ne doivent pas être = 0, pas les indices! Attention aux pinceaux…

[quote=“Moloch, post:16, topic: 46421”]Hint 1 : the cake is a lie L’addition est commutative.[/quote]Huh ? Et ?

[quote=“Moloch, post:16, topic: 46421”]Hint 2 : Tu peux faire beaucoup mieux que du O(n^3)[/quote]C’est ce sur quoi j’étais parti au début en allant directement dans la recherche opérationnelle mais je doute que ce soit ce qu’il faut à l’astrojojo. On peut faire bien plus rigolo avec des pointeurs, une structure arborescente et de la récursion rigolotte mais la on aura perdu le jojo avant la 3eme ligne.

Mmmm sans tout cela je pense que je peux faire du O(n), d’ailleurs je m’y mets.

[quote=« Moloch, post:16, topic: 46421 »]Hint 1 : the cake is a lie L’addition est commutative.
Hint 2 : Tu peux faire beaucoup mieux que du O(n^3)[/quote]
Hein :slight_smile: ?

Oui, pas de soucis là dessus, mais merci quand même :crying:.

Mais euhhhh :cry:.

Comme d’hab je raconte nimp, O(n) est possible seulement avec deux elements, la je suis dans quelque chose de vraiment bon, mais au pire en O(n^2).

C’est un backtracking tout simple, d’ailleurs ca m’etonnerait pas que ton prof s’attende a truc de ce genre. J’espere avoir bien compris l’ennonce…

En gros le but c’est de construire un tableau avec les occurences possibles, et parcourir les pioches possible jusqu’a trouver la bonne. Durant le chemin les nombres tires sont memorises pour les afficher a la fin.

[code]#include
#include
#include

#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>

#include

#include

using namespace std;
using namespace boost::lambda;

int ExtractNextAvailableValue(std::vector &vec, int iStart)
{

int iValue = 0;

for (std::vector::size_type i = iStart; (i < vec.size()) && (iValue == 0); ++i)
{
if (vec[i] > 0)
{
iValue = i;
–vec[i];
}
}

return iValue;

}

template <int _MaxVal, int _MaxDepth>
bool backtrack(std::vector &vec, int iSum, int iDepth, std::list &listPath)
{

if (iDepth >= _MaxDepth)
return false;

// optimiz0r pour la derniere profondeur
if (iDepth == (_MaxDepth - 1))
{
if (iSum > _MaxVal)
return false; // rien a tenter si notre somme est toujours superieure a _MaxVal

// il faut au moins une occurence de iSum
if (vec[iSum] > 0)
{
listPath.push_back(iSum);
return true;
}
else
{
return false;
}
}

for(int i = 1; i < vec.size(); ++i)
{
int iValue = ExtractNextAvailableValue(vec, i);
if (!iValue)
return false;

// no time wasted on values too great
if (iValue < iSum)
{
listPath.push_back(iValue);

if (backtrack<_MaxVal, _MaxDepth>(vec, iSum - iValue, iDepth + 1, listPath))
return true;

listPath.pop_back();
}

// put back
vec[iValue]++;
}

return false;

}

bool WillThereBeCake(int iSum, vector &Ingredients, list &listPath)
{

// on veut savoir si la combinaison est possible et presente…
// donc deja on extrait les occurences de chaque

vector Occurences(10);

int & (vector::* pf) (vector::size_type ) = &vector::at;

// O(n)
for_each(Ingredients.begin(), Ingredients.end(), ++bind(pf, &Occurences, _1));

// :o c’est beaucoup plus simple maintenant…

return backtrack<9, 3>(Occurences, iSum, 0, listPath);

}

int main(int argc, char **argv)
{

vector Recipee(10);

int i = 0;

generate(Recipee.begin(), Recipee.end(), var(i)++);

// there will be cake
vector Ingredients(30);

generate(Ingredients.begin(), Ingredients.end(), rand);
transform(Ingredients.begin(), Ingredients.end(), Ingredients.begin(), (_1 % 9) + 1);

list listPath;

cout << WillThereBeCake(15, Ingredients, listPath) << endl;

for_each(listPath.begin(), listPath.end(), cout << _1 << ‘.’);

cout << endl;

}[/code]