Eine gegebene Zahl ändern, um die erforderliche Summe zu finden?

Question

Ein Freund von mir schickte mir diese Frage. Ich war nicht wirklich in der Lage, irgendeinen Algorithmus zur Lösung dieses Problems zu finden.

Sie sind mit einer Nr. sagen 123456789 und zwei Operatoren * and +. Jetzt ohne Änderung der Reihenfolge der zur Verfügung gestellten Nr. und die Verwendung dieser Operatoren so oft wie Sie es wünschen, bewerten den angegebenen Wert:

zB: gegebenen Wert 2097
Lösung: 1+2+345*6+7+8+9

Irgendwelche Ideen auf, wie man Probleme wie diese zu nähern?

Answer 1

Es gibt nicht so viele Lösungen - das Python-Programm unter einer Sekunde nimmt sie alle hier

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) 

zu Brute-Force ist ein Probelauf durch grep

$ 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) 

Answer 2

Eine der einfachsten Möglichkeiten ist die Verwendung der Shell-Erweiterung in BAS H:

 
#!/bin/sh 

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

die gibt:

 
$ 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 

Answer 3

Dies ist nicht der einfachste Weg, aber ich habe versucht zu schreiben "optimiert" Code: genereting alle 3^(n-1) Strings ist teuer und du musst viele von ihnen bewerten; Ich noch Brute-Force eingesetzt, sondern schneide unproduktiv „Zweige“ (und die Quelle C, wie im Titel angefordert)

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

Answer 4

Hier ist eine Implementierung einer nicht-rekursive C Brute-Force-Version, die für jede Menge arbeiten von Ziffern (mit vernünftigen Werten im 32-Bit-Bereich und nicht nur für das obige Beispiel). Jetzt fertig. :)

#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 

Answer 5

Sie könnten rückwärts arbeiten und versuchen, alle Möglichkeiten zu prüfen, die Lösung geben könnte;

z:

1 (something) 9 = 10 

1*9=10 - false 

1/9=10 - false 

1-9=10 - false 

1+9=10 - True 

Also, im Grunde rohe Gewalt - aber es ist wiederverwendbar Code gegeben, dass die Eingabe anders sein könnte.