Ändern Sie eine bestimmte Zahl, um die erforderliche Summe zu finden?

Ein Freund von mir hat mir diese Frage geschickt. Ich bin nicht wirklich in der Lage gewesen, irgendeinen Algorithmus zu finden, um dieses Problem zu lösen.

Sie erhalten ein Nein. sagen 123456789 und zwei Operatoren * and +. Jetzt ohne die Reihenfolge der bereitgestellten Nr. zu ändern. und verwenden Sie diese Operatoren so oft Sie möchten, werten Sie den angegebenen Wert aus:

zB: gegebener Wert 2097

Lösung: 1+2+345*6+7+8+9

Irgendwelche Ideen, wie man solche Probleme angeht?

Eine der einfachsten Möglichkeiten, dies zu tun, ist die Verwendung der Shell-Erweiterung in BASH:

#!/bin/sh

for i in 1{,+,*}2{,+,*}3{,+,*}4{,+,*}5{,+,*}6{,+,*}7{,+,*}8{,+,*}9; do
    if [ $(( $i )) == 2097 ]; then
        echo $i = 2097
    fi
done

was ergibt:

$ sh -c '. ./testequation.sh'
12*34+5*6*7*8+9 = 2097
12*3*45+6*78+9 = 2097
1+2+345*6+7+8+9 = 2097

Es gibt nicht so viele Lösungen – dieses Python-Programm braucht weniger als eine Sekunde, um sie alle brutal zu erzwingen

from itertools import product

for q in product(("","+","*"), repeat=8):
    e="".join(i+j for i,j in zip('12345678',q))+'9'
    print e,'=',eval(e)

Hier ist ein Beispiel, das grep durchläuft

$ python sums.py | grep 2097
12*34+5*6*7*8+9 = 2097
12*3*45+6*78+9 = 2097
1+2+345*6+7+8+9 = 2097

Allgemeine Lösung ist eine einfache Modifikation

from itertools import product

def f(seq):
    for q in product(("","+","*"), repeat=len(seq)-1):
        e="".join(i+j for i,j in zip(seq[:-1],q))+seq[-1]
        print e,'=',eval(e)

Dies ist nicht der einfachste Weg, aber ich habe versucht, “optimierten” Code zu schreiben: Das Generieren aller 3^(n-1) Zeichenfolgen ist teuer, und Sie müssen viele von ihnen auswerten; Ich habe immer noch Bruteforce verwendet, aber unproduktive “Teilbäume” geschnitten (und die Quelle ist C, wie im Titel gefordert)

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "math.h"

#define B 10

void rec_solve(char *, char *, int, char, int, char, int, char *);

int main(int argc, char** argv) {
    char *n, *si = malloc(0);
    if (argc < 2) {
        printf("Use : %s num sum", argv[0]);
    } else {
        n = calloc(strlen(argv[1]), sizeof (char));
        strncpy(n, argv[1], strlen(argv[1]));
        rec_solve(n, si, 0, '+', 0, '+', atoi(argv[2]), n);
    }
    return 0;
}

