免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 6112 | 回复: 5

我用C写的一个算24点代码。 [复制链接]

论坛徽章:
0
发表于 2006-03-24 11:16 |显示全部楼层
主要是使用逆波兰表达式的求值。欢迎测试和指正!


  1. /* cal24.c
  2. * given N integer numbers
  3. * find one expression which produces value T using all
  4. * the N numbers and {+,-,*,/} operators
  5. */
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <string.h>

  9. #define N 4  /* number of cards    */
  10. #define T 24 /* target solution    */
  11. #define M 13 /* maximum card value */
  12. #define STACK_SIZE (N+N-1)
  13. #define EPS 1e-6
  14. #define ADD M+1
  15. #define SUB M+2
  16. #define MUL M+3
  17. #define DIV M+4

  18. /* evaluate an expression in reverse Polish notation (RPN) */
  19. double eval(int expr[])
  20. {
  21.     double oprnds[N],oprnd1,oprnd2;
  22.     int top = -1,i,op;
  23.     for(i = 0;i<STACK_SIZE;++i){
  24.         op = expr[i];
  25.         if(op<=M){
  26.             oprnds[++top] = (double)op;
  27.             continue;
  28.         }
  29.         oprnd1 = oprnds[top--];
  30.         oprnd2 = oprnds[top--];
  31.         switch(op){
  32.         case ADD: oprnd1 += oprnd2; break;
  33.         case SUB: oprnd1 -= oprnd2; break;
  34.         case MUL: oprnd1 *= oprnd2; break;
  35.         case DIV:
  36.             if(oprnd2<EPS && oprnd2>-EPS) return 0.0;
  37.             oprnd1 /= oprnd2;
  38.         }
  39.         oprnds[++top] = oprnd1;
  40.     }
  41.     return oprnds[top];
  42. }

  43. int succ(int expr[])
  44. {
  45.     double x = eval(expr);
  46.     if(x>T-EPS && x<T+EPS) return 1;
  47.     return 0;
  48. }

  49. /* just to make the expression more readable by human */
  50. void printsolution(int expr[])
  51. {
  52.     double oprnds[N],oprnd1,oprnd2,result;
  53.     int top = -1,i,op;
  54.     char c;
  55.     for(i = 0;i<STACK_SIZE;++i){
  56.         op = expr[i];
  57.         if(op<=M){
  58.             oprnds[++top] = (double)op;
  59.             continue;
  60.         }
  61.         oprnd1 = oprnds[top--];
  62.         oprnd2 = oprnds[top--];
  63.         switch(op){
  64.         case ADD:
  65.             c = '+';
  66.             result = oprnd1 + oprnd2;
  67.             break;
  68.         case SUB:
  69.             c = '-';
  70.             result = oprnd1 - oprnd2;
  71.             break;
  72.         case MUL:
  73.             c = '*';
  74.             result = oprnd1 * oprnd2;
  75.             break;
  76.         case DIV:
  77.             c = '/';
  78.             result = oprnd1 / oprnd2;
  79.         }
  80.         printf("%.2f %c %.2f => %.2f\n",oprnd1,c,oprnd2,result);
  81.         oprnds[++top] = result;
  82.     }
  83. }

  84. /* update ret[] with next possible permutation of N cards */
  85. int permute(int ret[])
  86. {
  87.     int orig[N],i,j = 1;
  88.     for(i = 0;i<N-1;++i)
  89.         if(ret[i]<ret[i+1]){
  90.             j = 0;
  91.             break;
  92.         }
  93.     if(j) return 0;
  94.     for(i = 0;i<N;++i) orig[i] = ret[i];
  95.     for(i = N-2;i>=0;--i)
  96.         if(orig[i]<orig[i+1]) break;
  97.     for(j = N-1;j>i;--j)
  98.         if(orig[j]>orig[i]) break;
  99.     ret[i] = orig[j];
  100.     orig[j] = orig[i];
  101.     for(j = i+1;j<N;++j)
  102.         ret[j] = orig[N-j+i];
  103.     return 1;
  104. }

  105. /* update ops[] with next possible operators */
  106. int operators(int ops[])
  107. {
  108.     int i,j;
  109.     for(i = N-1;i>=0;--i){
  110.         if(ops[i]<DIV){
  111.             ++ops[i];
  112.             for(j = i+1;j<N-1;++j) ops[j] = ADD;
  113.             return 1;
  114.         }
  115.     }
  116.     return 0;
  117. }

  118. /* update expr[] with next possible expression in RPN */
  119. int expressions(int expr[])
  120. {
  121.     if(expr[3]>M && expr[4]>M) return 0;
  122.     if(expr[2]>M && expr[4]>M) expr[2]^=expr[3]^=expr[2]^=expr[3];
  123.     else if(expr[2]>M) expr[4]^=expr[5]^=expr[4]^=expr[5];
  124.     else if(expr[3]>M) expr[2]^=expr[3]^=expr[2]^=expr[3];
  125.     else expr[3]^=expr[4]^=expr[3]^=expr[4];
  126.     return 1;
  127. }

  128. int main(int argc,char *argv[])
  129. {
  130.     int opd[N],pmt[N],ops[N-1],expr[STACK_SIZE],i,succeed = 1;
  131.     if(argc<N+1) exit(printf("Not enough arguments!\n"));
  132.     for(i = 0;i<N;++i) opd[i] = atoi(argv[i+1]);
  133.     for(i = 0;i<N;++i) pmt[i] = i;
  134.     for(i = 0;i<N-1;++i) ops[i] = ADD;
  135.     while(1){
  136.         for(i = 0;i<N;++i) expr[i] = opd[pmt[i]];
  137.         for(i = 0;i<N-1;++i) expr[N+i] = ops[i];
  138.         if(succ(expr)) break;
  139.         while(expressions(expr))
  140.             if(succ(expr)) break;
  141.         if(succ(expr)) break;
  142.         if(!operators(ops)){
  143.             if(!permute(pmt)){
  144.                 succeed = 0;
  145.                 break;
  146.             }
  147.             for(i = 0;i<N-1;++i) ops[i] = ADD;
  148.         }
  149.     }
  150.     if(!succeed) exit(printf("Find no solutions!\n"));
  151.     printsolution(expr);
  152. }

