游戏24点课程设计报告

一.题目:

分析类:

计算24点：任意输入4位数字，利用+,-,*,/四则运算使之得到结果 24。输出所有不同算法的计算表达式，可为运算优先级而使用括号。

二.问题分析：

1.全面性：

此问题要求输出结果为24的计算表达式，并且要求输出要全面，我考虑用for循环与递归实现遍历来保证输出的全面性，考虑到递归的‘一归到底',每一次完整递归都代表一种算法(详情见算法)。

2.输出的判定和四位数字的类型：

在输出的时候对最后结果等于24的判别，因为考虑到有除法，有可能中途结果可能会出现不能整除的情况与小数，所以输出的四个数都设为float型，且输出判定的时候用近似判定法，而不直接写让最后结果等于24(详情见算法)。

3.重复性：

如果用循环与递归保证了输出24的表达式的全面性，但不可避免的会出现重复，才开始我想在遍历与递归时，加一些限定条件来消除重复但是这样做不但会出错，还不能保证它的输出全面性。于是我想在输出的时候加限定条件，使重复的只输出一遍。

但是对于输入的那4位数字中如果有重复的话，程序结果还是会出现重复的,此问题尚未解决.(详情见算法)。

4.括号问题的处理：

对于括号问题，我规定对每一步的计算表达式，除了*之外，+，-,\都加上括号，即让程序按自己规定的方向执行，输出的括号只是让人能看懂，其实在运算时不起作用(详情见算法)。

5.输出：

输出方面我以为用了遍历所以在每一层遍历都把运算表达式存到一个较大的数组中，在输出的时候如果满足输出条件(在遍历时纪录每次递归的第一次运算的结果，第一次运算的运算符，第二次运算的结果，第二次运算的运算符和第三次运算的运算符)，就直接把那个数组里的内容输出，遍历会直接去寻找表达式里的表达式(详情见算法)。

三.算法描述（源代码里有更详尽解释）：

1.主要方法：

遍历与递归。

2.主要思路：

把输入的四个数放在一个数组n[4]中，然后任取其中任意两个（不能取同一个--既不能出现自己和自己运算的情况），然后用一个for和一个switch语句来实现这两个数的加减乘除运算， 然后把运算的结果放到另一个数组b[4]中并记录此运算的表达式（放到一个大一点的数组tm[4][25]中），同时把其他两个没用到的数也放到该数组中，然后重复以上过程（用遍历实现），最后先判定是不是最后一层运算，是的话在判定最后结果是不是等于24，等于24的话就把那个纪录运算式的数组输出。

然后考虑到不能出现重复的（例如：1*2*3*4和2*4*3*1等等）我在遍历的同时记录了第一次运算的结果，第一次运算的运算符，第二次运算的结果，第二次运算的运算符和第三次运算的运算符，对输出的时候做限定（例如：对运算符全*的只输出一遍等等）。在有一次输出后我还定义了另外两个数组用来分别保存上一次输出的第一次运算的结果，第一次运算的运算符，第二次运算的结果，第二次运算的运算符和第三次运算的运算符，来解决重复输出的问题，不过此种做法有可能导致输出的时候不全。（此问题尚未解决）即还不能同时保证全面性与不重复性。

３．主要函数与数组：

主要有两个函数，一个主函数，用来输入四个数，并且完成初始化。还有一个count(float a[],char tem[][25],int n)函数，用来完成遍历，递归，与输出，其中a[]中存放要输入的4个数，tem[][25]中放计算步骤，n是a[]中元素的个数。在函数体内还定义了b[4]和tm[4][25]用来完成递归，函数一开始先判定输出条件（是否是第三次运算，结果是否等于24），如果不满足条件就做遍历与递归，遍历用了3个for循环和1个switch语句来完成，然后为递归准备数据，用sprintf函数将运算式输出到数祖tm[]中，在输入运算式的同时把括号输到tm[]中，然后提取第一次运算的运算符与运算结果，提取第二次运算的运算符与运算结果和提取第三次运算的运算符，然后备份没用到的数据（为递归之用）。接下来进行递归重复上述过程。

4.算法流程图：(简化的流程图，源代码里有更详尽解释)

                                                  

四.源代码及其分析

#include<iostream.h>

#include<math.h>

#include<string.h>

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define MAX   4;//最大输入个数。

int  k=0;//全局变量 用来判定是否有解

char tp[4]={0,0,0,0},tpt[2000]={0},tptt[2000]={0},tre[2000]={0};//用来消除重复。tp[1-3]用来记录运算式中的3个运算符。

