n个数进行加减乘除得到m

Question

小于四个的数还可以用穷举法，还是比较简单。n比较大的时候就行不通了，这个时候我考虑到了用递归的方法。就是从这n个数中取两个进行加减乘除，把得到的四种结果再分别和从剩余的n-2个数中的一个数再进行加减乘除。如此递归下去，直到这n个数全部进行过计算，最后看得到的结果是否等于m。我试着写了些代码，可是错得一塌糊涂。求正确的代码（c语言）。

Answer 1

是要用到全排列。范围嘛，n<=10，每个数小于等于15吧！

Answer 2

先  化简 4则运算和位置 等同情况 a+b+c-d 和 a-d+c+b  类似。

Answer 3

最好先整理出一个所为"算法结构",
这样你再用DELPHI代码实现即可

Answer 4

化简四则运算貌似行不通吧。DELPHI没有学过 。

Answer 5

三个数a,b,c进行全排列：
a,b,c;
a,c,b;
b,a,c;
b,c,a;
c,a,b;
c,b,a;
对每种排列结果最后两个数进行四则运算，如：a,b,c;
p[0]=b + c; result[0][0]=a + p[0]; result[0][1]=a-p[0];result[0][2]=a*p[0];result[0][3]=a/p[0];
p[1]=b - c; result[1][0]=a + p[1]; result[1][1]=a-p[1];result[1][2]=a*p[1];result[1][3]=a/p[1];
p[2]=b * c; result[2][0]=a + p[2]; result[2][1]=a-p[2];result[2][2]=a*p[2];result[2][3]=a/p[2];
p[3]=b / c; result[3][0]=a + p[3]; result[3][1]=a-p[3];result[3][2]=a*p[3];result[3][3]=a/p[3];
看result中有没有一个值等于m的，如果有返回yes，没有返回no。

Answer 6

和delphi 没关系。。
a-b-c 
和a -(b+c) 结果是一样的
这些是需要 做剪枝的。。 能提高一些效率。象这个问题 目标解空间一定的 主要是 搜索的时候 效率优化
。

Answer 7

"先枚举某几种形式的算式"
选择有效的方式缩小范围。。
http://topic.csdn.net/t/20020128/09/503163.html

Answer 8

to vividw:他们的思想我是基本理解了，可是他们的算法不能达到100%的精确。我这需要十分精确，耗费比较的时间和内存也是无所谓的。

Answer 9

不要求显示这n个数得到m的算术表达式，只要求判断能否得到m。

Answer 10

明白了,其实我是想倒推,如
(a+b)+? = m
? = m - a - b
检索一下除a,b外是否有这个?,如果有就yes,没有继续其他
其他运算规则一样,唯独带有除法的时候,所以要问清楚了

Answer 11

