/*----------------------------------------------------------
以下代码(约300行)给出24点游戏较严格的“独立解”
不仅继续禁止“/1”(除1)而且不允许“*1”(乘1)泛滥成灾。例如:对于
1、1、11、13,第21楼程序给出的算式如下:
13+11+1-1=24
(13+11)*1*1=24
(13*1+11)*1=24
13*1+11*1=24
13*1*1+11=24
(11*1+13)*1=24
11*1*1+13=24
现在这个改进版程序给出的算式就只有头2个:
13+11+1-1=24
(13+11)*1*1=24
现在这个程序在“+1-1”仍有点泛滥。如, 对于 1、1、4、6 给出
6*4*1*1=24
6*4+1-1=24
(6+1-1)*4=24 <--- 是不是有点泛滥?
(4+1-1)*6=24 <--- 是不是有点泛滥?
本程序认为“2*2”与“2+2”不等价
特色在于引入“记忆库”以抑制非独立算式的出现!详见以下红色代码
------------------------------------------------------------*/
#define TEN 10 //“记忆库”的大小
char save[20][TEN]; int isav;
void Save(int type, int a,int op1,int b,int op2,int c)
{
if(isav < TEN)//防止“记忆库”溢出
{
save[isav][0]=type;
save[isav][1]=a;
save[isav][2]=op1;
save[isav][3]=b;
save[isav][4]=op2;
save[isav][5]=c;
isav++;
}
}
int Found(int type, int a,int op1,int b,int op2,int c)
{
int is;
for(is=0;is<isav;is++)
{
if(op1*op2==1)
{if(save[is][1]+save[is][3]+save[is][5]==a+b+c)return 1;}
else
{
if(type-save[is][0])continue;
if(a-save[is][1]||b-save[is][3]||c-save[is][5])continue;
if(op1==save[is][2] && op2==save[is][4])return 1;
}
}
return 0;
}
#include<stdio.h>
int MAX=13;//扑克牌的最大点数,如果把J,Q,K算进去,则MAX=13
int way;//用于统计某组(4张)牌实现“24”的独立解的个数。每发现1种就way++。若所有方案试遍,依然way==0,则显示failure(无解)。
void print2(char *format,int a,char o1,int b,char o2,int c,char o3,int d)
{
way++;
if(way==1)printf("\n");
//printf("(%02d)",way);
printf(format,a,o1,b,o2,c,o3,d);
}
int OP(int x,int iop,int y)
{
if(iop==1)return x>=y ? x+y:-9999;
if(iop==2)return x>=y ? x-y:-9999;
if(iop==3)return x>=y ? x*y:-9999;
if(iop==4)if(y && y-1 && x%y==0)return x/y;
return -9999;
}
int op(int x,int iop,int y)
{
if(iop==1)return x+y;else
if(iop==3)return x*y;else
return OP(x,iop,y);
}
int quan_pai_lie(int a[],int n)
//这个俺自编的全排列函数很有特色。功能如下
//int型数组 a[ ](n个元素)既是入口参数,也是出口参数。
//进入时要求从大到小排列,如{5,4,3,2,1}。调用1次就变成
//{5,4,3,1,2},再调用就变成{5,4,2,3,1},依此类推。函数
//的返回值通常是1,表示还有未尽的排列;如果返回0,则表示
//给出的排列已经全了。于本例,就是到达{1,2,3,4,5}状态。
//如果初始状态为{1,2,4,5,3},调用后相继出现{1,2,4,3,5}
//{1,2,3,5,4}最终{1,2,3,4,5}。该函数还能正确对待重复
//元素: 设n=4,最初{5,5,5,1},调用后相继出现{5,5,1,5}、
//{5,1,5,5}最终定格在{1,5,5,5}。
//【注】欲颠倒排序方向,请关注末尾带////的行
{ //from 4321 to 1234
int i,j,k,temp,t;
for(k=n-1;k>0;k--)
if(a[k-1]>a[k])break; ////改为a[k-1]<a[k]
if(k==0)return 0;
temp=a[k-1];i=k;
for(j=k+1;j<n;j++)
if(temp>a[j]&&a[j]>a[i])i=j; ////两个">"都改为"<"
a[k-1]=a[i];a[i]=temp;
for(i=k;i<n-1;i++)
for(j=k;j<n-1+k-i;j++)
if(a[j+1]>a[j])
////改为a[j+1]<a[j]
{t=a[j];a[j]=a[j+1];a[j+1]=t;}
return 1;
}
//下面的“宏”替换掉了凶巴巴的三重循环,而且1行顶3行
#define DO(I,a1,a2, J,m1,m2, K,z1,z2) for(K=z1;K<=z2;K++)for(J=m1;J<=m2;J++)for(I=a1;I<=a2;I++)
int main( void )
{
char os[ ]="@+-*/"; //os[ ]存放prinf()要用及的四则运算符。os[0]被弃之不用
int p[5];//p[i]记录第i张牌的点数(i=1,2,3,4)。元素p[0]弃之不用,所以开辟5元素的数组,下同
int A[5];//A[ ]可以说是p[ ]的拷贝。因p[i]是循环变量,为了不搅乱循环系统同时又要调用全排列
//函数,所以要将4张牌(的点数)复制到A[ ]中去,让A[ ]充当全排列函数的“实参”
int noslv=0; //对海量搜索过程中发现的无解出牌进行编号,并弄清总共有多少个无解出牌组
int op1,op2,op3; //连结4个数的3种四则运算,op1代表最先执行的运算
#define
a
A[1] //用“简变”代替“下标变量”
#define
b
A[2] //用“简变”代替“下标变量”
#define
c
A[3] //用“简变”代替“下标变量”
#define
d
A[4] //用“简变”代替“下标变量”
for(p[1]=
1 ;p[1]<=MAX;p[1]++) //全部
for(p[2]=p[1];p[2]<=MAX;p[2]++) //可能的
for(p[3]=p[2];p[3]<=MAX;p[3]++) //出牌
for(p[4]=p[3];p[4]<=MAX;p[4]++) //组合
{
isav=0;//“记忆库”指针清零,因为换了一副“新牌”
way=0; //“独立解法”计数器清零,因为换了“新牌”
printf("%d,%d,%d,%d: ",p[1],p[2],p[3],p[4]);//显示4张牌(小数在前,大数在后)
A[1]=p[4],A[2]=p[3],A[3]=p[2],A[4]=p[1];//让A[1]>=A[2]>=A[3]>=A[4]以满足全排列函数要求
//全加a+b+c+d,三加一减a+b+c-d,二加二减a+b-c-d模式:
DO(op1,1,2, op2,1,2, op3,1,2)
{
if(OP(OP(OP(a,op1,b),op2,c),op3,d)==24)
if( !(op2==2 && op3==1 && c==d) ) //只允许“+x-x”以避免等价解
print2("%d%c%d%c%d%c%d=24\n",a,os[op1],b,os[op2],c,os[op3],d);
}
//以上循环会遗漏“K,K,Q,Q”组合,为此补上“K-K+Q+Q”:
if(a==13 && b==13 && c==12 && d==12)
print2("%d%c%d%c%d%c%d=24\n",a,os[2],b,os[1],c,os[1],d);
//全乘a*b*c*d,三乘一除a*b*c/d,两乘两除a*b/c/d模式:
DO(op1,3,4, op2,3,4, op3,3,4)
{
if(OP(OP(OP(a,op1,b),op2,c),op3,d)==24)
{
if( !(op2==4 && op3==3 && c==d) &&
!(op1==4 && op3==3 && d==b) &&
!(op1==4 && op2==3 && b==c) )
print2("%d%c%d%c%d%c%d=24\n",a,os[op1],b,os[op2],c,os[op3],d);
}
else if(b-c && OP(OP(OP(a,op1,c),op2,d),op3,b)==24 && op3==4)
print2("%d%c%d%c%d%c%d=24\n",a,os[op1],c,os[op2],d,os[op3],b);
else if(a-b && OP(OP(OP(b,op1,c),op2,d),op3,a)==24 && op3==4)
print2("%d%c%d%c%d%c%d=24\n",b,os[op1],c,os[op2],d,os[op3],a);
}
do //让某一组牌“遍历”所有的先后顺序:
{
DO(op1,1,2, op2,1,2, op3,0,0)
{
if(OP(OP(a,op1,b),3,OP(c,op2,d))==24) //(a±b)*(c±d)
print2("(%d%c%d)%c(%d%c%d)=24\n",a,os[op1],b,os[3],c,os[op2],d);
if(OP(OP(a,op1,b),op2,OP(c,4,d))==24 && op2==2) //(a±b)-(c/d)
print2("%d%c%d%c%d%c%d=24\n",a,os[op1],b,os[op2],c,os[4],d);
}
DO(op1,0,0, op2,1,2, op3,3,4)
{
if(OP(OP(a,3,b),op2,OP(c,op3,d))==24) //(a*b)±(c*d),(a*b)±(c/d)
{
if(b*d==1)
{
if(!Found(4, a,op2,c,' ',' ')){Save(4, a,op2,c,' ',' ');print2("(%d%c%d)=24\n",a,os[op2],c,' ',' ',' ',' ');}
}
else if(a*b==12)
{
if(b==1){Save(2, a,op2,c,op3,d);Save(2, c,op3,d,op2,a);}
if(!Found(3, c,op3,d,op2,12)){Save(3, a,3,b,op2,OP(c,op3,d));goto prnt;}
}
else if(b==1)
{
if(!Found(2, a,op2,c,3,d)){Save(2, a,op2,c,3,d);goto prnt;}
}
else if(d==1)
{
if(!Found(2, a,3,b,op2,c)){Save(2, a,3,b,op2,c);goto prnt;}
}
else
{
prnt: print2("%d%c%d%c%d%c%d=24\n",a,os[3],b,os[op2],c,os[op3],d);
}
}
if(op3==4 && OP(OP(a,3,b),op3,OP(c,op2,d))==24) //(a*b)/(c±d)
{
print2("%d%c%d%c(%d%c%d)=24\n",a,os[3],b,os[op3],c,os[op2],d);
}
}
DO(op1,1,2, op2,1,2, op3,0,0) //(a±b±c)*d
{
if(OP(OP(a,op1,b),op2,c)*d==24 && !(op1==2 && op2==1) && !(op1==op2 && b<c))
{
if(d==1 && !Found(1, a,op1,b,op2,c))
{
Save(1, a,op1,b,op2,c);
Save(1, a,op2,c,op1,b);
if(op1==1){Save(1, b,1,a,op2,c);Save(1, b,op2,c,1,a);}
print2("(%d%c%d%c%d)%c%d=24\n",a,os[op1],b,os[op2],c,os[3],d);
}
else if(d-1)
{
print2("(%d%c%d%c%d)%c%d=24\n",a,os[op1],b,os[op2],c,os[3],d);
}
}
}
DO(op1,0,0, op2,1,2, op3,3,4)
{
//(a*b±c)*d,(a*b±c)/d
if(op(OP(OP(a,3,b),op2,c),op3,d)==24)
{
if(a*b==c)Save(2, c,1,a,3,b);
if(d*b==1)
{
if(!Found(4, a,op2,c,' ',' ')){Save(4, a,op2,c,' ',' ');print2("(%d%c%d)=24\n",a,os[op2],c,' ',' ',' ',' ');}
}
else if(d==1)
{
if(!Found(2, a,3,b,op2,c)){Save(2, a,3,b,op2,c);goto disp;}
}
else if(b==1)
{
if(!Found(2, a,op2,c,op3,d)){Save(2, a,op2,c,op3,d);goto disp;}
}
else
{
disp:
print2("(%d%c%d%c%d)%c%d=24\n",a,os[3],b,os[op2],c,os[op3],d);
}
}
//(c±a*b)*d,(c±a*b)/d
if(op(OP(c,op2,OP(a,3,b)),op3,d)==24)
{
if(d*b==1)
{
if(!Found(4, c,op2,a,' ',' ')){Save(4, c,op2,a,' ',' ');print2("(%d%c%d)=24\n",c,os[op2],a,' ',' ',' ',' ');}
}
else if(a*b==c && Found(2, c,op2,a,3,b) && d-1)
{
;;;; //do nothing
}
else if(d==1)
{
if(!Found(2, c,op2,a,3,b)){Save(2, c,op2,a,3,b);goto done;}
}
else if(b==1)
{
if(!Found(2, c,op2,a,op3,d)){Save(2, c,op2,a,op3,d);goto done;}
}
else
{
done:
print2("(%d%c%d%c%d)%c%d=24\n",c,os[op2],a,os[3],b,os[op3],d);
}
}
}
DO(op1,1,2, op2,0,0, op3,1,4)
{
//(a±b)*c±d,(a±b)*c*d,(a±b)*c/d
if(op(OP(a,op1,b)*c,op3,d)==24 && !(op3==3 && c<d))
{
if(c*d==1 && op3==3)
{
if(!Found(4, a,op1,b,' ',' ')){ Save(4, b,op1,a,' ',' ');Save(4, a,op1,b,' ',' ');goto view; }
}
else if(c==1 && op3<3)
{
if(!Found(1, a,op1,b,op3,d)){ Save(1, a,op1,b,op3,d);goto view; }
}
else if(d==1 && op3==3)
{
if(!Found(2, a,op1,b,3,c)){ Save(2, a,op1,b,3,c);goto view; }
}
else
{
view:
print2("(%d%c%d)%c%d%c%d=24\n",a,os[op1],b,os[3],c,os[op3],d);
}
}
//(a±b)/c±d
if(op(OP(OP(a,op1,b),4,c),op3,d)==24 && op3<3)
{
print2("(%d%c%d)%c%d%c%d=24\n",a,os[op1],b,os[4],c,os[op3],d);
}
}
//a*b±c±d, a/b±c±d, a*b*c±d, a*b/c±d
DO(op1,3,4, op2,1,4, op3,1,2)
{
if(op(op(OP(a,op1,b),op2,c),op3,d)==24 && !(op2==op3 && c<d) && !(op2==2 && op3==1)
&& !(op1*op2==9 && b<c) && !(op1==4 && op2==3))
{
if(op1*op2==9 && b*c==1)goto pass;
if(b==1)
{
if(!Found(1, a,op2,c,op3,d)){Save(1, a,op2,c,op3,d);goto here;}
}
else if(c==1 && op2>2)
{
if(!Found(2, a,op1,b,op3,d)){Save(2, a,op1,b,op3,d);goto here;}
}
else
{
here: print2("%d%c%d%c%d%c%d=24\n",a,os[op1],b,os[op2],c,os[op3],d);
}
pass:
if(b==1 && op2<3||c==1 && op1==3)goto next;
}
}
// 以下涉及实型除法
next:
for(op2=1;op2<=2;op2++)
//(a/b±c)*d
if(op(a,op2,b*c)*d==24*b && b-1)
print2("(%d%c%d%c%d)%c%d=24\n",a,os[4],b,os[op2],c,os[3],d);
if((b*c-a)*d==24*b && b-1) //(c-a/b)*d
print2("(%d%c%d%c%d)%c%d=24\n",c,os[2],a,os[4],b,os[3],d);
if(d*b==(c*b-a)*24)
//d/(c-a/b)
print2("%d%c(%d%c%d%c%d)=24\n",d,os[4],c,os[2],a,os[4],b);
if(d*b==(a-c*b)*24)
//d/(a/b±c)
print2("%d%c(%d%c%d%c%d)=24\n",d,os[4],a,os[4],b,os[2],c);
}
while(quan_pai_lie(A+1,4));
if(!way)printf("failure(%d)\n",++noslv);//无效组合序号及总数noslv
}
return(0);
}
[
本帖最后由 yu_hua 于 2010-11-26 10:24 编辑 ]