复制代码

论坛徽章:
0
发表于 2006-03-24 11:18 |显示全部楼层
几个比较“经典”的数字组合测试:

  1. [bohnanza:misc]$ ./cal24 3 3 8 8
  2. 8.00 / 3.00 => 2.67
  3. 3.00 - 2.67 => 0.33
  4. 8.00 / 0.33 => 24.00
  5. [bohnanza:misc]$ ./cal24 5 5 1 5
  6. 1.00 / 5.00 => 0.20
  7. 5.00 - 0.20 => 4.80
  8. 4.80 * 5.00 => 24.00
  9. [bohnanza:misc]$ ./cal24 4 4 10 10
  10. 10.00 * 10.00 => 100.00
  11. 100.00 - 4.00 => 96.00
  12. 96.00 / 4.00 => 24.00
  13. [bohnanza:misc]$ ./cal24 3 7 3 7
  14. 3.00 / 7.00 => 0.43
  15. 0.43 + 3.00 => 3.43
  16. 7.00 * 3.43 => 24.00
  17. [bohnanza:misc]$ ./cal24 1 2 3 4
  18. 2.00 + 1.00 => 3.00
  19. 3.00 + 3.00 => 6.00
  20. 4.00 * 6.00 => 24.00
  21. [bohnanza:misc]$ ./cal24 7 7 7 7
  22. Find no solutions!

复制代码

原帖由 emacsnw 于 2006-3-23 19:16 发表
主要是使用逆波兰表达式的求值。欢迎测试和指正!


  1. /* cal24.c
  2. * given N integer numbers
  3. * find one expression which produces value T using all
  4. * the N numbers and {+,-,*,/} operators
  5. ...
复制代码

论坛徽章:
0
发表于 2006-03-24 11:32 |显示全部楼层
  1. [bohnanza:misc]$ ./cal24 3 3 8 8
  2. 8.00 / 3.00 => 2.67
  3. 3.00 - 2.67 => 0.33
  4. 8.00 / 0.33 => 24.00
复制代码


这个涉及到精度的这样子表示好像不太妥当.
我觉得最后表达出来的时候写成一连串的数字和运算符组合可能好点,比如上面的那个:
8/ (3 - 8 /3)...

回头我也研究一下24点的算法

论坛徽章:
0
发表于 2006-03-24 12:24 |显示全部楼层
原帖由 converse 于 2006-3-23 19:32 发表
  1. [bohnanza:misc]$ ./cal24 3 3 8 8
  2. 8.00 / 3.00 => 2.67
  3. 3.00 - 2.67 => 0.33
  4. 8.00 / 0.33 => 24.00
复制代码


这个涉及到精度的这样子表示好像不太妥当.
我觉得最后表达出来的时候写成一连串 ...


计算的时候是使用double精度的,这个只是打印的时候不想在数字后面打太多位的小数。
打印表达式确实你说的那样更好一些。但是我自己在玩这个游戏的时候却是这样的一个
过程,而且逆波兰表达式转换成这种打印形式方便一些,偷懒了。

论坛徽章:
1
荣誉会员
日期:2011-11-23 16:44:17
发表于 2006-03-24 12:47 |显示全部楼层
很久很久以前,也写过一个很垃圾的
http://bbs.chinaunix.net/viewthr ... &highlight=yuxh

论坛徽章:
0
发表于 2006-03-24 15:41 |显示全部楼层
用分数吧,反正全是有理数
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP