数学研发论坛

 找回密码
 欢迎注册
查看: 7016|回复: 54

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

[复制链接]
发表于 2012-4-12 14:06:40 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

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

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

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

8\8\4\3
先给一个,看谁先算出来
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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}
  1. TableForm[{#, ToExpression[#]} & /@ Map[StringJoin,  Riffle[CharacterRange["1", "4"], #] & /@ Tuples[{"+", "-", "*", "/"}, {3}]]]
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-13 08:28:30 | 显示全部楼层
找到一个过去写的c++代码
  1. #include   <stdio.h>   
  2.   #include   <map>   
  3.   #include   <algorithm>   
  4.   using   namespace   std;   
  5.   int   pm[]={0x1,0x55,0x10515,0x555555,0x41041,0x15,0x30f3f,0xffffff,   
  6.                       0x3f,0x30f3f,0xaaff,0x20b,0xaaff,0x2cb2cb,0x1c71c7};   
  7.   short   table[]={   
  8.           0,       65,     130,     195,     132,     261,     134,     199,   
  9.               328,     201,     138,     203,     140,     205,     142,     207,   
  10.                   402,     467,     537,     410,     475,     412,     605,     414,   
  11.       479,     354,     227,     164,     229,     166,     231,       42,   
  12.           107,     172,     237,     174,     303,     691,     436,     501,   
  13.               438,     503,   1416,   1481,   1738,   1803,   1420,   1485,   
  14.               1871,   1432,   1497,   1754,   1819,   1436,   1501,   1887,   
  15.               1760,   1825,   1442,   1507,   1893,   1446,   1511,   1776,   
  16.               1841,   1458,   1523,   1909,   1462,   1527,   2883,   2503,   
  17.               2899,   2519,   2921,   2541,   2937,   2557,   3331,   3975,   
  18.               3915,   3535,   3287,   3931,   3551,   3937,   3557,   3369,   
  19.               4013,   3953,   3573,   3325,   4301,   4573,   4327,   4599   
  20.   };   
  21.    
  22.   short   o0[24];   
  23.   short   o1[24];   
  24.   short   o2[24];   
  25.   short   o3[24];   
  26.   char   opprint[]={'+','-','*','/'};   
  27.   int   mask_cd,mask_bcd,mask_ab_cd;   
  28.   #define   mask_null   0xFFFFFF   
  29.   #define   mask_abcd   1   
  30.    
  31.   struct   expression{   
  32.       int   value;   
  33.           expression(int   v):value(v){     }   
  34.               int   first_op()const{   
  35.                         return   value   &   3;   
  36.             }   
  37.                   int   second_op()const{   
  38.             return   (value   >>   2)&3;   
  39.                 }   
  40.       int   third_op()const{   
  41.                 return   (value   >>   4)&3;   
  42.                     }   
  43.           int   graph_type()const{   
  44.                     return   (value   >>   6)/24;   
  45.         }   
  46.               int   num_order()const{   
  47.                         return   (value   >>   6)%24;   
  48.             }   
  49.   };   
  50.    
  51.   typedef   int   INT;   
  52.   struct   factor_num{   
  53.         INT   up;   
  54.               INT   down;   
  55.                     factor_num(){}   
  56.           factor_num(INT   u,INT   d):up(u),down(d){     }   
  57.   };   
  58.    
  59.   typedef   factor_num   (*OperatorFun)(const   factor_num&   x,const   factor_num&   y);   
  60.   factor_num   sum(const   factor_num&   i,const   factor_num&   j){   
  61.   INT   d,u;   
  62.         if(i.down==0||j.down==0){   
  63.                   d=0;   
  64.         }else{   
  65.                   d=i.down   *   j.down;   
  66.             u=i.up   *   j.down   +   j.up   *   i.down;   
  67.                   }   
  68.               return   factor_num(u,d);   
  69.   }   
  70.    
  71.   factor_num   dif(const   factor_num&   i,const   factor_num&   j){   
  72.   INT   d,u;   
  73.         if(i.down==0||j.down==0){   
  74.                   d=0;   
  75.         }else{   
  76.                   d=i.down   *   j.down;   
  77.             u=i.up   *   j.down   -   j.up   *   i.down;   
  78.                   }   
  79.               return   factor_num(u,d);   
  80.   }   
  81.    
  82.   factor_num   prod(const   factor_num&   i,const   factor_num&   j){   
  83.   INT   d,u;   
  84.         u=i.up   *   j.up;   
  85.               d=i.down   *   j.down;   
  86.                     return   factor_num(u,d);   
  87.   }   
  88.   factor_num   ratio(const   factor_num&   i,const   factor_num&   j){   
  89.   INT   d,u;   
  90.         if(i.down   ==   0   ||   j.down==0){   
  91.                   d=0;   
  92.         }else{   
  93.                   d=i.down   *   j.up;   
  94.             u=i.up   *   j.down;   
  95.                   }   
  96.               return   factor_num(u,d);   
  97.   }   
  98.   OperatorFun   funs[]={sum,dif,prod,ratio};   
  99.    
  100.   bool   equal_num(const   factor_num&   i,INT   j)   
  101.   {   
  102.           if(i.down==0){   
  103.                         return   false;   
  104.                 }else{   
  105.                               return   i.up   ==   j   *   i.down;   
  106.                       }   
  107.   }   
  108.    
  109.   void   show(INT   input[],expression   expr){   
  110.         int   order=expr.num_order();   
  111.               INT   aa=input[o0[order]];   
  112.                     INT   bb=input[o1[order]];   
  113.           INT   cc=input[o2[order]];   
  114.                 INT   dd=input[o3[order]];   
  115.                       short   op1=expr.first_op();   
  116.             char   ops1=opprint[op1];   
  117.                   short   op2=expr.second_op();   
  118.         char   ops2=opprint[op2];   
  119.               short   op3=expr.third_op();   
  120.                     char   ops3=opprint[op3];   
  121.           switch(expr.graph_type()){   
  122.                 case   0:   
  123.                             if(op1<2   &&   op2   >=2){   
  124.                     printf("(%d%c%d)%c",aa,ops1,bb,ops2);   
  125.                 }   else   {   
  126.                         printf("%d%c%d%c",aa,ops1,bb,ops2);   
  127.                     }   
  128.                         if(op2>=op3){   
  129.                 printf("(%d%c%d)",cc,ops3,dd);   
  130.                             }else{   
  131.                     printf("%d%c%d",cc,ops3,dd);   
  132.                 }   
  133.                     break;   
  134.           case   1:   
  135.                 if(op2<2&&op3>=2)   
  136.                                 printf("(");   
  137.                             if(op1<2&&op2>=2)   
  138.                             printf("(");   
  139.                         printf("%d%c%d",aa,ops1,bb);   
  140.                     if(op1<2&&op2>=2)   
  141.                     printf(")");   
  142.                 printf("%c%d",ops2,cc);   
  143.                             if(op2<2&&op3>=2)   
  144.                             printf(")");   
  145.                   printf("%c%d",ops3,dd);   
  146.               break;   
  147.                     case   2:   
  148.                           if(op1<2&&op3>=2)   
  149.                           printf("(");   
  150.                       printf("%d%c",aa,ops1);   
  151.                   if(op1>=op2)   
  152.                   printf("(");   
  153.               printf("%d%c%d",bb,ops2,cc);   
  154.                           if(op1>=op2)   
  155.                           printf(")");   
  156.                       if(op1<2&&op3>=2)   
  157.                       printf(")");   
  158.                   printf("%c%d",ops3,dd);   
  159.               break;   
  160.                     case   3:   
  161.                           printf("%d%c",aa,ops1);   
  162.                       if(op1>=op3)   
  163.                         printf("(");   
  164.                   if(op2<2&&op3>=2)   
  165.                     printf("(");   
  166.               printf("%d%c%d",bb,ops2,cc);   
  167.                           if(op2<2&&op3>=2)   
  168.                             printf(")");   
  169.                       printf("%c%d",ops3,dd);   
  170.                   if(op1>=op3)   
  171.                     printf(")");   
  172.               break;   
  173.                     case   4:   
  174.                           printf("%d%c",aa,ops1);   
  175.                       if(op1>=op2)   
  176.                       printf("(");   
  177.                   printf("%d%c",bb,ops2);   
  178.               if(op2>=op3)   
  179.                               printf("(");   
  180.                           printf("%d%c%d",cc,ops3,dd);   
  181.                       if(op2>=op3)   
  182.                       printf(")");   
  183.                   if(op1>=op2)   
  184.                   printf(")");   
  185.               break;   
  186.                     }   
  187.   }   


  188. #define   elems(x)   (sizeof(x)/sizeof(x[0]))   
  189.    
  190.   void   c_main(INT   input[],int   mask,INT   result)   
  191.   {   
  192.           int   total=0;   
  193.                   int   i;   
  194.           factor_num   r1,r2,r;   
  195.           for(i=0;i<elems(table);i++){   
  196.               int   op=table[   i]&63;   
  197.                   int   left=table[   i]>>6;   
  198.       int   g=left>>4;   
  199.           int   pl=left&15;   
  200.               int   pattern=pm[pl]&mask;   
  201.                   int   j;   
  202.       for(j=0;j<24;j++){   
  203.             if(pattern&(1<<j)){   
  204.                       short   elem=(j+g*24)*64+op;   
  205.                 expression   t(elem);   
  206.                           short   op1=t.first_op();   
  207.                     short   op2=t.second_op();   
  208.               short   op3=t.third_op();   
  209.                         short   gtype=t.graph_type();   
  210.                   short   order=t.num_order();   
  211.             factor_num   aa=factor_num(input[o0[order]],1);   
  212.                       factor_num   bb=factor_num(input[o1[order]],1);   
  213.                 factor_num   cc=factor_num(input[o2[order]],1);   
  214.                           factor_num   dd=factor_num(input[o3[order]],1);   
  215.                     OperatorFun   fun1=funs[op1];   
  216.               OperatorFun   fun2=funs[op2];   
  217.                         OperatorFun   fun3=funs[op3];   
  218.                   switch(gtype){   
  219.             case   0:   
  220.                           r1=fun1(aa,bb);   
  221.                         r2=fun3(cc,dd);   
  222.                       r=fun2(r1,r2);   
  223.                     break;   
  224.               case   1:   
  225.                   r1=fun1(aa,bb);   
  226.                 r2=fun2(r1,cc);   
  227.                               r=fun3(r2,dd);   
  228.                             break;   
  229.                       case   2:   
  230.                           r1=fun2(bb,cc);   
  231.                         r2=fun1(aa,r1);   
  232.                       r=fun3(r2,dd);   
  233.                     break;   
  234.               case   3:   
  235.                   r1=fun2(bb,cc);   
  236.                 r2=fun3(r1,dd);   
  237.                               r=fun1(aa,r2);   
  238.                             break;   
  239.                       case   4:   
  240.                           r1=fun3(cc,dd);   
  241.                         r2=fun2(bb,r1);   
  242.                       r=fun1(aa,r2);   
  243.                     break;   
  244.               }   
  245.             if(equal_num(r,result)){   
  246.                       show(input,t);   
  247.                 printf("/t");   
  248.                           total++;   
  249.                     }   
  250.                   }   
  251.                 }   
  252.             }   
  253.                 if(total)printf("/n");   
  254.   }   
  255.    
  256.   void   c24(INT   s1,INT   s2,INT   s3,INT   s4,INT   r){   
  257.       INT   input[4];   
  258.           int   i,j;   
  259.               input[0]=s1;input[1]=s2;input[2]=s3;input[3]=s4;   
  260.                   for(i=0;i<4;i++){   
  261.         for(j=i+1;j<4;j++){   
  262.                 if(input[j]<input[   i]){   
  263.                           INT   temp=input[j];   
  264.                     input[j]=input[   i];   
  265.               input[   i]=temp;   
  266.                       }   
  267.                       }   
  268.             }   
  269.       if(input[0]==input[1]){//a==b   
  270.                 if(input[1]!=input[2]){   
  271.                                   if(input[2]!=input[3]){//only   a==b   
  272.                             INT   temp=input[2];   
  273.                                       input[2]=input[0];   
  274.                                 input[0]=temp;   
  275.                                           temp=input[3];   
  276.                                     input[3]=input[1];   
  277.                               input[1]=temp;   
  278.                                         c_main(input,mask_cd,r);   
  279.                           }else{//a==b,c==d   
  280.                                     c_main(input,mask_ab_cd,r);   
  281.                       }   
  282.               }else   if(input[2]!=input[3]){//a==b==c!=d   
  283.                                 INT   temp=input[0];   
  284.                                   input[0]=input[3];   
  285.                     input[3]=temp;   
  286.                       c_main(input,mask_bcd,r);   
  287.                   }else{//a==b==c==d   
  288.                     c_main(input,mask_abcd,r);   
  289.                 }   
  290.                       }else{//a!=b   
  291.                   if(input[1]==input[2]){   
  292.                     if(input[2]!=input[3]){//b==c   
  293.                             INT   temp=input[3];   
  294.                                     input[3]=input[1];   
  295.                             input[1]=temp;   
  296.                                     c_main(input,mask_cd,r);   
  297.                       }else{//b==c==d   
  298.                               c_main(input,mask_bcd,r);   
  299.                                 }   
  300.                 }else{   
  301.                                   if(input[2]==input[3]){//c==d   
  302.                           c_main(input,mask_cd,r);   
  303.                             }else{   
  304.                                     c_main(input,mask_null,r);   
  305.                       }   
  306.               }   
  307.         }   
  308.   }   
  309.   #define   N   13   
  310.   void   init()   
  311.   {   
  312.   INT   i=0;   
  313.   short   a[4]={0,1,2,3};   
  314.   do{   
  315.       o0[   i]=a[0];   
  316.           o1[   i]=a[1];   
  317.               o2[   i]=a[2];   
  318.                   o3[   i]=a[3];   
  319.       i++;   
  320.   }while(next_permutation(a,a+4));   
  321.   for(i=0;i<24;i++){   
  322.       short   inv[4];   
  323.           inv[o0[   i]]=0;   
  324.               inv[o1[   i]]=1;   
  325.                   inv[o2[   i]]=2;   
  326.       inv[o3[   i]]=3;   
  327.           if(inv[2]<inv[3]){   
  328.                 mask_cd|=(1<<i);   
  329.                     }   
  330.               if(inv[1]<inv[2]&&inv[2]<inv[3]){   
  331.                     mask_bcd|=(1<<i);   
  332.         }   
  333.                   if(inv[0]<inv[1]&&inv[2]<inv[3]){   
  334.         mask_ab_cd|=(1<<i);   
  335.             }   
  336.   }   
  337.   }   
  338.   int   bits(int   x){   
  339.           int   b=0,i;   
  340.           for(i=0;i<32;i++)if(x&(1<<i))b++;   
  341.           return   b;   
  342.   }   
  343.   int   main()   
  344.   {   
  345.   INT   i=0,j,k,m;   
  346.   init();   
  347.   for(i=1;i<=N;i++)for(j=i;j<=N;j++)for(k=j;k<=N;k++)for(m=k;m<=N;m++){   
  348.       c24(i,j,k,m,24);   
  349.   }   
  350.   }
复制代码

点评

你的代码我看不懂,看到没注释的代码,我就不想看了,但是能写这么复杂,表示你很牛逼  发表于 2018-7-27 13:00
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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

文字内容和代码都没看明白!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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


没有注释的程序,将来自己能看明白吗?
我很怀疑!
我觉得那么长的程序,还不如弄成压缩一下传上来呢
对了,最好还有注释与说明,不然程序真的很难懂!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-13 11:52:21 | 显示全部楼层
其实这个代码几乎不包含什么有用的信息,主要是一个表格,包含了四个数的不等价的表达式的一种编码后的形式。而产生表格的代码我已经找不到。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-13 14:37:59 | 显示全部楼层
文字内容和代码都没看明白!
mathematica 发表于 2012-4-13 11:48


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

点评

这个是只能没有括号的情况  发表于 2013-10-18 18:08
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-13 15:42:19 | 显示全部楼层
还可以用x~jia~y来表示(x+y),赫赫。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-15 10:59:39 | 显示全部楼层
7# zgg___
  ,逃不过zgg的慧眼

感觉有括号的情况要麻烦些
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-18 13:20:45 | 显示全部楼层
我也看不懂,Mathematica的函数真多
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-3-19 16:58 , Processed in 0.053468 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表