West and east,home is best……
如何在式子中加入括号呢
似乎有些数据还不好处理,比如(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;
}
...想问下括号应该如何处理???
看了“雨中飞燕做”的24点DEMO,很强!
不知道筛选相同结果的原则是什么?但是有一点是肯定的——筛选标准很严格!
可否开源一观?或者仅仅是筛选结果的那部分!
以下,是我做了一个例程,筛选部分见filter()函数。
大家帮忙测试看看,效果是否理想?!
#include <iostream.h>
#include <math.h>
#define MINVALUE 1e-004float num[24][4];
int opetator[4] = {0,1,2,3};
int op[200][5];
float cmp1[4]={0};void intit(float *a)
{
int p = 0;
for(int i = 0;i<200;i++)
for(int j = 0;j<5;j++)
op[i][j] = -1;
for(int i = 0;i<4;i++)
for(int j = 0;j<4;j++)
for(int m = 0;m<4;m++)
for(int n = 0;n<4;n++)
{
if(i!=j&&i!=m&&i!=n&&j!=m&&j!=n&&m!=n)
{
num[p][0] = a[i];
num[p][1] = a[j];
num[p][2] = a[m];
num[p][3] = a[n];
p++;
}
else
continue;
}
}float OneStep(float a,float b,int i)
{
switch(opetator[i])
{
case 0:
return a+b;
case 1:
return a-b;
case 2:
return a*b;
case 3:
return a/b;
default:
return 0;
}
}void run(float sum)
{
int count = 0;
for(int i =0;i<24;i++)
for(int j = 0;j<4;j++)
for(int m = 0;m<4;m++)
for(int n = 0;n<4;n++)
{
if(abs(sum-OneStep(OneStep(num[i][0],num[i][1],j),OneStep(num[i][2],num[i][3],m),n))<MINVALUE)
{
op[count][0] = 2; //style: (2)(2)
op[count][1] = i; //link to num[][]
op[count][2] = j; //operator 1
op[count][3] = n; //operator 2
op[count][4] = m; //operator 3
count++;
}
if(abs(sum-OneStep(OneStep(OneStep(num[i][0],num[i][1],j),num[i][2],m),num[i][3],n))<MINVALUE)
{
op[count][0] = 1; //style: ((2)1)(1)
op[count][1] = i; //link to num[][]
op[count][2] = j; //operator 1
op[count][3] = m; //operator 2
op[count][4] = n; //operator 3
count++;
}
if(abs(sum-OneStep(OneStep(num[i][0],OneStep(num[i][1],num[i][2],j),m),num[i][3],n))<MINVALUE)
{
op[count][0] = 3; //style: (1(2))(1)
op[count][1] = i; //link to num[][]
op[count][2] = m; //operator 1
op[count][3] = j; //operator 2
op[count][4] = n; //operator 3
count++;
}
}
}char ToOperator(int i)
{
switch(i)
{
case 0:
return '+';
case 1:
return '-';
case 2:
return '*';
case 3:
return '/';
default:
return 0;
}
}void sort(float *a)
{
float p;
for(int i=0;i<4;i++)
for(int j=i+1;j<4;j++)
{
if(a[i]<a[j])
{
p = a[i];
a[i] = a[j];
a[j] = p;
}
}
}float* Analysis(int *a)
{
for(int i =0;i<4;i++)
cmp1[i] = 0;
if(a[0] == 1)
{
if(a[2]<=1&&a[3]>=2)
{
cmp1[0] = OneStep(num[a[1]][0],num[a[1]][1],a[2]);
cmp1[1] = num[a[1]][2];
cmp1[2] = num[a[1]][3];
sort(cmp1);
}
else if(a[3]<=1&&a[4]>=2)
{
cmp1[0] = OneStep(OneStep(num[a[1]][0],num[a[1]][1],a[2]),num[a[1]][2],a[3]);
cmp1[1] = num[a[1]][3];
sort(cmp1);
}
else
{
cmp1[0] = num[a[1]][0];
cmp1[1] = num[a[1]][1];
cmp1[2] = num[a[1]][2];
cmp1[3] = num[a[1]][3];
sort(cmp1);
}
}
else if(a[0] == 2)
{
if(a[3]>=2&&a[2]<=1&&a[4]<=1)
{
cmp1[0] = OneStep(num[a[1]][0],num[a[1]][1],a[2]);
cmp1[1] = OneStep(num[a[1]][2],num[a[1]][3],a[4]);
sort(cmp1);
}
else if(a[3]>=2&&a[2]<=1&&a[4]>=2)
{
cmp1[0] = OneStep(num[a[1]][0],num[a[1]][1],a[2]);
cmp1[1] = num[a[1]][2];
cmp1[2] = num[a[1]][3];
sort(cmp1);
}
else if(a[3]>=2&&a[2]>=2&&a[4]<=1)
{
cmp1[0] = OneStep(num[a[1]][2],num[a[1]][3],a[4]);
cmp1[1] = num[a[1]][0];
cmp1[2] = num[a[1]][1];
sort(cmp1);
}
else
{
cmp1[0] = num[a[1]][0];
cmp1[1] = num[a[1]][1];
cmp1[2] = num[a[1]][2];
cmp1[3] = num[a[1]][3];
sort(cmp1);
}
}
else if(a[0] == 3)
{
if(a[2]>=2&&a[3]<=1)
{
cmp1[0] = OneStep(num[a[1]][1],num[a[1]][2],a[3]);
cmp1[1] = num[a[1]][0];
cmp1[2] = num[a[1]][3];
sort(cmp1);
}
else if(a[2]<=1&&a[4]>=2)
{
cmp1[0] = OneStep(num[a[1]][0],OneStep(num[a[1]][1],num[a[1]][2],a[3]),a[2]);
cmp1[1] = num[a[1]][3];
sort(cmp1);
}
else
{
cmp1[0] = num[a[1]][0];
cmp1[1] = num[a[1]][1];
cmp1[2] = num[a[1]][2];
cmp1[3] = num[a[1]][3];
sort(cmp1);
}
}
return cmp1;
}bool IsSame(int *a,int *b)
{
bool bRet = true;
float *aa,*bb,aaa[4],bbb[4];
aa = Analysis(a);
for(int i=0;i<4;i++)
{
aaa[i] = aa[i];
}
bb = Analysis(b);
for(int i=0;i<4;i++)
{
bbb[i] = bb[i];
}
for(int i=0;i<4;i++)
{
if(abs(aaa[i]-bbb[i]) > MINVALUE)
bRet = false;
}
return bRet;
}void filter()
{
for(int i = 0;i<200;i++)
for(int j = 0;j<200;j++)
{
if(i!=j&&op[i][0]!=-1&&op[j][0]!=-1&&IsSame(op[i],op[j]))
{
op[i][0] = -1;
break;
}
}
}void ShowAnswer()
{
for(int i = 0;i<200;i++)
{
if(op[i][0] == 1)
{
cout<<\"(\"<<\"(\"<<num[op[i][1]][0]<<ToOperator(op[i][2])<<num[op[i][1]][1]<<\")\"
<<ToOperator(op[i][3])<<num[op[i][1]][2]<<\")\"<<ToOperator(op[i][4])<<num[op[i][1]][3]<<endl;
}
else if(op[i][0] == 2)
{
cout<<\"(\"<<num[op[i][1]][0]<<ToOperator(op[i][2])<<num[op[i][1]][1]<<\")\"
<<ToOperator(op[i][3])<<\"(\"<<num[op[i][1]][2]<<ToOperator(op[i][4])<<num[op[i][1]][3]<<\")\"<<endl;
}
else if(op[i][0] == 3)
{
cout<<\"(\"<<num[op[i][1]][0]<<ToOperator(op[i][2])<<\"(\"<<num[op[i][1]][1]
<<ToOperator(op[i][3])<<num[op[i][1]][2]<<\")\"<<\")\"<<ToOperator(op[i][4])<<num[op[i][1]][3]<<endl;
}
}
}void main()
{
float a[4],sum=24;
cout<<\"Input four datas:\";
cin>>a[0]>>a[1]>>a[2]>>a[3];
intit(a);
run(sum);
filter();
ShowAnswer();
}
[此贴子已经被作者于2007-8-22 16:42:05编辑过]