mathematica 发表于 2012-4-12 14:06:40

求算24点的程序,要求快且求出所有解!

给出4个整数.
1,2,3,4允许改变顺序,则可以是4,3,2,1

分四类情况:
A\允许改变数字顺序,不允许使用括号,使用加减乘除.
B\允许改变数字顺序,允许使用括号,使用加减乘除.
C\不允许改变数字顺序,不允许使用括号,使用加减乘除.
D\不允许改变数字顺序,允许使用括号,使用加减乘除.

在这四种情况下,写出程序!

8\8\4\3
先给一个,看谁先算出来

wayne 发表于 2012-4-12 14:29:44

C
{-23, -13, -(23/2), -10, -9, -8, -(13/2), -5, -4, -(23/6), -(11/3), -(10/3), -(5/2), -(7/3), -2, -(7/4), -(5/3), -1, -(1/2), -(1/ 4), 0, 1/24, 1/6, 3/8, 2/3, 5/6, 1, 7/6, 5/4, 3/2, 2, 9/4, 5/2, 8/3, 11/4, 3, 11/3, 15/4, 4, 25/6, 13/3, 14/3, 11/2, 17/3, 6, 15/2, 9, 10, 11, 25/2, 14, 15, 24, 25}TableForm[{#, ToExpression[#]} & /@ Map, #] & /@ Tuples[{"+", "-", "*", "/"}, {3}]]]

mathe 发表于 2012-4-13 08:28:30

找到一个过去写的c++代码#include   <stdio.h>   
#include   <map>   
#include   <algorithm>   
using   namespace   std;   
int   pm[]={0x1,0x55,0x10515,0x555555,0x41041,0x15,0x30f3f,0xffffff,   
                      0x3f,0x30f3f,0xaaff,0x20b,0xaaff,0x2cb2cb,0x1c71c7};   
short   table[]={   
          0,       65,   130,   195,   132,   261,   134,   199,   
            328,   201,   138,   203,   140,   205,   142,   207,   
                  402,   467,   537,   410,   475,   412,   605,   414,   
      479,   354,   227,   164,   229,   166,   231,       42,   
          107,   172,   237,   174,   303,   691,   436,   501,   
            438,   503,   1416,   1481,   1738,   1803,   1420,   1485,   
            1871,   1432,   1497,   1754,   1819,   1436,   1501,   1887,   
            1760,   1825,   1442,   1507,   1893,   1446,   1511,   1776,   
            1841,   1458,   1523,   1909,   1462,   1527,   2883,   2503,   
            2899,   2519,   2921,   2541,   2937,   2557,   3331,   3975,   
            3915,   3535,   3287,   3931,   3551,   3937,   3557,   3369,   
            4013,   3953,   3573,   3325,   4301,   4573,   4327,   4599   
};   
   
short   o0;   
short   o1;   
short   o2;   
short   o3;   
char   opprint[]={'+','-','*','/'};   
int   mask_cd,mask_bcd,mask_ab_cd;   
#define   mask_null   0xFFFFFF   
#define   mask_abcd   1   
   
struct   expression{   
      int   value;   
          expression(int   v):value(v){   }   
            int   first_op()const{   
                        return   value   &   3;   
            }   
                  int   second_op()const{   
            return   (value   >>   2)&3;   
                }   
      int   third_op()const{   
                return   (value   >>   4)&3;   
                  }   
          int   graph_type()const{   
                  return   (value   >>   6)/24;   
      }   
            int   num_order()const{   
                        return   (value   >>   6)%24;   
            }   
};   
   
typedef   int   INT;   
struct   factor_num{   
      INT   up;   
            INT   down;   
                  factor_num(){}   
          factor_num(INT   u,INT   d):up(u),down(d){   }   
};   
   
typedef   factor_num   (*OperatorFun)(const   factor_num&   x,const   factor_num&   y);   
factor_num   sum(const   factor_num&   i,const   factor_num&   j){   
INT   d,u;   
      if(i.down==0||j.down==0){   
                  d=0;   
      }else{   
                  d=i.down   *   j.down;   
            u=i.up   *   j.down   +   j.up   *   i.down;   
                  }   
            return   factor_num(u,d);   
}   
   
factor_num   dif(const   factor_num&   i,const   factor_num&   j){   
INT   d,u;   
      if(i.down==0||j.down==0){   
                  d=0;   
      }else{   
                  d=i.down   *   j.down;   
            u=i.up   *   j.down   -   j.up   *   i.down;   
                  }   
            return   factor_num(u,d);   
}   
   
factor_num   prod(const   factor_num&   i,const   factor_num&   j){   
INT   d,u;   
      u=i.up   *   j.up;   
            d=i.down   *   j.down;   
                  return   factor_num(u,d);   
}   
factor_num   ratio(const   factor_num&   i,const   factor_num&   j){   
INT   d,u;   
      if(i.down   ==   0   ||   j.down==0){   
                  d=0;   
      }else{   
                  d=i.down   *   j.up;   
            u=i.up   *   j.down;   
                  }   
            return   factor_num(u,d);   
}   
OperatorFun   funs[]={sum,dif,prod,ratio};   
   
bool   equal_num(const   factor_num&   i,INT   j)   
{   
          if(i.down==0){   
                        return   false;   
                }else{   
                              return   i.up   ==   j   *   i.down;   
                      }   
}   
   
void   show(INT   input[],expression   expr){   
      int   order=expr.num_order();   
            INT   aa=input];   
                  INT   bb=input];   
          INT   cc=input];   
                INT   dd=input];   
                      short   op1=expr.first_op();   
            char   ops1=opprint;   
                  short   op2=expr.second_op();   
      char   ops2=opprint;   
            short   op3=expr.third_op();   
                  char   ops3=opprint;   
          switch(expr.graph_type()){   
                case   0:   
                            if(op1<2   &&   op2   >=2){   
                  printf("(%d%c%d)%c",aa,ops1,bb,ops2);   
                }   else   {   
                        printf("%d%c%d%c",aa,ops1,bb,ops2);   
                  }   
                        if(op2>=op3){   
                printf("(%d%c%d)",cc,ops3,dd);   
                            }else{   
                  printf("%d%c%d",cc,ops3,dd);   
                }   
                  break;   
          case   1:   
                if(op2<2&&op3>=2)   
                              printf("(");   
                            if(op1<2&&op2>=2)   
                            printf("(");   
                        printf("%d%c%d",aa,ops1,bb);   
                  if(op1<2&&op2>=2)   
                  printf(")");   
                printf("%c%d",ops2,cc);   
                            if(op2<2&&op3>=2)   
                            printf(")");   
                  printf("%c%d",ops3,dd);   
            break;   
                  case   2:   
                        if(op1<2&&op3>=2)   
                        printf("(");   
                      printf("%d%c",aa,ops1);   
                  if(op1>=op2)   
                  printf("(");   
            printf("%d%c%d",bb,ops2,cc);   
                        if(op1>=op2)   
                        printf(")");   
                      if(op1<2&&op3>=2)   
                      printf(")");   
                  printf("%c%d",ops3,dd);   
            break;   
                  case   3:   
                        printf("%d%c",aa,ops1);   
                      if(op1>=op3)   
                        printf("(");   
                  if(op2<2&&op3>=2)   
                  printf("(");   
            printf("%d%c%d",bb,ops2,cc);   
                        if(op2<2&&op3>=2)   
                            printf(")");   
                      printf("%c%d",ops3,dd);   
                  if(op1>=op3)   
                  printf(")");   
            break;   
                  case   4:   
                        printf("%d%c",aa,ops1);   
                      if(op1>=op2)   
                      printf("(");   
                  printf("%d%c",bb,ops2);   
            if(op2>=op3)   
                              printf("(");   
                        printf("%d%c%d",cc,ops3,dd);   
                      if(op2>=op3)   
                      printf(")");   
                  if(op1>=op2)   
                  printf(")");   
            break;   
                  }   
}   


