Existe-t-il un moyen d'interchanger les opérateurs mathématiques dans une boucle while ou for ?

Question

J'essaie d'écrire un programme en C pour tester comment 6 nombres, qui sont entrés par l'utilisateur (ce n'est pas un problème jusqu'à présent), sont combinés de toutes les manières possibles.

J'ai essayé d'utiliser la fonction de recherche, mais je ne sais pas vraiment ce qu'il faut chercher.

Ça devrait faire un peu comme ça :

...
temp[i] = a + b + c + d - e - f;
i++;
temp[i] = a + b + c - d - e - f;
i++;
temp[i] = a + b - c - d - e - f;
i++;
...

Egalement avec les multiplications et les divisions.

Il serait bon d'implémenter également toutes les façons de mettre entre parenthèses et de ne pas utiliser tous les chiffres.

C'est comme forcer brutalement tous les résultats possibles à partir de ces chiffres.

Existe-t-il un moyen d'y parvenir sans coder chaque combinaison à la main ?

Answer 1

Récursion est très utile pour ce genre de choses :

#include <stdio.h>

void compute_all_combinations(int *list, int length, int running_total) {
    if (length <= 0) {
        printf("%d\n", running_total);
        return;
    }
    compute_all_combinations(list+1, length-1, running_total + *list);
    compute_all_combinations(list+1, length-1, running_total - *list);
}

int main() {
    int numbers[4] = { 3141, 5926, 5358, 9793 };
    compute_all_combinations(numbers, 4, 0);
    return 0;
}

En compute_all_combinations() fonction acceptera une liste de n'importe quelle longueur (dans la limite du raisonnable). Elle s'appelle récursivement pour parcourir tout l'arbre de décision représentant les sommes que vous essayez de calculer (c'est-à-dire qu'à chaque nœud, il faut bifurquer à gauche/droite pour ajouter/soustraire la valeur du nœud), et imprimer les résultats à chaque nœud feuille. J'espère que c'est assez explicite.

Answer 2