void rec_solve(char *str, char *sig, int p, char ps, int l, char ls, int max, char *or) {
    int i, len = strlen(str), t = 0, siglen = strlen(sig), j, k;
    char *mul;
    char *add;
    char *sub;

    if (p + l <= max) {
        if (len == 0) {
            k = (ls == '+') ? p + l : p*l;

            if ((k == max) && (sig[strlen(sig) - 1] == '+')) {
                for (i = 0; i < strlen(or) - 1; i++) {
                    printf("%c", or[i]);
                    if (sig[i] && (sig[i] != ' '))
                        printf("%c", sig[i]);
                }
                printf("%c\n", or[i]);
            }
        } else {
            for (i = 0; i < len; i++) {
                t = B * t + (str[i] - '0');

                if (t > max)
                    break;

                sub = calloc(len - i - 1, sizeof (char));
                strncpy(sub, str + i + 1, len - i - 1);

                mul = calloc(siglen + i + 1, sizeof (char));
                strncpy(mul, sig, siglen);

                add = calloc(strlen(sig) + i + 1, sizeof (char));
                strncpy(add, sig, siglen);

                for (j = 0; j < i; j++) {
                    add[siglen + j] = ' ';
                    mul[siglen + j] = ' ';
                }

                add[siglen + i] = '+';
                mul[siglen + i] = '*';

                switch (ps) {
                    case '*':
                        switch (ls) {
                            case '*':
                                rec_solve(sub, add, p*l, '*', t, '+',max, or);
                                rec_solve(sub, mul, p*l, '*', t, '*',max, or);
                                break;
                            case '+':
                                rec_solve(sub, add, p*l, '+', t, '+',max, or);
                                rec_solve(sub, mul, p*l, '+', t, '*',max, or);
                                break;
                        }
                    case '+':
                        switch (ls) {
                            case '*':
                                rec_solve(sub,add,p, '+',l*t,'+',max, or);
                                rec_solve(sub,mul,p, '+',l*t,'*',max, or);
                                break;
                            case '+':
                                rec_solve(sub,add,p + l,'+',t,'+',max, or);
                                rec_solve(sub,mul,p + l,'+',t,'*',max, or);
                                break;
                        }
                        break;
                }
            }
        }
    }
}

Hier ist eine Implementierung einer nicht-rekursiven C Bruteforce-Version, die für jeden Ziffernsatz funktioniert (mit vernünftigen Werten im 32-Bit-Bereich und nicht nur für das obige Beispiel). Jetzt vollständig. 🙂

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

/* simple integer pow() function */
int pow(int base, int pow)
{
    int i, res = 1;
    for (i = 0; i < pow; i++)
        res *= base;
    return res;
}

/* prints a value in base3 zeropadded */
void zeropad_base3(int value, char *buf, int width)
{
    int length, dif;

    _itoa(value, buf, 3);
    length = strlen(buf);
    dif = width - length;

    /* zeropad the rest */
    memmove(buf + dif, buf, length+1);
    if (dif)
        memset(buf, '0', dif);
}

int parse_factors(char **expr)
{
    int num = strtol(*expr, expr, 10);
    for ( ; ; )
    {
        if (**expr != '*')
            return num;
        (*expr)++;
        num *= strtol(*expr, expr, 10);
    }
}

/* evaluating using recursive descent parser */
int evaluate_expr(char* expr)
{
    int num = parse_factors(&expr);
    for ( ; ; )
    {
        if (*expr != '+')
            return num;
        expr++;
        num += parse_factors(&expr);
    }
}

void do_puzzle(const char *digitsString, int target)
{
    int i, iteration, result;
    int n = strlen(digitsString);
    int iterCount = pow(3, n-1);
    char *exprBuf = (char *)malloc(2*n*sizeof(char));
    char *opBuf = (char *)malloc(n*sizeof(char));

    /* try all combinations of possible expressions */
    for (iteration = 0; iteration < iterCount; iteration++)
    {
        char *write = exprBuf;

        /* generate the operation "opcodes" */
        zeropad_base3(iteration, opBuf, n-1);

        /* generate the expression */
        *write++ = digitsString[0];
        for (i = 1; i < n; i++)
        {
            switch(opBuf[i-1])
            {
            /* case '0' no op */
            case '1': *write++ = '+'; break;
            case '2': *write++ = '*'; break;
            }
            *write++ = digitsString[i];
        }
        *write="\0";

        result = evaluate_expr(exprBuf);
        if (result == target)
            printf("%s = %d\n", exprBuf, result);
    }

    free(opBuf);
    free(exprBuf);
}

int main(void)
{
    const char *digits = "123456789";
    int target = 2097;
    do_puzzle(digits, target);
    return 0;
}

12*34+5*6*7*8+9 = 2097
12*3*45+6*78+9 = 2097
1+2+345*6+7+8+9 = 2097

Sie könnten rückwärts arbeiten und versuchen, alle Möglichkeiten zu testen, die eine Lösung bieten könnten;

z.B:

1 (something) 9 = 10

1*9=10 - false

1/9=10 - false

1-9=10 - false

1+9=10 - True

Also im Grunde Brute Force – aber es ist wiederverwendbarer Code, da die Eingabe unterschiedlich sein kann.