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

Ah oui mais si Astrojojo dit qu’il ne connait pas les pointeurs, je suppose qu’il ne connait pas les structures de données et je suppose donc qu’il n’a pas le droit d’utiliser vector, list… et ces trucs bizarres de boost :slight_smile:

Pour ma part j’ai répondu à une part de la question, c’est-à-dire déterminer si il existe une solution dans les sommes possibles, et ceci avec un nombre de variable de sommes.
J’ai fait donc ça sans structure de données, avec une simple récursion. Je me trompe peut-être mais je ne vois pas trop comment pouvoir afficher les éléments composant la somme sans aucune structure de données variable comme un tableau dynamique à la C99, liste, pile…

[code]#include <stdio.h>
#include <stdlib.h>

#define GOAL 15
#define NB_SUM 3

int values[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

void
sum_rec(int nb_sum, int val)
{
int i;
if (nb_sum == 0) {
if (val == GOAL) {
printf(« Une combinaison existe\n »);
exit(0);
}
return;
}
for (i = 0; i < sizeof(values)/sizeof(values[0]); i++) // Pas correct car réutilise plusieurs fois la même valeur
sum_rec(nb_sum - 1, val + values[i]);
}

int
main()
{
int nb_val = NB_SUM;
sum_rec(nb_val, 0);
printf(« Pas de combinaison\n »);
return 0;
}[/code]

Version corrigée :

[code]#include <stdio.h>
#include <stdlib.h>

#define GOAL 15
#define NB_SUM 3

int values[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

void
sum_rec(int nb_sum, int val, int index)
{
int i;
if (nb_sum == 0) {
if (val == GOAL) {
printf(« Une combinaison existe\n »);
exit(0);
}
return;
}
for (i = index; i < sizeof(values)/sizeof(values[0]); i++)
sum_rec(nb_sum - 1, val + values[i], i + 1);
}

int
main()
{
int nb_val = NB_SUM;
sum_rec(nb_val, 0, 0);
printf(« Pas de combinaison\n »);
return 0;
}[/code]

[quote=« kineox, post:21, topic: 46421 »]Ah oui mais si Astrojojo dit qu’il ne connait pas les pointeurs, je suppose qu’il ne connait pas les structures de données et je suppose donc qu’il n’a pas le droit d’utiliser vector, list… et ces trucs bizarres de boost :slight_smile:

Pour ma part j’ai répondu à une part de la question, c’est-à-dire déterminer si il existe une solution dans les sommes possibles, et ceci avec un nombre de variable de sommes.
J’ai fait donc ça sans structure de données, avec une simple récursion. Je me trompe peut-être mais je ne vois pas trop comment pouvoir afficher les éléments composant la somme sans aucune structure de données variable comme un tableau dynamique à la C99, liste, pile…[/quote]

Ton code a le mérite d’être très clair.

Tu peux ajouter l’optimisation pour la dernière étape, qui consiste à ne pas s’arrêter à 3 si sum == 0, mais tout simplement à 2 si sum == élément présent, tu gagnes une récursion.

Autre truc, il faut rajouter du code pour générer l’ensemble de « pioche » car là tu testes que dans values si j’ai bien compris. Tu ne fais pas l’étape qui consiste à organiser les données pour le traitement qui est assez importante pour le backtracking.

Je pense qu’on doit pouvoir améliorer encore l’algorithme de backtracking, au risque de perdre un peu en généricité.

Pour les trucs zarbis de boost (lambda fonctions), c’est dans le prochain standard du C++. Une journée sans lambda est une journée perdue en plus.

[quote=« Moloch, post:22, topic: 46421 »]Ton code a le mérite d’être très clair.

Tu peux ajouter l’optimisation pour la dernière étape, qui consiste à ne pas s’arrêter à 3 si sum == 0, mais tout simplement à 2 si sum == élément présent, tu gagnes une récursion.[/quote]
Oui exact.

[quote=« Moloch, post:22, topic: 46421 »]Autre truc, il faut rajouter du code pour générer l’ensemble de « pioche » car là tu testes que dans values si j’ai bien compris. Tu ne fais pas l’étape qui consiste à organiser les données pour le traitement qui est assez importante pour le backtracking.

Je pense qu’on doit pouvoir améliorer encore l’algorithme de backtracking, au risque de perdre un peu en généricité.[/quote]
Bien sûr j’aurais pu faire un truc beaucoup plus compliqué et puissant, ne t’en fais pas. Ce que je voulais c’est juste faire un code très simple pour astrojojo. Sauf que maintenant que j’y réfléchis, il n’a probalement pas vu la récursion non plus :slight_smile:

Et moi je dis vive le C (bon ok ça a l’air assez sympa quand même :crying:)

Edit : en fait en relisant le thread je me suis rendu compte que je ne répondais pas vraiment à la question puisque mon code autorisait à prendre plusieurs fois la même valeur (ex : 6 + 6 + 3 = 15). C’est de cas dont tu parlais Moloch ? (l’ensemble de « pioche »)

[quote=« kineox, post:23, topic: 46421 »]Oui exact.

Bien sûr j’aurais pu faire un truc beaucoup plus compliqué et puissant, ne t’en fais pas. Ce que je voulais c’est juste faire un code très simple pour astrojojo. Sauf que maintenant que j’y réfléchis, il n’a probalement pas vu la récursion non plus :slight_smile:

Et moi je dis vive le C (bon ok ça a l’air assez sympa quand même :crying:)[/quote]

Et non, j’ai pas encore vu, c’est pour ça que j’y comprend pas grand chose je crois ^^.
Sinon j’ai bien avancé depuis tout à l’heure, ça m’a bien débloqué :cry:.

Alors essaie d’abord de respecter les règles de base de la programmation structurée. Je ferais comme ça à partir du code qui est passé, mais je ne suis même pas sûr d’avoir compris l’énoncé…
En C++ tu peux utiliser le type bool, à part ça j’espère qu’il n’y a pas trop de différences.

[code]#include <stdio.h>

#define TRUE 1
#define FALSE 0

unsigned int foo (int tab[], int solution[], unsigned int nbElem,
int valCherchee);

int main (void)
{
int tab[5] = {10,2,3,4,5};
int solution[3];

if (foo(tab,solution,5,15) == TRUE)
{
puts (“Youpie”);
}
else
{
puts (“Oh noes”);
}

return 0;
}

unsigned int foo (int tab[], int solution[], unsigned int nbElem,
int valCherchee)
{
unsigned int i1, i2, i3;
unsigned int fin = FALSE;

for (i1 = 0; i1 < nbElem && fin == FALSE; i1++)
{
for (i2 = 0; i2 < nbElem && fin == FALSE; i2++)
{
for (i3 = 0; i3 < nbElem && fin == FALSE; i3++)
{
if (tab[i1]+tab[i2]+tab[i3] == valCherchee
&& i1 != i2
&& i1 != i3
&& i2 != i3)
{
solution[0] = tab[i1];
solution[1] = tab[i2];
solution[2] = tab[i3];
fin = TRUE;
}
}
}
}

return fin;
}[/code]

Je pense que ce que Moloch voulait dire c’est qu’au lieu de faire :

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

tu peux faire :

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

Par exemple pour les données {1, 2, 3, 4} au lieu de générer les combinaisons arrangements (avec répétitions) (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4) … (3, 3, 3), tu peux générer uniquement
(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4) (ce qui correspond ce coup ci aux combinaisons, il y en a bien (4!)/3!(4-3)! = 4.

Exactement kineox, sauf qu’apres je me suis rendu compte que le mieux c’etait un backtracking sur des donnes ordonnees.

Ce matin je me suis dit qu’on pouvait optimiser encore d’avantage, a la deuxieme recursion, on commence a l’indice Cible - Cardmax. Plus concretement.

Actuellement :

[ol]
[li](non optimisee) On teste avec 1 (si disponible)[/li][li](non optimisee) On teste avec le prochain disponible, ca peut etre 1, 2, 3…[/li][li]i [/i]On fait un lookup pour voir si la valeur est disponible[/li][/ol]

Version amelioree qui double les performances dans une distribution uniforme:

[ol]
[li](non optimisee) On teste avec 1 (si disponible)[/li][li]i[/i] On teste avec le prochain disponible, mais dont le resulat peut potentiellement etre valide, c’est a dire pour une cible a 15, il faut commencer a 5, car 15 - 1 -5 = 9 qui est le maximum possible. Autrement dit, il n’existe aucune combinaision valide qui commence par le couple (1,4)[/li][li]i [/i]On fait un lookup pour voir si la valeur est disponible[/li][/ol]

Pour des cardinaux d’ensembles superieurs a 10, je ferais une dichotomie par le milieu, mais pour 10, c’est bien de faire de gauche a droite.

N’empeche que c’est typiquement le genre de question qui peut etre posee en entretien d’embauche, par exemple chez Google je sais qu’il y a une question de ce type basee sur les tables de hashage.

Edit, modification a apporter :

-for(int i = 1; i < vec.size(); ++i) +for(int i = (iDepth == (_MaxDepth - 2)) ? (iSum - _MaxVal) : 1; i < vec.size(); ++i)

Vous m’en voulez pas si je vous abandonne ? :slight_smile:

:crying: D’un autre cote ca veut dire que tu es sans doute capable d’avoir des interactions sociales normales. Tu peux encore etre sauve, abandonne l’informatique maintenant !!

Zut je viens juste de revoir le tag C++, tant pis, puisque c’est résolu j’ai le droit de dire nimp.
Fais ça avec maple, et utilise l’option “remember”, qui permet de se rappeller des résultats précédents.

Oublis.
Sauf s’il existe un truc dans une libririe quelconque pour reproduire ce genre de comportements.

Ouai, sauf que bon ça m’empêche pas d’y penser assez souvent, et je me dis que ça m’amuse, et ça commence à m’inquiéter :crying:.

[quote=« fser, post:30, topic: 46421 »]Zut je viens juste de revoir le tag C++, tant pis, puisque c’est résolu j’ai le droit de dire nimp.
Fais ça avec maple, et utilise l’option « remember », qui permet de se rappeller des résultats précédents.

Oublis.
Sauf s’il existe un truc dans une libririe quelconque pour reproduire ce genre de comportements.[/quote]
Maple ?
Pour les lib, on a juste un « baba.h » fourni par la prof qui contient
#include
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include
#include <time.h>

Et quelques fonctions (principalement des trucs sur des chaines du genre premier ou reste).

[quote=« astrojojo, post:31, topic: 46421 »]Pour les lib, on a juste un « baba.h » fourni par la prof qui contient
#include
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include
#include <time.h>[/quote]
Dans un cours de C++ ? :slight_smile:

C’est plutôt de l’algo en fait, et on fait du C++ “sans le savoir” via le “langage baba” (beurk ce truc, mais on en a bientôt fini :)).

Effectivement : omfg.

<inquisition parce que je suis anal-rétentif et je m’emmerde un peu ce soir>

Ceci, c’est du C :

<span class="postcolor">#include <iostream> // <- bon sauf ça #include <math.h> #include <stdlib.h> #include <stdio.h> #include <string> // et ça #include <time.h>

La plupart de ces includes n’ont aucune raison d’être. St Sutter, notre prophète sur Terre et guide vers la lumière m’envoie un SMS m’autorisant à l’usage de l’ultra violence.

En C++, on utilise rarement les includes, C, et quand on le fait, on utilise les includes préfixés par « c » qui garantissent que tout se passe bien. Exemple

 #include <ctime> // et non #include <time.h>

J’aimerais qu’on me donne la justification pour <stdio.h> étant donné et .

Mais surtout filer un fichier .h au lieu d’expliquer la raison des includes sur le plan didactique je trouve ça bof.

Ok alors voilà ce qu’on va faire, tu vas nous donner l’adresse de ton prof, et nous, on se charge du reste. Moi je propose de l’attacher sur le pare-choc d’un Hummer™, rouler à fond sur l’autoroute allemande et le laisser mourir sous l’impact des moustiques en mettant de la musique bavaroise folklore à fond.

Cela dit garde toi bien de faire des remarques en cours si tu veux pas te faire saquer toute l’année, certains ont essayé et ils ont regretté…
</inquisition parce que blah blah blah knowin’ the perverted truth that rot inside the pit of your soul, that’s how my freakin’ day was!>

Oui, les “faut faire comme ça, ça c’est pas bien, et c’est comme ça, point!”, je connais xD.
Bref.

Tiens je vais en profiter pour poser une question su les switch case.
Au lieu de mettre switch(N) … case (N), est-ce qu’on a le droit de faire : case (N==x || N==y) ou alors on est obligé de faire ça avec des if ?

[quote=“astrojojo, post:35, topic: 46421”]Oui, les “faut faire comme ça, ça c’est pas bien, et c’est comme ça, point!”, je connais xD.
Bref.

Tiens je vais en profiter pour poser une question su les switch case.
Au lieu de mettre switch(N) … case (N), est-ce qu’on a le droit de faire : case (N==x || N==y) ou alors on est obligé de faire ça avec des if ?[/quote]
Tu peux faire :

switch (n) { case x: case y: /* ... */ break; default: }

En C en tout cas. Note que par convention les identifiants en majuscules sont réservés aux macros.

Ok merci des infos :).

Allez encore une petite question. J’ai pensé à un truc pour ne pas me taper toutes les operations, ça a l’air de fonctionner,
Mais je voulais confirmation de l’exactitude de la chose.

Au lieu de faire ça :

[code]for (int i = 0; i < 9; i ++){
for (int j = 0; j < 9; j ++){
for (int k = 0; k < 9; k ++){

			if (
				(joueur[i]+joueur[j]+joueur[k] == 15) &&  
				(i != j) && (joueur[i] != 0) &&			 
				(j != k) && (joueur[j] != 0) &&		  
				(k != i) && (joueur[k] != 0)){[/code]

J’ai fait ça :

[code]for (int i = 0; i < 9; i ++){
for (int j = i; j < 9; j ++){
for (int k = j; k < 9; k ++){

			if (
				(joueur[i]+joueur[j]+joueur[k] == 15) &&  
				(i != j) && (joueur[i] != 0) &&			 
				(j != k) && (joueur[j] != 0) &&		  
				(k != i) && (joueur[k] != 0)){[/code]

Je ne sais pas pourquoi j’ai l’impression de passer à côté de quelque chose, mais apparemment ça fonctionne.
Qu’est-ce que vous en dites ?

[quote=« astrojojo, post:35, topic: 46421 »]Oui, les « faut faire comme ça, ça c’est pas bien, et c’est comme ça, point! », je connais xD.
Bref.

Tiens je vais en profiter pour poser une question su les switch case.
Au lieu de mettre switch(N) … case (N), est-ce qu’on a le droit de faire : case (N==x || N==y) ou alors on est obligé de faire ça avec des if ?[/quote]

Le switch est une construction problématique qui peut généralement être évitée avec des spécialisations de templates.

En plus niveau performances c’est une catastrophe car la prédiction de branchement part dans l’espaaaace.

Mé bon parfois pas le choix… :slight_smile:

J’ai finalement remplacé ce switch par des if :).