C'est un petit problème amusant sur lequel j'ai déjà passé beaucoup trop de temps ! Je n'utiliserais pas la récursion pour les permutations, mais ce n'est pas vraiment la partie la plus difficile de la question. Obtenir les groupements est facile si vous utilisez postfixe au lieu d'essayer de faire des groupements avec infixe. En supposant que j'ai fait quelques erreurs de copier-coller, ceci (ainsi qu'une suite de tests !) peut également être trouvé à l'adresse suivante https://github.com/wrp/examples/blob/master/c/arithperm.c . Un exemple d'exécution :

$ ./a.out 1.54 3 7.4 -2.3 1 78 | awk 'NR % 4027 == 0'
((1.54 / ((3 * 7.4) * -2.3)) * 1) / 78 = -0.000386674
((1.54 - 3) - ((7.4 - -2.3) / 1)) / 78 = -0.143077
(1.54 + ((3 + 7.4) / (-2.3 + 1))) / 78 = -0.0828205
((1.54 * (3 / 7.4)) * -2.3) * (1 / 78) = -0.0184096
((1.54 * 3) - 7.4) * ((-2.3 * 1) * 78) = 498.732
1.54 * (((3 + (7.4 - -2.3)) * 1) - 78) = -100.562
1.54 * ((3 - (7.4 / (-2.3 + 1))) + 78) = 133.506
1.54 - (((3 / 7.4) - -2.3) / (1 - 78)) = 1.57514
1.54 - (3 * (((7.4 * -2.3) + 1) - 78)) = 283.6
1.54 - (3 - ((7.4 - -2.3) + (1 / 78))) = 8.25282

Voici le code qui génère ce qui précède :

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <err.h>
#include <assert.h>

struct expression {
        double *operands;    /* The numbers to be manipulated */
        char operators[16];  /* operators to apply, eg "++/-*" */
        uint32_t mask;       /* A bit mask showing where to apply operators */
        int count;           /* Number of operands */
        struct element {
                double val;
                char descr[512];  /* Human readable description (for infix) */
        } *stack;                 /* Stack used for computation */
};

void * xmalloc(size_t s);
void parse_cmd_line(int argc, char **argv, struct expression*);
int next_op(struct expression *);
void eval(struct expression *);

int
main(int argc, char **argv)
{
        struct expression exp;

        parse_cmd_line(argc, argv, &exp);
        do eval(&exp); while(next_op(&exp));
        free(exp.operands);
        free(exp.stack);
}

/*
 * Evaluate the expression and pretty print it to stdout
 */
void
eval(struct expression *exp)
{
        int c = 0;
        uint32_t m = exp->mask;
        char *ops = exp->operators;
        struct element *sp = exp->stack;

        while( m ) {
                if( m & 0x1 ) { /* Apply an operator */
                        char buf[1024];
                        char *fmt = (m == 1) ? "%s %c %s" : "(%s %c %s)";
                        assert(sp - exp->stack > 1); /* True because of mask_is_invalid() */
                        assert(sizeof buf >= sizeof sp->descr); /* Ensure terminating null after strncpy */
                        sp -= 2;
                        snprintf(buf, sizeof buf, fmt, sp->descr, *ops, sp[1].descr);
                        strncpy(sp->descr, buf, sizeof sp->descr);
                        switch(*ops++) {
                        case '+': sp->val += sp[1].val; break;
                        case '-': sp->val -= sp[1].val; break;
                        case '*': sp->val *= sp[1].val; break;
                        case '/': sp->val /= sp[1].val; break;
                        default: assert(0);
                        }
                } else {
                        assert(c < exp->count);
                        sp->val = exp->operands[c++];
                        snprintf(sp->descr, sizeof sp->descr, "%g", sp->val);
                }
                sp += 1;
                assert( sp - exp->stack <= exp->count );
                m >>= 1;
        }
        sp -= 1;
        printf("%s = %g\n", sp->descr, sp->val);
        return;
}

int
mask_is_invalid(uint32_t m)
{
        /*
         * A mask is invalid (will lead to underflow) unless it meets the following condition:
         *  For any given bit, the number of unset bits to the right of it must be greater
         *  than the number of set bits.
         */
        int sum = 0;
        do {
                sum += ( m & 0x1 ) ? 1 : -1;
                m >>= 1;
        } while( m && sum < 0 );
        return sum >= 0;
}

/*
 * generate the next mask with N bits set.  See:
 * https://stackoverflow.com/questions/26594951/finding-next-bigger-number-with-same-number-of-set-bits
 */
uint32_t
next_mask(uint32_t x)
{
        do {
                uint32_t c = x & -x;
                uint32_t r = x + c;
                x = (((r ^ x) >> 2) / c) | r;
        } while( mask_is_invalid(x));
        return x;
}

/* Given a string of operators (eg "+*-/++"), generate the next permutation */
void
next_perm( char *s )
{
        size_t len = strlen(s);
        assert(strspn( s, "+-*/" ) == len);
        for( int i = 0; i < (int)len; i++) {
                switch(s[i]) {
                case '+': s[i] = '-'; return;
                case '-': s[i] = '*'; return;
                case '*': s[i] = '/'; return;
                case '/': s[i] = '+'; break;
                }
        }
}

int
next_op(struct expression *exp)
{
        int N = exp->count - 1;
        if(strspn( exp->operators, "/" ) == (unsigned)N) {
                exp->mask = next_mask(exp->mask);
                assert( exp->mask >= 1 << 2*N );
        }
        next_perm(exp->operators);
        return exp->mask < 1 << (2*N + 1);
}

/*
 * Initialize exp from the command line arguments.
 */
void
parse_cmd_line(int argc, char **argv, struct expression *exp)
{
        double *v;
        if(argc < 3 || argc > 14) {
                errx(EXIT_FAILURE, "Invalid call: must specify between 2 and 14 numeric values");
        }

        argv += 1;
        argc -= 1;
        exp->operands = v = xmalloc( sizeof *v * argc);
        exp->count = argc;

        for( ;*argv; argv++, v++ ) {
                char *end;
                *v = strtod(*argv, &end);
                if(*end != '\0') {
                        errx(EXIT_FAILURE, "Invalid input in \"%s\""
                                "at position %ld.  Unexpected value: '%c'",
                                *argv, end - *argv, *end);
                }
        }
        strncpy(exp->operators, "++++++++++++++++++++", exp->count - 1);
        exp->operators[exp->count] = '\0';
        exp->mask = (( 0x1 << ( exp->count - 1 )) - 1);
        exp->mask = next_mask(exp->mask);
        exp->operands = exp->operands;
        exp->stack = xmalloc( exp->count * sizeof *exp->stack);
}

void *
xmalloc(size_t s)
{
        void *r = malloc(s);
        if(r == NULL) {
                err(EXIT_FAILURE, "malloc");
        }
        return r;
}

Answer 3

Je vais utiliser n au lieu de 6 pour rendre l'exercice un peu plus général (j'ajouterai une note expliquant pourquoi ci-dessous), cela créera toutes les équations possibles, vous devrez créer un analyseur d'équation qui résoudra ces équations par la règle BODMAS.