#define   elems(x)   (sizeof(x)/sizeof(x))   
   
void   c_main(INT   input[],int   mask,INT   result)   
{   
          int   total=0;   
                  int   i;   
          factor_num   r1,r2,r;   
          for(i=0;i<elems(table);i++){   
            int   op=table[   i]&63;   
                  int   left=table[   i]>>6;   
      int   g=left>>4;   
          int   pl=left&15;   
            int   pattern=pm&mask;   
                  int   j;   
      for(j=0;j<24;j++){   
            if(pattern&(1<<j)){   
                      short   elem=(j+g*24)*64+op;   
                expression   t(elem);   
                        short   op1=t.first_op();   
                  short   op2=t.second_op();   
            short   op3=t.third_op();   
                        short   gtype=t.graph_type();   
                  short   order=t.num_order();   
            factor_num   aa=factor_num(input],1);   
                      factor_num   bb=factor_num(input],1);   
                factor_num   cc=factor_num(input],1);   
                        factor_num   dd=factor_num(input],1);   
                  OperatorFun   fun1=funs;   
            OperatorFun   fun2=funs;   
                        OperatorFun   fun3=funs;   
                  switch(gtype){   
            case   0:   
                        r1=fun1(aa,bb);   
                        r2=fun3(cc,dd);   
                      r=fun2(r1,r2);   
                  break;   
            case   1:   
                  r1=fun1(aa,bb);   
                r2=fun2(r1,cc);   
                              r=fun3(r2,dd);   
                            break;   
                      case   2:   
                        r1=fun2(bb,cc);   
                        r2=fun1(aa,r1);   
                      r=fun3(r2,dd);   
                  break;   
            case   3:   
                  r1=fun2(bb,cc);   
                r2=fun3(r1,dd);   
                              r=fun1(aa,r2);   
                            break;   
                      case   4:   
                        r1=fun3(cc,dd);   
                        r2=fun2(bb,r1);   
                      r=fun1(aa,r2);   
                  break;   
            }   
            if(equal_num(r,result)){   
                      show(input,t);   
                printf("/t");   
                        total++;   
                  }   
                  }   
                }   
            }   
                if(total)printf("/n");   
}   
   
