time 
设为首页】【收藏本站
当前位置: 主页 > 程序设计 > C\C++\VC > C语言 > 计算24点的C程序(穷举法)

计算24点的C程序(穷举法)

时间:2009-09-20 23:31 点击:1207次 字体:[ ]




    几年前,女朋友很喜欢和我玩计算24点的游戏,来测试谁的反应更快一些,结果我总是输而不得不承认在这方面她比我强。于是我就用C和我可怜的数据结构知识写了这个程序来挽回点面子,结果竟然让她很佩服。现在女朋友已经成功升级成老婆了,这程序也久没有用武之地了,就放在这里给和我们有一样故事的人们参考一下吧!

 //24点分析(穷举法)
//
#include
#include
#include

typedef struct D_NODE
{
        int data;
        struct D_NODE *left,*right;
} NODE24;
NODE24 head;

int res=24;

int maketree(int *src,int *i, NODE24 *p)
{
        int d=src[*i];
        (*i)++;
        switch (d)
        {
        case '+':
        case '-':
        case '*':
        case '/':
                p->left=new NODE24;
                p->right=new NODE24;
                p->data=d;
                maketree(src,i,p->left);
                maketree(src,i,p->right);
                break;
        default:
                p->data=d;
                p->left=NULL;
                p->right=NULL;
        }
        return 0;
}

int cmaketree(NODE24 *p)
{
        int c;
        c=getch();
        putchar(c);
        switch (c)
        {
        case '+':
        case '-':
        case '*':
        case '/':
                p->left=new NODE24;
                p->right=new NODE24;
                p->data=c;
                cmaketree(p->left);
                cmaketree(p->right);
                break;
        default:
                p->data=c-'0';
                p->left=NULL;
                p->right=NULL;
        }
        return 0;
}

int work(struct D_NODE *d)
{
        int res=0;
        if (d->left==NULL&&d->right==NULL)
                res=d->data;
        else
        {
        int a,b;
        a=work(d->left);
        b=work(d->right);
        switch (d->data)
        {
          case '+':
                res=a+b;//work(d->left)+work(d->right);
                break;
          case '-':
                res=a-b;//work(d->left)-work(d->right);
                break;
          case '*':
                res=a*b;//work(d->left)*work(d->right);
                break;
          case '/':
                if (b!=0)
                  res=(a%b==0)?a/b:-79;
                else
                  res=-79;
                //res=work(d->right)?work(d->left)/work(d->right):-79;
                break;
        }
        }
        return res;
}

int destroy(struct D_NODE *d)
{
        if (d->left==NULL&&d->right==NULL)
                delete d;
        else
        {
                destroy(d->left);
                d->left=NULL;
                destroy(d->right);
                d->right=NULL;
                if (d != &head)
                  delete d;
        }
        return 0;
}

int show(struct D_NODE *d)
{
        if (d->left==NULL && d->right==NULL)
                printf("%d",d->data);
        else
        {
                printf("(");
                show(d->left);
                printf("%c",d->data);
                show(d->right);
                printf(")");
        }
        return 0;
}

/* int input()
{
        //int buf[30]={'*','+','2','4','+','2','3'},idx=0;
        //maketree(buf,&idx,&head);

        int buf[20],idx=0;
        printf("\nPlease Input:");
        for (idx=0;idx<20;idx++)
        {
          buf[idx]=getch();
          printf("%c",buf[idx]);
        }
        idx=0;
        maketree(buf,&idx,&head);
        return 0;
}  */

#define test(p1,p2,p3,p4,p5,p6,p7) {exp[0]=(p1),exp[1]=(p2), \
        exp[2]=(p3),exp[3]=(p4),exp[4]=(p5),exp[5]=(p6),exp[6]=(p7); \
        idx=0; \
        maketree(exp,&idx,&head); \
        if (work(&head)==res) \
        { \
           found++;printf("%5d: ",found);show(&head);\
           if (!(found%3)) printf("\n");\
        } \
        destroy(&head);\
        }

//      printf("%d,%d,%d,%d,%d,%d,%d\n",p1,p2,p3,p4,p5,p6,p7); \

int test24()
{
        int num[4],opc[4]={'+','-','*','/'},exp[20];
        int i1,i2,i3,i4,ic1,ic2,ic3,idx,found=0;

        char prompt[]="24点游戏分析\n易华卫 12/17/2000\n";
        printf("%s",prompt);
        for (i1=0;i1<4;i1++)
        {
          printf("请输入第%d个数字: ",i1+1);
          scanf("%d",num+i1);
          //num[i1]=num[i1]%13+1;
        }
        printf("\n你已经输入了:%d,%d,%d,%d四个数字!\n",num[0],num[1],num[2],num[3]);
        printf("\n请输入要计算的结果值,(当然二十四点就输入24啦!):");
        scanf("%d",&res);
        printf("OK! 按任意键就可以开始了!\n");
        getch();
        for (i1=0;i1<4;i1++)
        for (i2=0;i2<4;i2++)
        if (i2!=i1)
          for (i3=0;i3<4;i3++)
          if (i3!=i1&&i3!=i2)
                for (i4=0;i4<4;i4++)
                if (i4!=i1&&i4!=i2&&i4!=i3)
                  for (ic1=0;ic1<4;ic1++)
                  for (ic2=0;ic2<4;ic2++)
                  for (ic3=0;ic3<4;ic3++)
                  {
                         test(opc[ic1],opc[ic2],opc[ic3],num[i1],num[i2],num[i3],num[i4]);
                         test(opc[ic1],opc[ic2],num[i1],opc[ic3],num[i2],num[i3],num[i4]);
                         test(opc[ic1],opc[ic2],num[i1],num[i2],opc[ic3],num[i3],num[i4]);
                         test(opc[ic1],num[i1],opc[ic2],opc[ic3],num[i2],num[i3],num[i4]);
                         test(opc[ic1],num[i1],opc[ic2],num[i2],opc[ic3],num[i3],num[i4]);
                  }
        printf("\n共找到了 %d 条正确的计算方法!(很抱歉,我没有处理交换率*^_^*)\n",found);
        return 0;
}

main()
{
//      fflush(stdin);
//      input();
//      cmaketree(&head);
//      printf("\n=%d\n",work(&head));
        test24();
        return 0;
}



本文地址 : http://www.fengfly.com/plus/view-77302-1.html
标签: 穷举法
------分隔线----------------------------
最新评论 查看所有评论
发表评论 查看所有评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
验证码:
本栏分类