1. entrée n de l'utilisateur
2. créer un tableau de n nombres => entrées
3. saisir tous les éléments
4. créer un tableau de 2^(2 * n - 1) chaînes de caractères => sorties
5. for i = 0 to 2^(2 n - 1) (total combinations) outputs[i] = "";
   for j = 0 to n if (i && 2^(j+1) != 0) if (i && 2^j != 0) outputs[i] += ("" + inputs[j]) else outputs[i] += ("/" + inputs[j]) else if (i && 2^j != 0) outputs[i] += ("+" + inputs[j]) else outputs[i] += ("-" + inputs[j])

Mon idée est basée sur la représentation binaire d'un nombre, votre réponse aurait 2^(2 * n - 1) nombres et la représentation binaire de tous les nombres de 0 à 2^(2 * n - 1) sera toutes les combinaisons. 2 bits aux positions 2n et 2n + 1 représentent un signe pour le nombre à la nième position (00 => -, 01=> +, 10=> / et 11=> *). Je n'arrive pas à trouver un moyen d'ajouter des parenthèses. Vous pouvez ajouter une boucle 2^n autour de cela pour fournir toutes les permutations de nombres au tableau d'entrée. Je soustrais 1 dans 2^(2 * n - 1) parce que les signes de / et * n'ont pas leur place au début.

Edit : Un autre moyen (/meilleur) auquel je pense serait d'utiliser la récursion pour construire toutes les combinaisons possibles sous forme d'équations et de les résoudre à la fin.

Construire tous les sous-ensembles possibles dans tous les ordres possibles quelque chose comme ceci (pour k = 1 à n) https://www.geeksforgeeks.org/print-all-combinations-of-given-length/

Answer 4

Voici une solution simple pour imprimer et évaluer toutes les combinaisons des 4 opérateurs + , - , * y / entre les chiffres. Pour ce code, tous les opérateurs ont la même préséance.

#include <stdio.h>
#include <stdlib.h>

void print_combination(unsigned mask, int *values, int n) {
    int x = values[0];
    printf("%d", values[0]);
    for (int i = 1; i < n; i++, mask /= 4) {
        switch (mask % 4) {
        case 0: x += values[i]; printf(" + %d", values[i]); break;
        case 1: x -= values[i]; printf(" - %d", values[i]); break;
        case 2: x *= values[i]; printf(" * %d", values[i]); break;
        case 3: x /= values[i]; printf(" / %d", values[i]); break;
        }
    }
    printf(" = %d\n", x);
}

int main(int argc, char *argv[]) {
    int n = argc - 1;
    int values[n];
    for (int i = 0; i < n; i++) {
        values[i] = strtol(argv[i + 1], NULL, 0);
    }
    for (unsigned i = 0, mask = 1U << (2 * (n - 1)); i < mask; i++) {
        print_combination(i, values, n);
    }
    return 0;
}

Voici une version plus élaborée qui traite toutes les permutations de l'ensemble des données :

#include <stdio.h>
#include <stdlib.h>

void print_combination(unsigned mask, int *values, int n) {
    int x = values[0];
    printf("%d", values[0]);
    for (int i = 1; i < n; i++, mask /= 4) {
        switch (mask % 4) {
        case 0: x += values[i]; printf(" + %d", values[i]); break;
        case 1: x -= values[i]; printf(" - %d", values[i]); break;
        case 2: x *= values[i]; printf(" * %d", values[i]); break;
        case 3: x /= values[i]; printf(" / %d", values[i]); break;
        }
    }
    printf(" = %d\n", x);
}

unsigned print_combinations(int *values, int n) {
    unsigned i, mask;
    for (i = 0, mask = 1U << (2 * (n - 1)); i < mask; i++) {
        print_combination(i, values, n);
    }
    return mask;
}

unsigned perm(const int *src, int len, int *dest, int *bits, int n) {
    if (n == len) {
        return print_combinations(dest, len);
    } else {
        unsigned count = 0;
        for (int i = 0; i < len; i++) {
            if (bits[i] == 0) {
                bits[i] = 1;
                dest[n] = src[i];
                count += perm(src, len, dest, bits, n + 1);
                bits[i] = 0;
            }
        }
        return count;
    }
}

int main(int argc, char *argv[]) {
    int n = argc - 1;
    int values[n], dest[n], bits[n];
    for (int i = 0; i < n; i++) {
        values[i] = strtol(argv[i + 1], NULL, 0);
        bits[i] = 0;
    }
    printf("%u combinations\n", perm(values, n, dest, bits, 0));
    return 0;
}