Zmienić podaną liczbę, aby znaleźć żądaną kwotę?

Question

Mój przyjaciel przysłał mi to pytanie. Tak naprawdę nie byłem w stanie wymyślić żadnego algorytmu, który rozwiązałby ten problem.

Otrzymujesz nr. powiedz 123456789 i dwóch operatorów * and +. Teraz bez zmiany sekwencji podanego nr. i za pomocą tych operatorów tyle razy, ile chcesz, ocenić daną wartość:

np: podana wartość 2097
Rozwiązanie: 1+2+345*6+7+8+9

pomysłów, w jaki sposób podejść do problemów, takich jak te?

Answer 1

Są nie że wiele rozwiązań - program python bierze pod drugą do Bruteforce im wszystko

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) 

Oto przebieg próbki przez 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 

rozwiązanie ogólne jest prosta modyfikacja

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

Jednym z najprostszych sposobów na to jest użycie rozszerzenia powłoki w systemie 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 

co daje:

 
$ 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

nie jest najprostszym sposobem, ale próby zapisu "zoptymalizowany" Kod: genereting wszystkie 3^(n-1) jest drogie sznurki i musisz ocenić wiele z nich; I nadal używane Bruteforce, ale cięcia nieproduktywne „poddrzewa” (i źródłem jest C, zgodnie z wnioskiem w tytule)

#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

Oto wdrożenie non-rekurencyjne C wersji Bruteforce że będzie pracować dla dowolnego zestawu cyfr (z rozsądnymi wartościami w zakresie 32-bitowym, a nie tylko dla powyższego przykładu). Teraz ukończ. :)

#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

Można działać wstecz i spróbować przetestować wszystkie możliwości, które może dać rozwiązanie;

np:

1 (something) 9 = 10 

1*9=10 - false 

1/9=10 - false 

1-9=10 - false 

1+9=10 - True 

siła Więc zasadniczo brute - ale to jest do ponownego użycia kodu podano, że wejście może być inna.