| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3305 人关注过本帖
标题:关于计算24点输出式子重复的问题
取消只看楼主 加入收藏
魔城侠客
Rank: 1
等 级:新手上路
帖 子:200
专家分:0
注 册:2006-4-4
结帖率:50%
收藏
 问题点数:0 回复次数:6 
关于计算24点输出式子重复的问题

刚搜索下论坛贴子,发现24点输出式子重复的问题好像也不能得到解决,小弟我再来问下如何解决
比如4*7-6+2与4*7+2-6这两个式子重复,,,以下为个人程序


#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");
}

搜索更多相关主题的帖子: 输出 
2007-08-20 11:25
魔城侠客
Rank: 1
等 级:新手上路
帖 子:200
专家分:0
注 册:2006-4-4
收藏
得分:0 
13
因为我没有加入括号

West and east,home is best……
2007-08-20 12:29
魔城侠客
Rank: 1
等 级:新手上路
帖 子:200
专家分:0
注 册:2006-4-4
收藏
得分:0 
以下是引用noah_shi在2007-8-20 14:06:52的发言:
太长也没具体看代码,测试结果是错的!

跑了一下,输入5 6 1 2 ,结果是错的。

还是先算对了,再考虑优化吧

结果是对的,我试过了,输出的式子按顺序来算,不是按符号优先级来算的
如5+6+1*2为(5+6+1)*2.......;

我知道怎么把重复的去掉了.
比如两个重复的式子:10+3-9*6和3+10-9*6
我们只要把每个式子连同符号在内连成一个链表,结点中包括符号和数据
+,-,*,/分别对应数字为0,1,2,3
每个数据与前面的符号放在一结点里.如把9与"-"号放在一起,,故为数据为9与符号为1
第一个数的符号为:如果第二个数前的符号为+或-则第一个数符号可以看成是+,故为0
                      否则第一个数的符号可以看成是*,故为2....
如10,由于后面的符号为+,故10的符号也可看成是+,,,,,,
这样将成功输出的式子也转换成链表保存起来,再与将要输出的式子转换成链表与原先保存起来的链表比较,
如果两个链表中至少有3个结点完全相同时,我们就可以认为这两个式子是一样,,,,重量复的,,,

不知道这样是否可以将重复的式子去掉


West and east,home is best……
2007-08-20 15:04
魔城侠客
Rank: 1
等 级:新手上路
帖 子:200
专家分:0
注 册:2006-4-4
收藏
得分:0 
以下是引用雨中飞燕在2007-8-20 14:29:34的发言:
不如大家看看这个做得怎么样:
[attach]26309[/attach]
这是我做的解24点的小程序

这个是C语言写的???
源代码能否给出来看下


West and east,home is best……
2007-08-20 15:11
魔城侠客
Rank: 1
等 级:新手上路
帖 子:200
专家分:0
注 册:2006-4-4
收藏
得分:0 
源代码能否拿出来看下??

West and east,home is best……
2007-08-20 15:35
魔城侠客
Rank: 1
等 级:新手上路
帖 子:200
专家分:0
注 册:2006-4-4
收藏
得分:0 
利用链表比较的方法可以将重复的式子去掉的
我试过了

West and east,home is best……
2007-08-21 10:08
魔城侠客
Rank: 1
等 级:新手上路
帖 子:200
专家分:0
注 册:2006-4-4
收藏
得分:0 

如何在式子中加入括号呢
似乎有些数据还不好处理,比如(9-3)*(5-1)这样的就算不出来了
以下是我改的程序..
#include<stdio.h>
#include<stdlib.h>
#define N 4
#define M 20
#define true 1
#define false 0
typedef struct link
{
int sign_number; //数据的符号
int data; //数据
struct link *next;
}Qlink,*link;
int molecule[N],denominator[N],x;
Qlink *A[M];
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;
}
link Q_sort(Qlink *p) //链表排序 不改变指针,只改变结点中的数据
{
int dat,sig_number,i,j,temp_data,temp_sign;
Qlink *h,*pn;
h=p;
for(i=0;i<(N*(N-1)/2);i++)
{
p=h;
pn=p->next;
temp_data=p->data;
temp_sign=p->sign_number;
for(j=0;j<N-1-i;j++)
{
if(temp_data<pn->data || (pn->data==temp_data && temp_sign<pn->sign_number))
{
p->data=pn->data;
p->sign_number=pn->sign_number;
}
else
{
p->data=temp_data;
p->sign_number=temp_sign;
temp_data=pn->data;
temp_sign=pn->sign_number;
}
p=p->next;
pn=pn->next;
}
p->data=temp_data;
p->sign_number=temp_sign;
}
return h;
}
int compare(Qlink *p,Qlink *q) //判断两式子是否有重复
{
int i=0;
p=Q_sort(p);
q=Q_sort(q);
while(p && q)
{
if(p->data==q->data && p->sign_number==q->sign_number) i++;
p=p->next;
q=q->next;
}
if(i==4) return true;
else return false;
}
int Compare_same(Qlink *p)
{
int i=0;
Qlink *q;
while(A[i]->next)
{
if(compare(p,A[i]->next)) return true; //两个式子是一样
i++;
}
A[i]->next=p;
return false;
}
//以下计算分数参与,计算采用通分和约分
void calculate(int *q,int *s,int *p) //计算式子
{
int gys,gbs,yue,i;
Qlink *r,*head,*rear;
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) //计算成功则输出式子 (无括号)
{
rear=(Qlink *)malloc(sizeof(Qlink)); //将式子连成链表并按数据大小进行排序
rear->next=NULL;
head=rear;
if(*s==0 || *s==1) rear->sign_number=0; //若第二个数前的符号为+或-,则第一个数前的符号为+
else rear->sign_number=2; //否则第一个数前的符号为*
rear->data=molecule[*p];
for(i=0;i<=2;i++)
{
r=(Qlink *)malloc(sizeof(Qlink));
r->sign_number=*(s+i);
r->data=molecule[*(p+i+1)];
r->next=NULL;
rear->next=r;
rear=r;
}
if(!Compare_same(head)) //两式子没有重复
{
printf(" ");
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");
x=x+1; //计数器,计算有几种不同的解
}
}
}
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);
}
}
void Free_Point() //将指针数组A初始化
{
Qlink *p,*pn;
int i;
for(i=0;i<M;i++)
{
p=A[i]->next;
while(p)
{
A[i]->next=NULL;
pn=p->next;
free(p);
p=pn;
}
}
}
int main(void)
{
int i,c[N],*p,j;
printf(" ******************************\n");
printf(" * 超级24点 *\n");
printf(" ******************************\n");
for(i=0;i<M;i++)
{
A[i]=(Qlink*)malloc(sizeof(Qlink));
A[i]->next=NULL;
}
printf("输出的表达式中符号优先级一样,无括号。\n");
printf("如;8-2*5-6 为(8-2)*5-6=24.\n");
do
{
Free_Point();
x=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(x==0) printf("该4个数无法得出24!\n");
else printf("该4个数计算24点共有%d种方法!\n",x);
printf("继续计算请按1,退出请按0\n");
scanf("%d",&j);
}while(j);
printf("退出成功!\n");
return 0;
}

...想问下括号应该如何处理???


West and east,home is best……
2007-08-21 13:56
快速回复:关于计算24点输出式子重复的问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.024209 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved