zaijzhgh 发表于 2008-9-27 19:35

填数，算法题目

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

皇家救星 发表于 2008-9-27 23:10

暴力穷举啊

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

皇家救星 发表于 2008-9-27 23:12

写6重循环会被人笑死的

皇家救星 发表于 2008-9-27 23:14

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

想起来就尴尬

nslk 发表于 2009-3-25 22:28

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

iptton 发表于 2009-3-26 10:37

没人给个代码吗？
有分加

皇家救星 发表于 2009-3-26 23:55

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

皇家救星 发表于 2009-3-26 23:56

本帖最后由 iptton 于 2009-3-28 10:03 编辑

#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; //数字栈
char opr_stack; //操作符栈
int num_top = 0, opr_top = 0; //栈顶指针

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

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 = numbers; //第一个操作数进栈
      oprs = '#'; //用#标志结束
      opr_stack = '#'; //用#标志开始

      while (opr_top != 0 || i < OPR_LENGTH)
      {
                int cmp = compare(opr_stack, oprs[ i ]);
                if (cmp < 0)//栈空或者栈顶元素操作符低
                {
                        num_stack = numbers;
                        opr_stack = 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 = count(left_num, the_opr, right_num);
                }
                else //否则，退栈
                {
                        --opr_top;
                }
      }
      result = num_stack;
      //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 = 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

皇家救星 发表于 2009-3-26 23:59

不知道能加多少分呢

皇家救星 发表于 2009-3-27 00:06

晕，精度有点问题

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

haoxinqinga 发表于 2009-3-28 01:13

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

kids 发表于 2009-4-1 22:26

本帖最后由 kids 于 2009-4-2 22:05 编辑

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

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

DieIng 发表于 2009-4-3 14:14

本帖最后由 DieIng 于 2009-4-3 14:18 编辑

dp[ i ][ j ]==1代表前i个能取得为j的值~
再开多个状态记录是怎么得到这个值的
应该就行了吧~
页: [1]
查看完整版本: 填数，算法题目