Изменить данное число, чтобы найти необходимую сумму?

Question

Мой друг прислал мне этот вопрос.Я действительно не смог придумать какой-либо алгоритм для решения этой проблемы.

Вам предоставляется "нет".скажем 123456789 и два оператора * and +.Теперь без изменения последовательности предоставления нет.и используя эти операторы столько раз, сколько вы пожелаете, оцените данное значение:

например: данное значение 2097
Решение: 1+2+345*6+7+8+9

Любые идеи о том, как подходить к проблемамкак это?

Answer 1

Один из самых простых способов сделать это - использовать расширение оболочки в 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

, что дает:

$ <b>sh -c '. ./testequation.sh'</b>
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

Существует не так много решений - этой программе на python требуется всего одна секунда, чтобы все их обработать

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)

Вот пример прогона 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

Общее решение - этопростая модификация

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 3

Вот реализация нерекурсивной версии C bruteforce, которая будет работать для любого набора цифр (с разумными значениями в 32-битном диапазоне, а не только для примера выше).Теперь завершено.:)

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

Это не самый простой способ, но я попытался написать «оптимизированный» код: генерация всех 3 ^ (n-1) строк стоит дорого, и вы должны оценить многие из них; Я все еще использовал брутфорс, но резал непродуктивные «поддеревья» (а источник - C, как и требовалось в заголовке)

#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 5

Вы можете работать в обратном направлении и пытаться проверить все возможности, которые могут дать решение;

Например:

1 (something) 9 = 10

1*9=10 - false

1/9=10 - false

1-9=10 - false

1+9=10 - True

Итак, в основном грубая сила - но это код многократного использования, учитывая, что ввод может быть другим.