Изменить данное число, чтобы найти необходимую сумму?
Мой друг прислал мне этот вопрос. Я действительно не смог придумать какой-либо алгоритм для решения этой проблемы.
Вам предоставляется нет. сказать 123456789 и два оператора * and +, Теперь без изменения последовательности предоставления нет. и используя эти операторы столько раз, сколько вы хотите, оцените данное значение:
например: данное значение 2097
Решение: 1+2+345*6+7+8+9
Любые идеи о том, как подходить к таким проблемам?
5 ответов
Один из самых простых способов сделать это - использовать расширение оболочки в BASH:
#! / bin / sh для i в 1 {, +, *} 2 {, +, *} 3 {, +, *} 4 {, +, *} 5 {, +, *} 6 {, +, * * } {7, + *} 8 {+,*}9; do
if [ $(( $i)) == 2097 ]; тогда эхо $ i = 2097 который дает:
$ 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
Решений не так много - этой программе на 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)
Это не самый простой способ, но я попытался написать "оптимизированный" код: генерация всех 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;
}
}
}
}
}
Вот реализация нерекурсивной версии 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
Вы можете работать в обратном направлении и пытаться проверить все возможности, которые могут дать решение;
например:
1 (something) 9 = 10
1*9=10 - false
1/9=10 - false
1-9=10 - false
1+9=10 - True
Итак, в основном грубая сила - но это код многократного использования, учитывая, что ввод может быть другим.