填数，算法题目

zaijzhgh

1口23口4口56口7口8口9=100；其中“口”填入“+, -, *, /”
这道题是在网上看到的，想了好久，只想出了蛮力法(就是申请一个4^7*7的二维数组，然而在填入数组的
时候却不知道怎么写循环语句...汗呀！！！)。看过一道ACM题目，类似的，不会解。不知道大家有什么想法呢
？

皇家救星

暴力穷举啊

写循环当然不够，要配合递归

皇家救星

写6重循环会被人笑死的

皇家救星

记得当年参加深信服面试时，八皇后问题就写了八重循环

想起来就尴尬

nslk

数据结构里面的搜索-回溯吧?用栈来记录符号,递归回去...

iptton

没人给个代码吗？
有分加

皇家救星

1*23*4+56/7+8/9=100
1*23*4-56/7/8+9=100
1*23+4+56/7*8+9=100
1/23*4*56/7*8*9=100
1+23*4+56/7*8/9=100
1+23*4+56/7+8-9=100
1+23*4+56/7-8/9=100
1+23-4+56/7+8*9=100
1+23-4+56+7+8+9=100

皇家救星

#include <iostream>
#include <time.h>
using namespace std;

#define SIZE 100 //栈最大长度
#define OPR_LENGTH 6 //操作符个数
#define RESULT 100 //等式右边
#define OPR_TYPE_LENGTH 4 //操作符种类个数

double num_stack[SIZE]; //数字栈
char opr_stack[SIZE]; //操作符栈
int num_top = 0, opr_top = 0; //栈顶指针

char oprs[OPR_LENGTH + 1]; //存放操作符，一个单元格代表一个“口”
double numbers[OPR_LENGTH + 1] = {1, 23, 4, 56, 7, 8, 9}; //按顺序存放操作数
char opr_types[OPR_TYPE_LENGTH] = {'*', '/', '+', '-'}; //+ - * /

int run(); //主函数，递归用，作用是往“口”里面填操作符
int get_res(); //通过oprs和numbers获得结果
int compare(char opr1, char opr2); //比较两个操作符大小，opr1 > opr2 则返回1，opr1 = opr2　则返回0，　否则返回-1
int print(); //输出结果
double count(double left, char opr, double right); // 返回　a口b 的结果 具体原理见数据结构



int get_res() //计算表达式结果
{
        //栈初始化
        num_top = 0;
        opr_top = 0;

        double result = 0;
        int i = 0; //i 当前处理的操作符

        num_stack[num_top++] = numbers[0]; //第一个操作数进栈
        oprs[OPR_LENGTH] = '#'; //用#标志结束
        opr_stack[opr_top++] = '#'; //用#标志开始

        while (opr_top != 0 || i < OPR_LENGTH)
        {
                int cmp = compare(opr_stack[opr_top - 1], oprs[ i ]);
                if (cmp < 0)  //栈空或者栈顶元素操作符低
                {
                        num_stack[num_top++] = numbers[i+1];
                        opr_stack[opr_top++] = oprs[ i ];        
                        i++;//继续处理下一个操作符
                }
                else if (cmp > 0) //如果小于则，退栈计算
                {
                        char the_opr = opr_stack[--opr_top];
                        double right_num = num_stack[--num_top];        
                        double left_num = num_stack[--num_top];
                        
                        num_stack[num_top++] = count(left_num, the_opr, right_num);
                }
                else //否则，退栈
                {
                        --opr_top;
                }
        }
        result = num_stack[num_top - 1];
        //print();
        //cout << result << endl;
        return result;
}


int print()
{
        int i;
        for (i = 0; i < OPR_LENGTH; i++)
        {
                cout << numbers[ i ] << oprs[ i ] ;
        }
        cout << numbers[ i ] << "=" << RESULT << endl;

        return 0;
}

int run(int pos)
{
        if (pos == OPR_LENGTH)
        {
                double res = get_res() -RESULT;
                if (res >= -0.0001 && res <= 0.0001) //浮点数不能精确比较
                {
                        print();
                }
        }
        else
        {
                for (int i = 0; i < OPR_TYPE_LENGTH; i++)
                {
                        oprs[pos] = opr_types[ i ];
                        run(pos + 1);
                }
        }

        return 0;
}

double count(double left, char opr, double right)
{
        //cout << left << opr << right << endl;
        double result;
        switch(opr)
        {
        case '*':  result = left * right; break;
        case '/':  result = left / right; break;
        case '+':  result = left + right; break;
        case '-':  result = left - right; break;
        }
        return result;
}


int compare(char opr1, char opr2)
{
        if (opr1 == '*' || opr1 == '/') //乘除法优先级最高
        {
                return 1;
        }
        else if (opr1 == '+' || opr1 == '-')
        {
                if (opr2 == '*' || opr2 == '/') //加减法优先级小于乘除法
                {
                        return -1;
                }
                else
                {
                        return 1;
                }        
        }
        else
        {
                if (opr2 == '#')
                {
                        return 0;
                }
                else
                {
                        return -1;
                }
        }
}


int main(int argc,char *argv[])
{
   run(0);
   
   return 0;
}


有代码的地方注意 [ i ] 下标会如果没有空格格开会被解析为斜体确良
                                      --edit by iptton  

皇家救星

不知道能加多少分呢

皇家救星

晕，精度有点问题

不过算法基本思路差不多是这样了

haoxinqinga

8# 皇家救星
嗯，有空要看一下

kids

dp解都行
按计算符号 枚举的状态
总共 4^6种状态

贪心也行
搜索，也可以做，直接暴力吧孩子

DieIng

dp[ i ][ j ]==1代表前i个能取得为j的值~
再开多个状态记录是怎么得到这个值的
应该就行了吧~