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

En fait c’est pas ce que je voulais dire, il y a plusieurs raisons pour lesquelles j’aime pas le switch :

[ul]
[li]Ils sont source de bug car un break est facilement oublié, surtout en cas de rajout / modification sur un code dont on est pas l’auteur;[/li][li]Ils sont signes d’une erreur (peut-être mineure) de design et certainement de sous-utilisation du polymorphisme de variable et de la spécialisation de template[/li][li]Ils provoquent des troubles de l’érection[/li][/ul]

[quote=“Moloch, post:41, topic: 46421”]En fait c’est pas ce que je voulais dire, il y a plusieurs raisons pour lesquelles j’aime pas le switch :

[ul]
[li]Ils sont source de bug car un break est facilement oublié, surtout en cas de rajout / modification sur un code dont on est pas l’auteur;[/li][li]Ils sont signes d’une erreur (peut-être mineure) de design et certainement de sous-utilisation du polymorphisme de variable et de la spécialisation de template[/li][li]Ils provoquent des troubles de l’érection[/li][/ul][/quote]
[li] Ils sont très pratiques.[/li]Sinon je suis globalement pas d’accord avec toi. Source de bug si on oublie des trucs… à ce moment là, tout est source de bug. Un peu de sérieux et de rigeur vient facilement à bout de ce genre de probleme.

Pour l’erreur de design, je suis (presque) d’accord avec toi d’un point de vue purement théorique. D’un point de vue pratique, je vais pas faire 250 classes pour juste comparer ca a une string qui change. Et si oui, on peut le faire avec des if, c’est autrement plus pete couille (à mon humble avis, qui vaut ce qu’il vaut, et que je vous invite tous à prendre en considération malgré tout parce que je dis pas que des conneries).

(et je bande comme un taureau).

Maintenant, c’est comme tout, faut savoir abuser de rien et faire les choses intelligement.