void   c24(INT   s1,INT   s2,INT   s3,INT   s4,INT   r){   
      INT   input;   
          int   i,j;   
            input=s1;input=s2;input=s3;input=s4;   
                  for(i=0;i<4;i++){   
      for(j=i+1;j<4;j++){   
                if(input<input[   i]){   
                        INT   temp=input;   
                  input=input[   i];   
            input[   i]=temp;   
                      }   
                      }   
            }   
      if(input==input){//a==b   
                if(input!=input){   
                                  if(input!=input){//only   a==b   
                            INT   temp=input;   
                                    input=input;   
                              input=temp;   
                                          temp=input;   
                                    input=input;   
                              input=temp;   
                                        c_main(input,mask_cd,r);   
                        }else{//a==b,c==d   
                                    c_main(input,mask_ab_cd,r);   
                      }   
            }else   if(input!=input){//a==b==c!=d   
                              INT   temp=input;   
                                  input=input;   
                  input=temp;   
                      c_main(input,mask_bcd,r);   
                  }else{//a==b==c==d   
                  c_main(input,mask_abcd,r);   
                }   
                      }else{//a!=b   
                  if(input==input){   
                  if(input!=input){//b==c   
                            INT   temp=input;   
                                    input=input;   
                            input=temp;   
                                    c_main(input,mask_cd,r);   
                      }else{//b==c==d   
                              c_main(input,mask_bcd,r);   
                              }   
                }else{   
                                  if(input==input){//c==d   
                        c_main(input,mask_cd,r);   
                            }else{   
                                    c_main(input,mask_null,r);   
                      }   
            }   
      }   
}   
#define   N   13   
void   init()   
{   
INT   i=0;   
short   a={0,1,2,3};   
do{   
      o0[   i]=a;   
          o1[   i]=a;   
            o2[   i]=a;   
                  o3[   i]=a;   
      i++;   
}while(next_permutation(a,a+4));   
for(i=0;i<24;i++){   
      short   inv;   
          inv]=0;   
            inv]=1;   
                  inv]=2;   
      inv]=3;   
          if(inv<inv){   
                mask_cd|=(1<<i);   
                  }   
            if(inv<inv&&inv<inv){   
                  mask_bcd|=(1<<i);   
      }   
                  if(inv<inv&&inv<inv){   
      mask_ab_cd|=(1<<i);   
            }   
}   
}   
int   bits(int   x){   
          int   b=0,i;   
          for(i=0;i<32;i++)if(x&(1<<i))b++;   
          return   b;   
}   
int   main()   
{   
INT   i=0,j,k,m;   
init();   
for(i=1;i<=N;i++)for(j=i;j<=N;j++)for(k=j;k<=N;k++)for(m=k;m<=N;m++){   
      c24(i,j,k,m,24);   
}   
}

