¿Modificar un número dado para encontrar la suma requerida?

Question

Un amigo mío me envió esta pregunta. Realmente no he podido encontrar ningún tipo de algoritmo para resolver este problema.

Se le proporciona un no. diga 123456789 y dos operadores * and +. Ahora sin cambiar la secuencia del no proporcionado. y el uso de estos operadores tantas veces como desee, evaluar el valor dado:

por ejemplo: dado un valor 2097
Solución: 1+2+345*6+7+8+9

Cualquier ideas sobre cómo abordar problemas como estos?

Answer 1

no hay que muchas soluciones - este programa Python toma menos de un segundo al ataque de fuerza bruta a todos

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) 

Aquí está una muestra de ejecución a través de 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 

solución general es una simple modificación

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

Una de las formas más sencillas de hacerlo es utilizando la expansión de shell en 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 

que da:

 
$ 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

Ésta no es la forma más fácil, pero traté de escribir "optimizado" código: electrógeno todos los (n-1)^3 cuerdas es caro , y debes evaluar muchos de ellos; Todavía solía fuerza bruta, pero el corte "subárboles" improductivos (y la fuente es C, como se pide en el título)

#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

Aquí es una implementación de un no-recursivo C versión de fuerza bruta que funcionará para cualquier conjunto de dígitos (con valores razonables en el rango de 32 bits y no solo en el ejemplo anterior). Ahora complete. :)

#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

Se podría trabajar hacia atrás y tratar de probar todas las posibilidades que podrían dar solución;

por ejemplo:

1 (something) 9 = 10 

1*9=10 - false 

1/9=10 - false 

1-9=10 - false 

1+9=10 - True 

fuerza Así que, básicamente bruta - pero es reutilizable código dado que la entrada podría ser diferente.