(bon en plus, j’aime pas le c++. <3 C#)

Les humains font des erreurs, les programmeurs sont des humains, donc les programmeurs font des erreurs.

Les langages de programmation s’orientent de plus en plus vers un maximum de détection d’erreur à la compilation pour une raison très simple : c’est à ce moment que la détection est la moins chère. Le switch est une construction qui augmente la probabilité de faire des erreurs.

On écrit des compilateurs parce que l’assembleur c’est source d’erreur (entre autres…). Cela n’empêche pas beaucoup de programmeurs d’écrire du code assembleur sans erreurs.

On a arrêté de faire des goto dans tous les sens parce que, pareil, c’est source d’erreur. etc. etc.

Pour prendre une analogie un peu naïve, rouler vite, ça augmente la probabilité d’avoir des accidents. Tu peux être prudent, avoir une bonne voiture, etc., en conduite comme en programmation, tu ne contrôles pas tout.

Je suis pas sûr de comprendre… Pas besoin de créer 250 classes avec les templates, c’est ça la beauté du truc… Tu peux faire un meta-vecteur qui contiendra le mapping, ou un vecteur… ou une map…

genre…

[code](pseudo code)

class v : public std::vectorstd::wstring
{
public:
v(void)
{
push_back(« blah »);
push_back(« we »);
push_back(« omg »);
}
}

std::wstring get_string(int iCode)
{

static v vec;

// pourquoi faire un switch quand on peut faire un vecteur ?
return vec[iCode];

}[/code]

Le mieux c’est un meta vecteur, mais c’est moins triv. L’avantage du meta vecteur c’est les assertions statiques, tu peux à la compilation vérifier que tu n’as rien oublié, cf ma remarque plus haut.

Maintenant dans mon code j’ai aussi des switches parce que c’était plus simple ou plus adapté dans le contexte donné… Toute règle a des exceptions et je fais pas partie des gens qui dès qu’ils voient dans un code le déclare pourri.

Ce problème s’appelle Subset Sum Probleme : http://fr.wikipedia.org/wiki/Problème…_sous-ensembles

Et il est NP-Complet, donc il existe pas de problème Polynomiaux pour le resoudre…

Mais sinon, vu que doit quand meme coder le truc,

Je ferai une fonction F à deux arguments, qui prendrai la sommes et le nombre de termes.
Si tu dois trouver 15 avec 3 entiers entre 1 et 9
j’appelmerai avec une boucle,
F(15,3) = concat(1 , F(14,2)) . concat(2 , F(13,2)) . … . concat(9, F(6,2));

Où concat est une fonction qui rend la listes de la concatenation du premier argument avec chaque element de la liste qui est donnée en deuxieme argument.

Ca reste NP-Complet…

Ensuite on va optimiser, Dans mon algo il va y avoir des repetitions de calcul :
Dans la branche F(14,2) on va caculer au bout d’un moment F(1,1) et dans la branche F(13,2) on va aussi calculer F(1,1)
Quand tu calcules F(n,m), tu gardes en memoire que tu as calculer F(n,m). Quand tu rappelles la fonction F tu regardes si elle a déjà etait calculée, si oui tu donnes directement le resultat. ça evite de te retapper le calcul.
Sinon tu calcules.

C’est un truc que je coderai en Scheme, en moins de 15 lignes je penses…

Scheme ?

Sinon c’est résolu , j’ai fait ça http://www.geekzone.fr/ipb/index.php?s=&am…st&p=604353 :crying:. Mais merci :).

On ne cherche pas a resoudre le probleme, mais une instance de celui-ci, ca aurait ete bien cruel de la part du prof sinon…

Toutes les solutions postees sont polynomiales (meme les trois for imbriques le sont, n^3, c’est pas terrible mais polynomial, quant aux differents backtracking postes ils sont tous sub-n^2) ?

Que le probleme general soit non polynomial, personne n’en doute, et ca deja ete evoque en faisant allusion au probleme du sac de voyageur, lui aussi NP-Complet, et comme tu le sais, tout probleme NP-Complet peut etre reduit a un autre probleme NP-Complet.

La NP-completude n’a pas d’interet sur le plan pratique, c’est un outil theorique qui a ete invente pour tenter de repondre a la grande question du « P est il dans NP ».

Cela dit connaitre les problemes NP c’est tres bien car tu vois tout de suite quand tu t’attaques a un probleme glissant et qu’il va falloir trouver des optimisations grace au contexte.

[quote=« Moloch, post:46, topic: 46421 »]On ne cherche pas a resoudre le probleme, mais une instance de celui-ci, ca aurait ete bien cruel de la part du prof sinon…

Toutes les solutions postees sont polynomiales (meme les trois for imbriques le sont, n^3, c’est pas terrible mais polynomial, quant aux differents backtracking postes ils sont tous sub-n^2) ?[/quote]

Vu que c’est une petite instance du problème, le problème devient plus facile, comme tu le dit c’est n^3. Et je suis d’accord avec toi pour dire que le problème pour résoudre cette instance est polynomial. Mais si tu choisis de résoudre ce problème, avec 4 variables la complexité passe à n^4. et pas (n+1)^3. Donc ce problème est exponentiel (normal).

Mais avec 100 variables, je prend pas beaucoup de risque à dire que personne ici ne peux résoudre ce problème.

Et le backtracking est n^3 aussi. Dans le pire dans cas tu parcours l’ensemble des solutions quand même.

Ça a un intérêt, c’est pas juste un outil théorique, c’est juste un nom que l’on a donnée a des problèmes, et on a prouvé que ces problèmes sont les plus difficiles. Et les gens doivent résoudre se genre de problème aussi. Le seul truc qu’il savent c’est quand il y a trop de variable, on ne peux plus rien faire.

Et sinon la grande question c’est NP est t’il dans P. C’est super facile de montrer l’inverse (que P est dans NP)

Et on a pas inventé ça pour répondre à cette question. On c’est juste demandé si ces deux classes de problème, NP et P, étaient différentes ou équivalente. Et à ce jour personne n’a réfuté ou prouvé ce problème.

On dit plus souvent problème du sac à dos il me semble. Tu n’aurais pas fait un mix avec le voyageur de commerce ? :slight_smile:

Sauf que la derniere etape est un lookup en O(1), ca marche aussi sans backtracking remarque, c’est juste que le bt permet plus facilement de rajouter des etapes.

Un probleme NP est difficile a resoudre, un probleme NP-complet est tres difficile a resoudre… On pourrait aussi ajouter fortement NP-complet, presque complet, etc.

Concretement, quand ton truc est NP, t’es mort des que tes donnees explosent. S’il est NP-complet t’es plus mort que mort, ouais ok, et puis s’il est dans fortement NP-complet t’es mort de l’apocalypse et puis si c’est EXP et puis et puis…

Toute facon meme savoir que ton probleme est dans P c’est pas forcement gagne, je repense au test de primalite « polynomial » AKS…

…et parfois ton probleme NP peut se resoudre de maniere tres simple dans ton cas donne. etc.

Erreur de ma part, en fait oui, le but est de prouver que P = NP (donc que l’un est inclus dans l’autre, une relation etant triviale), enfin bon les travaux c’est plutot de prouver que P ≠ NP. Vaste debat, je ne suis pas theoricien…

Oui, sac a dos (knapsack), exactement, pas sac de voyageur…

Mon premier emploi a ete de bosser sur des programmes d’optimisation des tournees de livraison, donc je suis un peu traumatise par le voyageur de commerce. :slight_smile:

Yep, t’as tout a fait raison, mais NP c’est l’ensemble des problèmes qui peuvent être resolu avec un algo non déterministe polynomial.
Donc NP ne signifie pas forcement difficile et encore moins expo
Car P inclue dans NP
Et NP-Complet est inclue dans NP aussi…

Ah les cours de complexité quel bonheur…

En gros le truc c’est que si un des problèmes NPC se réduit dans P alors P=NP.

Et je pense aussi que le « vrai » problème c’est P≠NP, et même si ya un gars qui montre que le problème N=NP est indécidable ça m’entonnerai pas, mais ça c’est juste mon avis.

En tout cas je trouve ça très intéressant comme problème, mais si j’ai l’impression que c’est plus trop d’actualité la recherche dedans, on cherche plus a trouvé une solution efficace pour résoudre ces problèmes.

J’en profite pour linker un article qui m’a appris pas mal de truc, je connaissais pas au final ce qu’on avait vraiment trouvé en théorie sur N et NP :
http://interstices.info/display.jsp?id=c_21832

Voilà :slight_smile:

Je voudrais pas interrompre dans le débat, mais j’aimerai bien votre avis sur mes 3 boucles for où je part de l’indice précédent :).
Je pense que c’est bon mais je voudrais juste confirmation s’il vous plait (youpi projet fini, avec 3 semaines 1/2 d’avance, je vais pouvoir faire le 2ème pour des points bonus \o/).