#include<iostream>
#include<fstream>
#include<sstream>
#include<vector>
#include<ctime>
#include<cmath>using std::cout;
using std::string;
using std::vector;
using std::ofstream;
using std::stringstream;class Calc {
 public:
  Calc(){};
  void print_result() const;
  bool run(const int src[], size_t sz, double n = 24.0,
           bool expr_calc = true, bool show = true);
  const string& get_expr() const { return expr;}
  size_t get_count_expr() const { return count_expr;}
  size_t get_count_func() const { return count_func;} private:
  Calc(const Calc&);
  Calc& operator=(const Calc&);
  bool init(const int src[], size_t sz, double n);
  bool calc(size_t step);
  inline bool calc2(size_t step, size_t pos2,double na, double nb, int op);
  void calc_expr();  void add_parentheses(string& str) {
    string tmp;  tmp.reserve(str.size() + 2);
    tmp += '(';  tmp += str;  tmp += ')';
    str.swap(tmp);
  }  char get_op_char(int op) { return char(op >> RSHIFT); }
  int get_opv(int op) { return op & OPV_MASK; }  //0-2位表示操作符的优先级 加减: 1 乘除2  初始值4
  //+3位，即RFLAG标志，表示对减除法，交换两个操作数后再计算
  //4-7位表示操作符，8-15位表示该操作符的ascii值
  enum {
    OP_NULL = 4, RFLAG = 8, RSHIFT = 8, OPV_MASK = 7,
    FLAG_ADD = 0x10, FLAG_SUB = 0x20, FLAG_MUL = 0x40, FLAG_DIV = 0x80,
    ADD = '+' << RSHIFT | FLAG_ADD | 1, SUB = '-' << RSHIFT | FLAG_SUB | 1,
    MUL = '*' << RSHIFT | FLAG_MUL | 2, DIV = '/' << RSHIFT | FLAG_DIV | 2,
    RSUB = SUB | RFLAG, RDIV = DIV | RFLAG,
  };  struct Info_step {              //记录每一步取两个数所进行的计算
    size_t first;                 //第一个操作数位置
    size_t second;                //第二个操作数位置
    int op;                       //操作符
  };  size_t size;
  string expr;                    //得到的表达式  double result;                  //要得到的结果值
  size_t count_expr;              //处理的表达式总数
  size_t count_func;              //函数被调用次数
  vector<int> old_number;         //要计算的数
  vector<double> number;          //中间计算结果
  vector<int> ops;               //上一次计算所用的操作符,初始值要设为OP_NULL
  vector<Info_step> info_step;
};bool Calc::init(const int src[], size_t sz, double n)
{
  if (sz == 0 || src == NULL) return false;
  size = sz;
  expr.clear();
  result = n;
  count_expr = 0;
  count_func = 0;
  old_number.assign(src, src + sz);
  number.assign(src, src+sz);
  ops.assign(sz, OP_NULL);
  info_step.clear();
  info_step.resize(sz);
  return true;
}bool Calc::run(const int src[], size_t sz, double n, bool expr_calc, bool show)
{
  if (! init(src, sz, n)) return false;
  bool ret = calc(sz);
  if (ret && expr_calc) calc_expr();
  if (show) print_result();
  return ret;
}
void Calc::calc_expr()
{
  const size_t sz =  size;
  static vector<string> str;
  static vector<int> op_prev;
  static stringstream ss;
  str.resize(sz);
  op_prev.assign(sz,OP_NULL);    //初始值
  for (size_t i = 0; i < sz; ++i) {
    ss << old_number[i];
    getline(ss, str[i]);
    ss.clear();
  }
  for (size_t k = sz; k-- > 1; ) {
    size_t i = info_step[k].first;
    size_t j = info_step[k].second;
    int op = info_step[k].op;
    int opv= get_opv(op);
    int op1v, op2v;
    if (op & RFLAG) {
      str[i].swap(str[j]);
      op1v = get_opv(op_prev[j]);
      op2v = get_opv(op_prev[i]);
    } else {
      op1v = get_opv(op_prev[i]);
      op2v = get_opv(op_prev[j]);
    }    if (opv > op1v) add_parentheses(str[i]);
    if (opv > op2v || (opv == op2v && (op & (FLAG_SUB | FLAG_DIV))))
      add_parentheses(str[j]);
    op_prev[i] = op;
    op_prev[j] = op_prev[k];
    str[i].reserve(str[i].size() + str[j].size() + 1);
    str[i] += get_op_char(op);
    str[i] += str[j];
    str[j].swap(str[k]);
  }
  expr.swap(str[0]);
}bool Calc::calc(size_t step)
{
  ++count_func;
  if (step <= 1) {
    ++count_expr;
    const double zero = 1e-9;
    if (fabs(result - number[0]) < zero) return true;
    return false;
  }
  --step;
  for (size_t i = 0; i < step; i++){
    info_step[step].first = i;
    for(size_t j = i + 1; j <= step; j++) {
      info_step[step].second = j;
      double na = number[i];
      double nb = number[j];
      int op1 = ops[i];
      int op2 = ops[j];
      number[j] = number[step];
      ops[j] = ops[step];
      int tt = op1 | op2;
      bool ba = true, bb = true;
      if (tt & FLAG_SUB) ba = false;
      if (tt & FLAG_DIV) bb = false;      if (ba) {
        if (calc2(step, i, na, nb, ADD)) return true;
        if (nb != 0 && calc2(step, i, na, nb, SUB)) return true;
        if (na != nb && na != 0 && calc2(step, i, na, nb, RSUB)) return true;
      }      if (bb) {
        double nmul = na * nb;
        if (calc2(step, i, na, nb, MUL)) return true;
        if (na != 0 && nb !=0) {
          double ndiv = na / nb;
          if (nmul != ndiv && calc2(step,i,na, nb, DIV)) return true;
          double nrdiv = nb / na;
          if (nrdiv != ndiv && nrdiv != nmul && calc2(step,i,na, nb, RDIV))
            return true;
        }
      }
      number[i] = na;
      number[j] = nb;
      ops[i] = op1;
      ops[j] = op2;
    }
  }
  return false;
}inline bool Calc::calc2(size_t step, size_t pos2,double na,double nb, int op)
{
  info_step[step].op = op;
  ops[pos2] = op;
  switch (op) {
    case ADD:   number[pos2] = na + nb; break;
    case SUB:   number[pos2] = na - nb; break;
    case MUL:   number[pos2] = na * nb; break;
    case DIV:   number[pos2] = na / nb; break;
    case RSUB:  number[pos2] = nb - na; break;
    case RDIV:  number[pos2] = nb / na; break;
    default : break;
  }
  return calc(step);
}void Calc::print_result() const
{
  if (old_number.empty()) return;
  cout << "number: ";
  for (size_t i = 0; i < old_number.size(); ++i)
    cout << old_number[i] << " ";
  cout << "\n";
  if (! expr.empty()) std::cout << "result: YES\n";
  if(expr.empty())std::cout<<"result:NO\n";
}int main()
{
  Calc calc;
  int i,N,r[100];
  scanf("%d",&N);
  for(i=0;i<N;++i)
  {
      scanf("%d",&r[i]);
  }
  calc.run(r,N);
}我从网上找了个c++版的，略作修改过。运行正确着。可我还没学c++，谁能帮我改成c语言版的。