主题：【原创】将24进行到底 -- 泰让

共:💬28 🌺15 新:

老视野待整

分页树展主题 · 全看下页

家园
【原创】将24进行到底
这是答应过面壁同学的c原码，因为周末在玩新买的电视，加上犯懒，所以晚了.
稍后将给出算法的解释.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define TAGET 24
#define NOP 4
#define EOP NOP*2-1
int comp[EOP];
double op[NOP];
int validate(void ){
int top=0;
double stack[NOP];
int i=0;
for (i=0;i<EOP;i++) {
if (comp[i]<=NOP) {
stack[top]=op[comp[i]-1];
top++;
} else {
switch (comp[i]-NOP) {
case 1:
top--;
stack[top-1]+=stack[top];
break;
case 2:
top--;
stack[top-1]-=stack[top];
break;
case 3:
top--;
stack[top-1]*=stack[top];
break;
case 4:
top--;
if (stack[top]==0)
return 0;
stack[top-1]/=stack[top];
break;
}
}
}
if (fabs(stack[0]-TAGET)<=1e-5)
return 1;
else
return 0;
}
void output(void ) {
int i;
int top=0;
char* stack[EOP];
char tempstr[255];
for (i=0;i<EOP;i++) {
stack[i]=malloc(255*sizeof(char));
}
for (i=0;i<EOP;i++) {
if (comp[i]<=NOP) {
sprintf(stack[top]," %d ",(int)op[comp[i]-1]);
top++;
} else {
switch (comp[i]-NOP) {
case 1:
top--;
sprintf(tempstr,"(%s+%s)",stack[top-1],stack[top]);
strcpy(stack[top-1],tempstr);
break;
case 2:
top--;
sprintf(tempstr,"(%s-%s)",stack[top-1],stack[top]);
strcpy(stack[top-1],tempstr);
break;
case 3:
top--;
sprintf(tempstr,"(%s*%s)",stack[top-1],stack[top]);
strcpy(stack[top-1],tempstr);
break;
case 4:
top--;
sprintf(tempstr,"(%s/%s)",stack[top-1],stack[top]);
strcpy(stack[top-1],tempstr);
break;
}
}
}
printf("%s\n",stack[0]);
for (i=0;i<EOP;i++) {
free(stack[i]);
}
}
int expandable(int i, int j){
int repeat=0;
int k;
if (j<=NOP) {
repeat=0;
for (k=0;k<=i-1;k++)
if (comp[k]==j) {
return 0;
}
}
int op=0;
int act=0;
for (k=0;k<=i-1;k++) {
if (comp[k]<=NOP)
op++;
else
act++;
if (op<act)
return 0;
}
return 1;
}
void expand(int i) {
int j;
if (i==EOP){
if (validate())
output();
}
else {
for (j=1;j<=NOP+4;j++) {
if (expandable(i+1,j)==1) {
comp[i]=j;
expand(i+1);
}
}
}
}
int main(int argc,char **argv) {
int a;
int i;
for (i=0;i<=(NOP-1);i++) {
scanf("%d",&a);
op[i]=a;
}
expand(0);
}

