Modificare un dato numero per trovare la somma richiesta?

Question

Una mia amica mi ha inviato questa domanda. Non sono stato in grado di trovare alcun tipo di algoritmo per risolvere questo problema.

Si dispone di un n. dì 123456789 e due operatori * and +. Ora senza cambiare la sequenza del no fornito. e l'utilizzo di questi operatori tutte le volte che lo si desidera, di valutare il valore dato:

esempio: dato valore 2097
Soluzione: 1+2+345*6+7+8+9

Tutte le idee su come affrontare problemi come questi?

Answer 1

non ci sono che molte soluzioni - questo programma Python prende meno di un secondo per bruteforzare tutti

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) 

Qui è una corsa campione attraverso 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 

soluzione generale è una modifica semplice

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

Uno dei modi più semplici per farlo è utilizzare l'espansione della shell 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 

che assicura:

 
$ 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

Questo non è il modo più semplice, ma ha tentato di scrivere codice "ottimizzato": genereting tutte le^(n-1) stringhe 3 è costoso e devi valutarne molti; Ho ancora usato bruteforce, ma il taglio "sottoalberi" improduttivi (e la fonte è C, come richiesto nel titolo)

#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

Ecco un'implementazione di un non-ricorsiva C versione bruteforce che funzionerà per ogni insieme di cifre (con valori ragionevoli nell'intervallo di 32 bit e non solo per l'esempio sopra). Ora completo. :)

#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

Si potrebbe procedere a ritroso e provare a verificare tutte le possibilità che potrebbero dare soluzione;

es:

1 (something) 9 = 10 

1*9=10 - false 

1/9=10 - false 

1-9=10 - false 

1+9=10 - True 

forza Quindi, fondamentalmente bruta - ma è riutilizzabile codice dato che l'ingresso potrebbe essere differente.