char op[4]={'+','*','-','/'};

void count(float a[],char tem[][25],int n);//a[]中存放要输入的4个数，tem[][25]中放计算步骤，n是a[]中元素的个数。

int  q=0,p=0,e=0,w=0,t=0,r=0,g=0,h=0,v=0,u=0,tu=0,te=0;//用于消除重复。

float group[2]={0,0},flow[20]={0},flo[20]={0};//

//tem[][25]中放计算步骤，n是a[]中元素的个数。

void main()

{

  char br=1;

  int d;

while (br==1)

{  float number[4];//放四个数。

  char temp[4][25]; //放运算式，初始化放四个数。

  cout<<"please insert four numbers:";

  cout<<endl;

  for(d=0;d<4;d++)

     cin>>number[d];//输入四个数

  

  for(d=0;d<4;d++)

  {    

        sprintf(temp[d],"%d",(int) number[d]);

  }//初始化temp[d]；

 

  count(number,temp,4);//调用count函数。

  if (k==0)

      cout<<"no answer";

  cout<<endl; 

  cout<<"press 0 end"<<endl;

  scanf ("%d",&br);

}

}

void count(float a[],char tem[][25],int n)

{

    float b[4];

    char  tm[4][25];//b[4]和t[4][]作用同上（为 递归之用）。

    int  i,j,l,x,y;//i,j用来作双循环；l用来作加减乘除的开关；x,y为后面准备递归数据之用。

/************************************************************************************/

    //输出部分

    if(n==1)

    {      

            if (fabs(a[0]-24)<0.00001)//因为要考虑除法所以用fabs函数求绝对值与24比较。

            //相当于等于24时的情况。

            {  

/************************************************************************************/

//以下是限定输出条件：              

                if(tp[3]=='-'&&tp[2]=='-'&&tp[1]=='*')

                 {

                        if(te==0)

                        {

                        cout<<"\n有解为"<<tem[0]<<"=24";//最后的运算式存在tem[0]中

                            k=1;

                            te=1;

                        }

                }//对运算符全*的只输出一遍。

                else if(tp[3]=='+'&&(tp[2]=='+'||tp[0]=='+')&&tp[1]=='+')

                 {

                        if(t==0)

                        {

                        cout<<"\n有解为"<<tem[0]<<"=24";//最后的运算式存在tem[0]中

                            k=1;

                            t=1;

                        }

                }//对运算符全+的只输出一遍。

                   

                else if(tp[3]=='+'&&(tp[2]=='*'||tp[0]=='*')&&tp[1]=='+')

                 {

                        if(g==0)

                        {

                        cout<<"\n有解为"<<tem[0]<<"=24";//最后的运算式存在tem[0]中

                            k=1;

                            g=1;

                        }

                }

                else if((tp[3]=='-'&&tp[2]=='+')||(tp[3]=='+'&&tp[2]=='-'))

                {

                        if(w==0)

                        {

                        cout<<"\n有解为"<<tem[0]<<"=24";//最后的运算式存在tem[0]中

                            k=1;

                            w=1;

                        }

                }//对于第二次运算时取到b[0]时，第一第二个运算符是+,-或-，+的只输出一遍。

                else if(tp[3]=='+'&&tp[2]=='+')

                {

                        if(u==0)

                        {

                        cout<<"\n有解为"<<tem[0]<<"=24";//最后的运算式存在tem[0]中

                            k=1;

                            u=1;

                        }

                }//对于第二次运算时取到b[0]时，第一第二个运算符是+,+的只输出一遍

                    else if(tp[3]=='*'&&tp[2]=='*')

                    {

                        if(r==0)

                        {

                        cout<<"\n有解为"<<tem[0]<<"=24";//最后的运算式存在tem[0]中

                            k=1;

                            r=1;

                        }

                    }

                    else if(tp[3]=='*'&&tp[0]=='*'&&tp[1]=='+')

                    {

                        if(tu==0)

                        {

                        cout<<"\n有解为"<<tem[0]<<"=24";//最后的运算式存在tem[0]中

                            k=1;

                            tu=1;

                        }

                    }

                   

                else

                {   for(h=0;h<q;h++)

                    {

                        if(group[0]==flow[h])

                        {

                             if(tp[3]==tpt[h])

                             {

                                if(tp[2]=tptt[h])

                                {              

                                    if(group[1]==flo[h])

                                    {

                                        if(p==0)

                                    {

                        cout<<"\n有解为"<<tem[0]<<"=24";//最后的运算式存在tem[0]中

                                            k=1;

                                            p=1;

                                        }

                                    }

                                }

                             }

                        }                              

                            else if(h==q-1)                                                            

                        {

                           cout<<"\n有解为"<<tem[0]<<"=24";//最后的运算式存在tem[0]中

                           k=1;

                        }

                    }

                }

            flo[q]=group[1];//限定条件初始化。

            flow[q] =group[0];//限定条件初始化。

            tpt[q]=tp[3];//限定条件初始化。

            tptt[q]=tp[2];//限定条件初始化。

            tre[q]=tp[1];//限定条件初始化。

            tp[0]=0;

            tp[1]=0;

            tp[2]=0;

            tp[3]=0;

            q=q+1;             

        }

    }

/************************************************************************************/

    //运算部分：

    if(n>1)//该条件语句用来结束一次递归。

    {  

        for(i=0;i<n;i++)//对n个 数做'+','*','-','/'遍历。

    {

        for(j=0;j<n;j++)

        {

            if(i==j)

                continue;

            for(l=0;l<4;l++)//进行四则运算。

            {

                switch(l)

                {

                    case(0): if(n==2)

                            {  

                                b[0]=a[0]+a[1];

                                break;

                             }                             

                        else b[0]=a[i]+a[j];

                        break;

                    case(1):if(n==2)

                                {                                                                      

                                    b[0]=a[0]*a[1];

                                    break;                         

                                }                  

                            else    b[0]=a[i]*a[j];

                        break;                 

                                                 //对加和乘做遍历时去除a[i]+a[j]与a[j]+a[i]等情况。

                    case(2):  

                        b[0]=a[i]-a[j];

                        break;

                    case(3):

                        if(a[j]==0)

                                break;

                                b[0]=a[i]/a[j];

                        break;  //对'-'和'/'做遍历时考虑a[i]-a[j]与a[j]-a[i]的不同。

                        default:break;

                }//switch

                if(l!=3||a[j]!=0)//为递归准备数据(把没用到的数也放到b[]与tm[]中)。

                {  

                    {if(l==0||l==2||l==3) //用sprintf函数将运算式输出到数祖tm[]中。

                    //在输入运算式的同时把括号输到tm[]中。

                    sprintf(tm[0],"(%s%c%s)",tem[i],op[l],tem[j]);             

                    if(l==1)

                        sprintf(tm[0],"%s%c%s",tem[i],op[l],tem[j]);

                    }

                    {if(n==3)//提取第一次运算的运算符与运算结果。

                    {  

                        group[1]=b[0];

                        if(i!=0&&j!=0)

                        tp[0]=op[l];

                        else

                        tp[n-1]=op[l];

                       

                    }

                    else if(n==4)//提取第二次运算的运算符与运算结果。

                    {

                        tp[n-1]=op[l];

                        group[0]=b[0];

                    }

                    else         //提取第三次运算的运算符。 

                        tp[n-1]=op[l];

                   

                    }

                    for(x=0,y=1;x<n;x++)//备份没用到的数据（为递归之用）。

                     {

                         if(x!=i&&x!=j)

                           {

                               b[y]=a[x];

                               strcpy(tm[y],tem[x]);//复制字符串。

                               y++;

                           }//if

                     }//for

                }//if

                count(b,tm,n-1);

            }//第三层for循环结束。

        }//第二层for循环结束。

    }//for循环结束。

    }//if 结束。

}//count函数结束。

五.运行数据测试

1．输入数据（以空格分开）

2．回车后出运行结果

3．按0退出

六.心得体会

设计本程序，起因于儿时的游戏24点，游戏简单富有思考价值。程序数据结构是用的树，每一片叶子代表一种算法，从根开始为一个结点（第一层，第一次计算有48种情况，所以第二层有48个结点，第二次计算有24种情况，所以第三层有48*24个结点，即第二层的每一个结点有24个分支，最后一次计算有两种情况，所以第三层的每个结点都有2个分支，即共有2304个叶子。每一条分支都是一种情况，所以共2304种情况。每一个叶子结点代表着一次递归的结束。总体来说，就是对这颗树做遍历，找出符合要求的运算式。主要就是用遍历和递归来实现，独立做完程序，让我对c++有更深一步的了解，也有进一步的掌握。值得提出的是，本程序还有不足之处：本程序对于重复性问题还未有完全解决，但可以消掉一部分重复。为了更好的学习，我还望请老师多多指点，今后可以更新程序，把其所有不足之处都解决，也让自己能有所提高。