关于计算２４点输出式子重复的问题(页 1) - C语言论坛

魔城侠客 发表于 2007-8-20 11:25

关于计算２４点输出式子重复的问题

刚搜索下论坛贴子，发现２４点输出式子重复的问题好像也不能得到解决，小弟我再来问下如何解决 比如４＊７－６＋２与４＊７＋２－６这两个式子重复，，，以下为个人程序 #include<stdio.h> #define N 4 #define true 1 #define false 0 int molecule[N],denominator[N],r; int G_C_D(int a,int b) //求两数的最大公约数 { int temp; if(a<b) {temp=a;a=b;b=temp;} while(b!=0) { temp=a%b; a=b; b=temp; } return a; } //以下计算分数参与，计算采用通分和约分 void calculate(int *q,int *s,int *p) //计算式子 { int gys,gbs,yue,i; for(i=0;i<=2;i++) { gys=G_C_D(*(q+1),denominator[*p]); //最大公约数 gbs=*(q+1)*denominator[*p]/gys; //最小公倍数 if(*(s+i)==0) //0代表+ { *q=gbs/(*(q+1))*(*q)+gbs/denominator[*(p+i+1)]*molecule[*(p+i+1)]; *(q+1)=gbs; } else if(*(s+i)==1) //1代表- { *q=gbs/(*(q+1))*(*q)-gbs/denominator[*(p+i+1)]*molecule[*(p+i+1)]; *(q+1)=gbs; } else if(*(s+i)==2) //2代表* { *q=(*q)*molecule[*(p+i+1)]; *(q+1)=*(q+1)*denominator[*(p+i+1)]; yue=G_C_D(*q,*(q+1)); *q=*q/yue; *(q+1)=*(q+1)/yue; } else if(*(s+i)==3) //3代表/ { *q=(*q)*denominator[*(p+i+1)]; *(q+1)=*(q+1)*molecule[*(p+i+1)]; yue=G_C_D(*q,*(q+1)); *q=*q/yue; *(q+1)=*(q+1)/yue; } } if(*q/(*(q+1))==24 && *q%(*(q+1))==0) //计算成功则输出式子（无括号） { r=1; for(i=0;i<=3;i++) { printf("%d",molecule[*(p+i)]); switch(*(s+i)) { case 0:printf("+");break; case 1:printf("-");break; case 2:printf("*");break; case 3:printf("/");break; case 4:printf("=");break; } } printf("24\n"); } } int same(int *p) { int n=0,m=0; for(m=0;m<=N-1;m++) for(n=m+1;n<=N-1;n++) if(*(p+m)==*(p+n)) {return true;break;} return false; }
void tw_four(int *p) { int sign[N],result[2],*q; //result中保存计算结果的分子与分母 sign[N-1]=4; for(sign[0]=0;sign[0]<=N-1;sign[0]++) //符号穷举 for(sign[1]=0;sign[1]<=N-1;sign[1]++) for(sign[2]=0;sign[2]<=N-1;sign[2]++) { result[0]=molecule[*p]; result[1]=denominator[*p]; calculate(result,sign,p); } } main() { int i,c[N],*p,j; printf(" ******************************\n"); printf(" * 超级24点 *\n"); printf(" ******************************\n"); printf("输出的表达式中符号优先级一样。\n"); do { r=0; printf("请输入要计算的4个整数:"); for(i=0;i<=3;i++) //输出入数字，使分母初始化都为1 { scanf("%d",&molecule[i]); denominator[i]=1; } for(c[0]=0;c[0]<=N-1;c[0]++) for(c[1]=0;c[1]<=N-1;c[1]++) for(c[2]=0;c[2]<=N-1;c[2]++) for(c[3]=0;c[3]<=N-1;c[3]++) if(!same(c)) tw_four(c); if(r==0) printf("该4个数无法得出24!\n"); printf("继续计算请按1，退出请按0\n"); scanf("%d",&j); }while(j); printf("退出成功!\n"); system("pause"); }

coachard 发表于 2007-8-20 12:24

程序太长，没有看，不好意思 不过我想问下LZ，你这样穷举出来后，比如下面的算式，算出来结果是多少？ 1+2*3+4 是等于11还是等于13？

魔城侠客 发表于 2007-8-20 12:29

１３ 因为我没有加入括号

noah_shi 发表于 2007-8-20 13:33

问题关键：对判定式子重复的定义！ ４＊７－６＋２与４＊７＋２－６这两个式子可以认为重复， 我也可以认为是不重复的，先减6与后减6，运算顺序不同啊，单步得到的结果也不同啊。 所以关键是要把你认为的重复的那种标准，明确得定义下来，然后“告诉电脑”，就可以实现出来了！

noah_shi 发表于 2007-8-20 14:06

太长也没具体看代码，测试结果是错的！ 跑了一下,输入5 6 1 2 ，结果是错的。 还是先算对了，再考虑优化吧

雨中飞燕 发表于 2007-8-20 14:10

所有可以通过交换律或者结合律或者分配律可以变换出来的式子视为同一解 乘除1和加减0也算同一个运算

雨中飞燕 发表于 2007-8-20 14:29

不如大家看看这个做得怎么样： [attach]26309[/attach] 这是我做的解24点的小程序
[align=right][color=#000066][此贴子已经被作者于2007-8-20 14:30:39编辑过][/color][/align]

chen7806 发表于 2007-8-20 14:46

楼上做得很好呀。非常敬佩，用C写的吗？

lishizelibin 发表于 2007-8-20 14:53

<DIV class=quote>以下是引用雨中飞燕在2007-8-20 14:29:34的发言： 不如大家看看这个做得怎么样： [attach]26309[/attach] 这是我做的解24点的小程序 </DIV>
我要学习，你还是学生么？ 我们当学生的学的很多，感觉都不精，下学期刚大三，都是专业课了

coachard 发表于 2007-8-20 14:55

你都大三？应该感到惭愧哦[em04]，飞燕刚刚大一~~~~~~~~

雨中飞燕 发表于 2007-8-20 14:58

用C语言在VC6上写的
[align=right][color=#000066][此贴子已经被作者于2007-8-20 15:00:47编辑过][/color][/align]

lishizelibin 发表于 2007-8-20 14:59

那是，我是大二刚改行学计算机的，以前是学物理的 所以要努力了 大二下一边学数据结构，一边学c语言（自学）,还有微机原理
[align=right][color=#000066][此贴子已经被作者于2007-8-20 15:01:01编辑过][/color][/align]

coachard 发表于 2007-8-20 15:00

大学里面可以半途改专业？

lishizelibin 发表于 2007-8-20 15:03

<a href="http://bbs.bc-cn.net/viewthread.php?tid=159693&star=at" target="_blank" >http://bbs.bc-cn.net/viewthread.php?tid=159693&star=at</A># 看看我的历史 自学了一段时间c，以前都是基础课，还不知道怎么玩电脑

魔城侠客 发表于 2007-8-20 15:04

<DIV class=quote>以下是引用noah_shi在2007-8-20 14:06:52的发言： 太长也没具体看代码，测试结果是错的！ 跑了一下,输入5 6 1 2 ，结果是错的。 还是先算对了，再考虑优化吧 </DIV>
结果是对的，我试过了，输出的式子按顺序来算，不是按符号优先级来算的 如５＋６＋１＊２为（５＋６＋１）＊２．．．．．．．； 我知道怎么把重复的去掉了． 比如两个重复的式子：１０＋３－９＊６和３＋１０－９＊６ 我们只要把每个式子连同符号在内连成一个链表，结点中包括符号和数据 ＋，－，＊，／分别对应数字为０，１，２，３ 每个数据与前面的符号放在一结点里．如把９与＂－＂号放在一起，，故为数据为９与符号为１ 第一个数的符号为：如果第二个数前的符号为＋或－则第一个数符号可以看成是＋，故为０ 　　　　　　　　　　　　　　　　　　　　　　否则第一个数的符号可以看成是＊，故为２.... 如１０，由于后面的符号为＋，故１０的符号也可看成是＋，，，，，， 这样将成功输出的式子也转换成链表保存起来，再与将要输出的式子转换成链表与原先保存起来的链表比较， 如果两个链表中至少有３个结点完全相同时，我们就可以认为这两个式子是一样，，，，重量复的，，， 不知道这样是否可以将重复的式子去掉

雨中飞燕 发表于 2007-8-20 15:04

<DIV class=quote>以下是引用魔城侠客在2007-8-20 15:04:04的发言： 
结果是对的，我试过了，输出的式子按顺序来算，不是按符号优先级来算的 如５＋６＋１＊２为（５＋６＋１）＊２．．．．．．．； 我知道怎么把重复的去掉了． 比如两个重复的式子：１０＋３－９＊６和３＋１０－９＊６ 我们只要把每个式子连同符号在内连成一个链表，结点中包括符号和数据 ＋，－，＊，／分别对应数字为０，１，２，３ 每个数据与前面的符号放在一结点里．如把９与＂－＂号放在一起，，故为数据为９与符号为１ 第一个数的符号为：如果第二个数前的符号为＋或－则第一个数符号可以看成是＋，故为０ 　　　　　　　　　　　　　　　　　　　　　　否则第一个数的符号可以看成是＊，故为２.... 如１０，由于后面的符号为＋，故１０的符号也可看成是＋，，，，，， 这样将成功输出的式子也转换成链表保存起来，再与将要输出的式子转换成链表与原先保存起来的链表比较， 如果两个链表中至少有３个结点完全相同时，我们就可以认为这两个式子是一样，，，，重量复的，，， 不知道这样是否可以将重复的式子去掉 </DIV>
没这么简单，你试试看吧

lishizelibin 发表于 2007-8-20 15:08

下学期我也会做这种小软件了，我只会写代码，vc 还不会用，就要来的学期就要学应用工具开发了，那时我不害羞了，呵呵[em09]

魔城侠客 发表于 2007-8-20 15:11

<DIV class=quote>以下是引用雨中飞燕在2007-8-20 14:29:34的发言： 不如大家看看这个做得怎么样： [attach]26309[/attach] 这是我做的解24点的小程序 </DIV>
这个是Ｃ语言写的？？？ 源代码能否给出来看下

lishizelibin 发表于 2007-8-20 15:12

我想像这样小程序，我就给它反汇编了，不过是花时间的工作

雨中飞燕 发表于 2007-8-20 15:32

其实那个也不是做得很好，有的特殊数据处理不好 但大多数都是不错的

页: [1] 2