[quote=“astrojojo, post:38, topic: 46421”]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][/quote]

Bon je sais pas si tu veux bien optimiser, mais soyons fou :

L’ordre du test n’est pas optimal.
(i != j) && (j != k) && (k != i) && (joueur[i] != 0) && (joueur[j] != 0) && (joueur[k] != 0)) && (joueur[i]+joueur[j]+joueur[k] == 15)
Voilà là c’est mieux car, fait i!=j c’est pas couteux. Mais faire (joueur[i]+joueur[j]+joueur[k] == 15) c’est lourd, donc si tu commences à évaluer les truc pas couteux c’est plus mieux.

Et pour finir, tu commence ta boucles a i=j, le test du if va être forcement faux donc tu peux commencer à i=j+1.

Par contre il y a un truc que je comprend pas c’est pourquoi tu veux que tout les chiffres soient différents, pourquoi la solution 3+3+9 te plait pas ?

Et niveau complexité l’algo que j’ai proposé est un peu mieux, je pense car je teste pas les combinaisons, mais uniquement sur les bonnes.

ok, merci pour ces astuces :).

Pour le 3+3+9, c’est qu’en fait ces nombres représentent chacun une case, et qu’une case n’est jouée qu’une seule fois. Donc pas de doublons de chiffres possibles :crying:.

Je dis n’importe quoi… Enfin je pensais a l’egalité

1 != 2 et 2 != 4 n’implique pas 1 != 4…

/me sort

J’ai pas osé le dire :).
Sinon du coup avec i=0; j=i+1 et k=j+1, je n’ai normalement plus besoin des conditions (i != j)( j != k) et( i != k )! Me trompe-je ?

Ptet je dis encore des conneries :slight_smile: , mais je crois que ça sert plus à rien.

Supprime le dernier for avec un lookup dans une table. En fait quand tu arrives dans le dernier for, soit tu as un nombre disponible pour ta valeur V - a - b soi tu n’as rien, inutile de tout tester.

« un lookup dans une table » ?
Je vois pas bien ce que tu veux dire :slight_smile: . Faut bien que je cherche si la valeur manquante est dispo, non ?

[quote=« astrojojo, post:58, topic: 46421 »]« un lookup dans une table » ?
Je vois pas bien ce que tu veux dire :slight_smile: . Faut bien que je cherche si la valeur manquante est dispo, non ?[/quote]

Tu construis au debut une table des frequences de tous les elements, indexee par la clef de chaque element, a chaque iteration tu retires un de cette table, si a la derniere la valeur a l’index du reste est > 0 tu sais que c’est bon. cf le code example.

Euh, c’est un peu compliqué pour moi là :slight_smile: