【原创】24点游戏程序之一 - C语言论坛

得分:0

/*----------------------------------------------------------
        以下代码(约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 编辑 ]