本帖一共被 1 帖引用 (帖内工具实现)
- 空循环会被编译器优化掉
- 复【原创】将24进行到底
  家园 俺的程序惨不忍睹
  忙活了一个星期天，参照highway兄得输出办法，终于把输出解决了，但程序已经惨不忍睹。早知花上一个周末，还不如把逆波兰表达式吃透。不敢再玩了，就先这样吧。这个程序如果没有输出的问题，我认为这个算法还是很不错的。4个数两两相运算，变成3个数，再两两相运算，变成2个数，最后得结果。如果没有输出，适用N个数。
  #include<iostream>
  #include<vector>
  using namespace std;
  #define N 4
  int z = 0,k1=0,k2=0;
  vector<double> Operand(4);
  vector<int> Operator(3);
  void print(vector<double> A,vector<int> op,int i);
  void PRINT(vector<double> A,vector<int> op,int i); // (a#b)#(c#d)
  void print_op(int i)
  {
  switch (i)
  {
  case 0 : cout<<" + "; break;
  case 1 : cout<<" - "; break;
  case 2 : cout<<" * "; break;
  case 3 : cout<<" / "; break;
  case 4 : cout<<" - "; break;
  case 5 : cout<<" / "; break;
  }
  }
  inline double operation(const double x,const double y,int i)
  {
  double res;
  switch (i)
  {
  case 0 : res = x + y; break;
  case 1 : res = x - y; break;
  case 2 : res = x * y; break;
  case 3 : res = x / y; break;
  case 4 : res = y - x; break;
  case 5 : res = y / x; break;
  }
  return res;
  }
  inline void rechnen(vector<double> a,int n)
  {
  if (n==2) // Rekursion end
  {
  for (int i=0;i<6;i++)
  {
  if (operation(a[0],a[1],i)==24.0)
  {
  z++;
  int k3=0; if (i>3) k3++;
  Operator[2]=i;
  print(Operand,Operator,k1+k2+k3); cout<<endl;
  break; // z.B. a+b=24, a#b(b#a)!=24
  }
  }
  }
  else
  {
  vector<double> b(n-1);
  for (int u=0;u<n;u++)
  {
  for (int v=u+1;v<n;v++)
  {
  if (n==4) { Operand[0]=a[u]; Operand[1]=a[v]; }
  if (n==3) { Operand[2]=a[v-u]; Operand[3]=a[3-v+u]; }
  // A, B, C, D
  for (int i=0,j=1;j<n-1;i++)
  { if (i!=u&&i!=v) b[j++]=a[i]; }
  // "n=4" b[1],b[2]
  // "n=3" b[1]
  for (int i=0;i<6;i++)
  {
  Operator[4-n]=i;
  // op[0], op[1]
  b[0]=operation(a[u],a[v],i);
  if (i>3) { if (n==4) k1=4; if (n==3) k2=2; }
  if (n==3&&u==1)
  // (a#b)#(c#d)
  {
  for (int i=0;i<6;i++)
  {
  if (operation(b[1],b[0],i)==24.0)
  {
  z++;
  int k3=0; if (i>3) k3++;
  Operator[2]=i;
  PRINT(Operand,Operator,k1+k2+k3);
  cout<<endl; break;
  }
  }
  }
  else rechnen(b,n-1);
  k2=0;
  if (n==4) k1=0;
  }
  }
  }
  }
  }
  int main()
  {
  while (1)
  {
  double f; vector<double> a(N);
  cout<<"give me "<<N<<" nummer, please:"<<endl;
  for (int i=0;i<N&&cin>>f;i++) a[i]=f;
  // for (int i=0;i<4;i++) cout<<a[i]<<' ';
  rechnen(a,N);
  cout<<"\nso there are "<<z<<" kinds of ideas.\n\n";
  }
  return 0;
  }
  - 复俺的程序惨不忍睹
    家园 看了N遍
    计算部分大略看明白了一些。输出部分仍没有头绪。
    先说一个小的地方，rechnen（）是递归调用，为何定义成inline?
    不知道你有没有测试过N<>4的时候的情况，我觉得可能不work,起码输出函数似乎已经定死所有的表达式型了。
    - 复看了N遍
      家园 是的，就是输出搞不定
      早知老兄要看得这么仔细，我就多写些注解了，实在对不住。我认为这个算法还过得去，去掉了交换律的冗余，1 2 3 4 5 6 这六个数只有82001个可能（当然其中还有冗余）。
      就是因为输出问题搞不定，俺才拖了这么久才贴上来请教。inline 是因为原来写的递归很慢，我一厢情愿的认为加入inline好像能快点，忘了擦去，见笑了。inline的作用是否老兄再给个俺上个小灶？
      没办法，我把4个数定为abcd，k1表示4个数时任意前俩个数运算时换了位；然后b[]用来存储3个数，k2表示3个数时任意前俩个数运算时换了位；k3表示2个数时运算时换了位。
      对了，有什么好方法定义b[n-1]? 如果有，就不用vector这个蒙人的东东啦。
      明天考试，先请教这么多啦。唉，为了上学，浪费了我多少学习的时光啊！
      #define N 6
      int z=0;
      inline double operation(const double x,const double y,int i)
      {
      double res;
      switch (i)
      {
      case 0 : res = x + y; break;
      case 1 : res = x - y; break;
      case 2 : res = x * y; break;
      case 3 : res = x / y; break;
      case 4 : res = y - x; break;
      case 5 : res = y / x; break;
      }
      return res;
      }
      void rechnen(vector<double> a,int n)
      {
      if (n==2) // rekursion end
      {
      for (int i=0;i<6;i++)
      {
      if (operation(a[0],a[1],i)==24.0)
      {
      z++;
      break; // a+b=24, a#b(b#a)!=24
      }
      }
      }
      else
      {
      vector<double> b(n-1);
      for (int u=0;u<n;u++)
      {
      for (int v=u+1;v<n;v++)
      {
      for (int i=0,j=1;j<n-1;i++)
      { if (i!=u&&i!=v) b[j++]=a[i]; }
      // "n=4" b[1],b[2]
      // "n=3" b[1]
      for (int i=0;i<6;i++)
      {
      b[0]=operation(a[u],a[v],i);
      rechnen(b,n-1);
      }
      }
      }
      }
      }
      int main()
      {
      while (1)
      {
      double f; vector<double> a(N);
      cout<<"give me "<<N<<" nummer, please:"<<endl;
      for (int i=0;i<N&&cin>>f;i++) a[i]=f;
      // for (int i=0;i<4;i++) cout<<a[i]<<' ';
      rechnen(a,N);
      cout<<"\nso there are "<<z<<" kinds of ideas.\n\n";
      }
      return 0;
      }
      - 复是的，就是输出搞不定
        家园 inline
        inline有点类似于宏定义，是说函数编译的时候不写成一般的压栈然后转移的子程序形式，而是在调用点直接插入函数代码。这样可以省下一部分保存和恢复现场的时间。代价是编译后的代码会长一些。一般inline用于比较小一点的函数。
        但是这种标定不是强制性的，编译器发现不适合做inline的时候可以按一般函数处理。对于程序中的递归，因为自身中有调用点，显然不可能做inline处理，所以是无效的。
        复 inline
        家园 哈，这下彻底清楚啦！牛！
  - 复俺的程序惨不忍睹
    家园 为什么要用double类型，难道32位的整型不够么？另外，
    print等几个函数可以用const reference传参数，比如print可以申明为：
    void print( vector< double > const& A, vector< double > const& op, int i );
    - 复为什么要用double类型，难道32位的整型不够么？另外，
      家园 整形？
      如泰让兄所说，4/7 要是整形就等于0啊！
      标准的写法参照泰让兄的：
      fabs(stack[0]-TAGET)<=1e-5
      和highway兄的：
      private static final double SMALL = 0.0000001d
      另外，"vector<T> const& A" 这种声明，呜呜，好像是指针常量，即保证此指针不能指向其它东东；还有就是指向常量的指针了，即保证所指的东东不变；最后就是指针常量指向常量了。如果对于输出N个数有用还行，没用的话，呜呜，俺反正是晕了！
      - 复整形？
        家园 关于使用整型，我忽视了需要存放除法操作的中间结果，
        虽然理论上可以把除法操作都给“消掉”。不过那样就把问题搞得太复杂了。
        在函数声明中，给形式参数加上引用符（&），比如vector< double > const &，是为了避免在传参时不必要地复制。
        加上常数修饰符（const）是让编译器在函数定义里检查出试图修改这个形参的内容的语句。在象print这样的函数里，试图修改向量的内容应该是非法操作。
        顺便说一下，如果想要防止某个引用或指针变量被重新赋值，可以这样声明：
        T* const t = & someT;
        注意常数修饰符相对于星号的位置。
        不过，这样的用法用于声明函数的形式参数没有实际意义，因为C++调用函数时，传值不传址。
    - 复为什么要用double类型，难道32位的整型不够么？另外，
      家园 整形是不行的
      因为有的解中间结果是非整数。
      - 复整形是不行的
        家园 用分数保存计算结果，+-*/定义一下，结果保留分母分子
        复用分数保存计算结果，+-*/定义一下，结果保留分母分子
        家园 这个主意不错。我老是往如何迭代消减表达式这个方向想，越搞越复杂。
        感觉这个题目所要求的计算量不大的，如果能完全用整型来实现，速度应该还能提高。
      - 复整形是不行的
        家园 是因为除法么？不用吧。除法操作的结果必须是整数吧？
        复是因为除法么？不用吧。除法操作的结果必须是整数吧？
        家园 不一定
        7*(4-4/7)
        这个是 7 7 4 4 在同构意义下的唯一解.
        复不一定
        家园 这个是问题。不过，感觉这样的除法都能”削掉“吧？我好像
        在把问题给复杂化了。

分页树展主题 · 全看下页

有趣有益，互惠互利；开阔视野，博采众长。
虚拟的网络，真实的人。天南地北客，相逢皆朋友

版面群落趣味社区帮助常见问题网站简介基本河规隐私条款使用条款广告说明