mathematica 发表于 2012-4-13 11:48:19

C
{-23, -13, -(23/2), -10, -9, -8, -(13/2), -5, -4, -(23/6), -(11/3), -(10/3), -(5/2), -(7/3), -2, -(7/4), -(5/3), -1, -(1/2), -(1/ 4), 0, 1/24, 1/6, 3/8, 2/3, 5/6, 1, 7/6, 5/4, 3/2, 2, 9/4, 5/2, 8/3 ...
wayne 发表于 2012-4-12 14:29 http://bbs.emath.ac.cn/images/common/back.gif
文字内容和代码都没看明白!

mathematica 发表于 2012-4-13 11:49:31

找到一个过去写的c++代码#include      
#include      
#include      
using   namespace   std;   
int   pm[]={0x1,0x55,0x10515,0x555555,0x41041,0x15,0x30f3f,0xffffff,   
                  ...
mathe 发表于 2012-4-13 08:28 http://bbs.emath.ac.cn/images/common/back.gif

没有注释的程序,将来自己能看明白吗?
我很怀疑!
我觉得那么长的程序,还不如弄成压缩一下传上来呢
对了,最好还有注释与说明,不然程序真的很难懂!

mathe 发表于 2012-4-13 11:52:21

其实这个代码几乎不包含什么有用的信息,主要是一个表格,包含了四个数的不等价的表达式的一种编码后的形式。而产生表格的代码我已经找不到。

zgg___ 发表于 2012-4-13 14:37:59


文字内容和代码都没看明白!
mathematica 发表于 2012-4-13 11:48 http://bbs.emath.ac.cn/static/image/common/back.gif

赫赫,wayne的意思是:(* 关于题目中的情况C: *)
s := Select, #] & /@Tuples[{"+", "-", "*", "/"}, {3}]],ToExpression[#] == 24 &]; (* 这里套用wayne的代码 *)
{1, 2, 3, 4} // s (* 例子一 *)
{8, 8, 4, 3} // s (* 例子二 *)其实,我个人喜欢他们的风格,赫赫。

zgg___ 发表于 2012-4-13 15:42:19

还可以用x~jia~y来表示(x+y),赫赫。

wayne 发表于 2012-4-15 10:59:39

7# zgg___
:loveliness:,逃不过zgg的慧眼

感觉有括号的情况要麻烦些

mathe 发表于 2012-4-18 13:20:45

我也看不懂,Mathematica的函数真多
页: [1] 2 3
查看完整版本: 求算24点的程序,要求快且求出所有解!