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

algorithm math

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. digamos 123456789 y dos operadores * and + . Ahora sin cambiar la secuencia del no proporcionado. y utilizando estos operadores tantas veces como desee, evalúe el valor dado:

ej .: valor dado 2097
Solución: 1+2+345*6+7+8+9

¿Alguna idea sobre cómo abordar problemas como estos?

Answer 1

Aquí hay una implementación de una versión no recursiva de C bruteforce que funcionará para cualquier conjunto de dígitos (con valores razonables en el rango de 32 bits y no solo para 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 2

Esta no es la forma más fácil, pero intenté escribir el código "optimizado": generar todas las cadenas 3 ^ (n-1) es costoso y hay que evaluar muchas de ellas; Todavía usé fuerza bruta, pero corté "subárboles" improductivos (y la fuente es C, como se solicita 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 3

No hay tantas soluciones: este programa de Python requiere menos de un segundo para obligarlos 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í hay una muestra ejecutada 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

La 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 4

Podría trabajar hacia atrás e intentar probar todas las posibilidades que podrían brindar una solución;

p.ej:

1 (something) 9 = 10

1*9=10 - false

1/9=10 - false

1-9=10 - false

1+9=10 - True

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

Answer 5

Una de las maneras más fáciles de hacerlo es mediante la expansión de shell en 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

lo 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