Coder proprement le compte est bon

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Salut,
Je vous explique mon problème imaginons que j'ai trois variables: nb1, nb2 et objectif

Le but est de verifier qu'objectif est une somme / soustraction de nb1 et nb2. C'est pas très difficile

1
2
if( (nb1 + nb2) == obj || (nb1 - nb2 ) == obj || (nb2 - nb1 ) == obj)
    std::cout <<"Tu peux le faire je crois en toi !";

Le problème c'est que c'est moche, si j'ai trois+ variables ou d'autres operations, je peux pas taper toutes les combinaisons à la main.

Je n'arrive pas a mettre au point une technique pour le faire. En python j'aurais mis un tableau avec les operations ( string - / +) et les nombres et j'aurais fait toutes les combinaisons puis pris les résultât avec eval().

Mais en C++ une fonction comme eval n'existe pas (à ce que je sais). Comment dois-je m'y prendre ?

Édité par d3m0t3p

conseil: le thé est meilleur avec un zeste de citron

+0 -0

Cette réponse a aidé l'auteur du sujet

Salut.

Tu peux procéder par récursion et backtracking. À chaque étape de la récursion, tu ajoute/soustrais un nombre, puis une fois que tu es au bout, tu regarde si tu obtiens le résultat attendu. Sinon, tu remonte d'un cran et tu teste avec une autre opération.

Attention, c'est une méthode naïve, à complexité exponentielle.

Mon Github | Pony : Un langage à acteurs sûr et performant

+0 -0

Cette réponse a aidé l'auteur du sujet

Je ne vais pas parler d'algo : la force brute est probablement pas top, mais osef pour le moment.

Une "opération" en C++ est simplement une fonction. Il suffit donc créer un tableau de fonctions et le parcourir.

Un exemple rapide (mode brutasse) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <functional>
#include <string>

using op_t = std::pair<std::string, std::function<int(int, int)>>;

#define op(name) op_t{std::make_pair(#name, [](int lhs, int rhs) { return lhs name rhs; })}

auto vals = { 12, 23, 7, 18, 17 };
auto ops = { op(+), op(-), op(*), op(/) };
auto result = 30;

int main() {
    for (auto&& val1: vals) 
        for (auto&& val2: vals)
            for (auto&& o: ops)
                if (o.second(val1, val2) == result)
                    std::cout << "trouve!: " << val1 << 
                    o.first << val2 << std::endl;
}

Il faudrait mieux encapsuler cela, éviter les doublons, etc. Voire générer les opérations au compile time via template. Mais c'est l'idée de base : créer des fonctions pour les opérations et les manipuler comme des objets.

+0 -0

Dans la plupart des cas, la complexite sera de toute maniere exponentielle en la taille de l'ensemble de nombre a tester si tu peux prendre un sous-ensemble de taille quelconque et que tu ne fais pas d'hypothese sur les proprietes des operateurs.

En effet, si tu as initialement un ensemble de $n$ nombres, le nombre de combinaisons est deja exponentiel, sans meme tenir compte des operateurs et de leurs proprietes.

Le seul cas un peu simple que je vois c'est si tu veux a chaque fois utiliser l'ensemble de tes nombres et que tous tes operateurs sont commutatifs (ce qui n'est deja pas ton cas).

« Kommunist Fried Chicken » | Macroeconomics: Three decades of intellectual regress

+1 -0

Juste pour dire (pour eviter les confusions) : ca depend de comment on comprend la generalisation du probleme a trois variables ou plus.

(1) Peut-on obtenir l'objectif en exactement une operation, quand l'operation et les deux operandes decrivent l'ensemble donne ? (code de gbdivers)
(2) Deuxieme possibilite : peut-on l'obtenir en effectuant un nombre quelconque d'operations elementaires sur les elements de ces ensembles ? En fait, au vu de l'exemple pour $n=2$, il faut surement modifier la question en : peut-on l'obtenir en utilisant exactement (ou bien au plus, en demandant de faire au moins une operation, comme le laisserait entendre le terme de combinaison) une fois les elements de cet ensemble ? (reponses de KFC/Praetonus)

Suivant la vision qu'on prend (meme au sein des variations de (2)), on obtient des problemes plus ou moins difficiles.

Édité par Lucas-84

Si je ne me trompe pas, le compte est bon permet d'utiliser les nombres (et pas forcément tous) dans l'ordre voulu, avec les opérateurs et les parenthèses voulu.

Par exemple, pour obtenir 888 avec 1, 2, 3, 10, 75 et 100, on peut très bien faire $(75 - 1) \times (10 + 2)$.

Si c'est bien ça, je ne pense pas qu'il existe d'algorithme qui ne soit pas exponentiel dans le pire cas. Cependant, il semble qu'il y a moyen d'utiliser de la programmation dynamique pour éviter une (petite) partie du massacre.

En terme de code, l'idée de gbdivers est plutôt bonne, mais j'aurais tendance à utiliser std::plus, std::minus et autres pour éviter le #define.

+0 -0

Le #define sert surtout à afficher le nom de l'opération quand un résultat est trouvé.

Et mon code est largement perfectible. En particulier par que je repetes 2 fois chaque calcul (x@y et y@x) et j'utilise plusieurs fois la même valeur (x@x). Il faudrait implémenter quelque chose comme sample pour sortir une liste de 1 a N valeurs non repetees.

Édité par gbdivers

+0 -0
Auteur du sujet

je pensais avoir envoyé une réponse, mais j'ai du oublier de cliquer sur le bouton envoyer ^^

Merci à tous pour vos réponses,
Je me suis mis à lire des articles sur le backtracking, en particulier la résolution d'un sudoku.

@gbdivers:
Je ne comprends pas pourquoi il y a une fois # devant le name, mais pas les autres fois.

1
#define op(name) op_t{std::make_pair(#name, [](int lhs, int rhs) { return lhs name rhs; })}

EDIT: la lambda se faisait transformer en lien avec le format touche

Édité par d3m0t3p

conseil: le thé est meilleur avec un zeste de citron

+0 -0

Cette réponse a aidé l'auteur du sujet

Dans une macro, # sert à transformer le contenu de la variable en chaîne de caractère.

Même s'il n'y en a pas ici ## sert à concaténer 2 contenus/mots

#define op(name) #name avec op(+) donne "+"

#define cat(a,b) a##_##b avec cat(un, truc) donne un_truc

Édité par jo_link_noir

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte