数据结构课设 计算24点

武汉理工大学《数据结构》课程设计说明书PAGE8目录1．问题分析…………21.1问题描述……21.2问题分析……22．开发平台…………33．程序设计…………33.1用来消去重复的全局变量的定义…………33.2主程序设计…………………33.3算法设计……54．程序调试…………74.1程序错误……74.2运行结果……85．自我评价和总结…………………106．参考文献…………107．附录………………11计算24点1问题分析1.1问题描述有2、3、4、5、6、7、8、9、10、J、Q、K、A共13张牌，编一程序，判断对任意给定的4张牌，能否在进行加、减、乘、除运算后，其运算结果等于24。其中J按11计算，Q按12计算，K按13计算，A按1计算。（1）能接受用户输入的4张牌点，并进行24点判断，并输出判定结果。（2）若能得到结果24，要求输出至少一个可得到该结果的计算表达式。例如，对给定的2，7，J，Q，按下述方法计算可得到结果24：(J-7)*(Q/2)或Q*(J-2-7)（3）若不能得到24点，亦应输出提示。1.2问题分析1.2.1输入根据题意，输入要求能用数字或字符输入，数字为从2至10，字符为J、Q、K、A。在进行计算时将字符型转换成数字，J、Q、K、A分别代表11、12、13、1。当输入数据不符合要求时显示“重新输入”，直至输入数据满足要求。1.2.2输出问题要求是四个数组成的方程式能得出24，但因为除法运算中精度的影响，有些运算式并不能得出准确的24，所以将判断条件由等于24改为与24相比差距小于0.00001。然后当输入的四个数不能组成24时，输出“该牌点不能组成24点”。当输入的数据能组成24点时，用字符数组输出该组方程式。1.2.3测试用的数据合法数据有：（1）任务中的2、7、J、Q（2）1、2、3、5（3）1、5、7、9（4）4、5、6、8（5）J、Q、K、7等等非法数据有：（1）0、152开发平台MicrosoftVisualStudio2008专业版3程序设计采用穷举法，将四个数能组成的所有方程都进行计算，如果能得出24，则把相应的计算式输出。其中四个数字不能重复，运算符可以重复。具体方法是利用for循环选取四个数进行组合，然后将运算分成三层利用递归一层层计算并保存。但是因为利用的是穷举法，而且乘加法有交换律，所以有很多方程式是重复的，在输出时加入一点限定条件来消除重复。但是还是有少量的方程式依然重复，这个问题还是无法解决。在括号的问题上我的方法是程序进行运算时括号并不起作用，只在输出时加入方程式然后输出。并且除了最后一次运算，前三次都加上括号。3.1用来消去重复的全局变量的定义为了消去重复先用opp[3]保存3个运算符，再根据运算符用ta、tb、t[5][20]来判断重复的第一个方程式是否已输出。3.2主程序设计原来是准备将输入的数字或字符存入char数组，然后转换为int型再存入数组。但是10这个数字算两个字符，进行输入时占了两个字符就出现了错误。用了很多方法进行改正还是总出现各种各样的问题，所以直接将输入J、Q、K、A改为输入11、12、13、1。这样输入的话检验错误输入的条件也变得容易了。对于输入的数据的合法性判断利用bool类型的flag（初始为false）来做判断，do…while循环进行校验。数据的合法在于数字是否在1~13的范围内和是否和前面输入的数字不同，只有当两者都满足时才将flag改为true时接受输入的数字，并保存。以下流程图为：其中的k为检测是否存在能得出24的方程式的判断标志，为全局变量。当其为0时表示不存在，为1是存在，初始时为0。3.3算法设计计算的主要函数为count(floata[],charopef[][25],intn)函数。其参数a[]传递的是已计算后得出的结果和未计算的数字，opef[][25]传递的是已计算的公式和未计算的数字，n是a[]中有效的的数字个数。此外函数还有print(charopp[],charopef[][25])，judge(intt[],charopp[],charopef[][25])这两个函数，print函数用来输出已消去部分重复后的所有方程式，judge函数是print函数中的重复部分，单独弄成函数是为了方程的简洁。count函数的算法为：count(floata[],charopef[][25],intn)beginfloatb[4]charopeff[4][25]ifn=1&&|a[0]-24|<0.00001

thenprint(opp,opef)

elsebegin fori

←0ton forj

←0ton begin ifi=j thencontinue; elseform

←0to4 begin switch(m){ case(0):b[0]←a[i]+a[j]; break; case(1):b[0]←a[i]-a[j]; break; case(2):b[0]←a[i]*a[j]; break; case(3):ifa[j]=0 thenbreak; b[0]←a[i]/a[j]; break; end ifn=2 thenopeff[0]←’opef[i]’+’op[m]’+’opef[j]’; elseopeff[0]←’(‘+’opef[i]’+’op[m]’+’opef[j]’+’)’; opp[n-1]←op[m]; y←1 forx←0ton begin ifx!=i&&x!=j b[y]←a[x]; strcpy(opeff[y],opef[x]); y++; end count(b,opeff,n-1); end endendprint函数消去重复方程式的限定条件有：三个运算符全为*或+只输出一次；前两次运算符全为*或+的，第三次的运算符每种只输出一次；最后一次运算符为*或+的，前两次的运算符各种不同的组合输出一次；其余的全部输出；当有输出时将k改为1。judge函数作用是对print函数中第三步的两个运算符的不同组合进行筛选。4程序调试4.1程序错误调试过程中出现了两种错误，一种是语法错误，一种是算法错误，现摘录部分错误。4.1.（1）因为用了count函数使用了多重循环和递归所以经常忘记末尾的“}”符号；（2）循环参数定义在for语句中，但因多重循环太多，参数出现了重复，导致参数定义也重复了；（3）有时句尾忘记加;号；（4）忘记切换中英文输入法导致输入了中文字符，程序无法识别；4.1.2（1）按照题目要求在输入数据时本来是打算输入字符再转换，后来发现10这个数字太特殊了，如果是输入字符10占两个位置导致只输入了两个数据。并且输入的是字符的话对输入数据是否正确的判断会很难。（2）在main函数中对输入的数据进行判断开始并没有用标志进行判断，而是直接用if语句和for语句循环与之间的数据比较重复性来判断，结果发现数据即使重复了依然会被保存，例如第二个数据在重复提示输入正确数据一遍后就被保存了，接着第三个数据在重复提示输入正确数据两遍后依然会被保存。后来就将这段程序改为了利用flag标志来判断是否正确输入。（3）在main函数中，出现如下问题：第一个数字输入有效后，第二个数字即使不在1~13之间依然被储存。后发现是因为flag标志在第一个数字输入后被更新为true，第二个数字就被储存了，解决方案是将flag定义在for语句中。（4）在count函数中，switch语句中忘记加break语句，导致全进行的除法运算。（5）在count函数中，没有考虑到除法运算与其他运算的特殊之处：除数不能为0，程序的提示为：1>d:\visualstudio2008\projects\24点\24点.cpp(37):errorC2124:被零除或对零求模（6）在count函数中，将递归的函数写在了上一层的语句，导致运行失败。4.2运行结果4.2.1合法数据（1）（2）（3）(4)（5）4.2.2非法数据5自我评价和总结计算24的的这个游戏在小时候的时候常常玩，一直觉得很简单，但没想到做成程序却有点复杂，要能把所有可能的算法全部算出来。这个算法用三层for语句循环很容易就能得出，但是要将得出24的方程式输出就有困难了，于是这点难倒我了。分析了很多别人的算法后，我找到了一个方法就是使用递归，递归调用，从4个数算到3个数……将计算结果、运算符和运算公式一层层保存，当最后一层运算结束后保存的数据中就只剩下一个结果和运算方程式，再根据计算结果来输出保存的字符，然后循环计算不同的方程式。在最后输出的时候，我尽量地消去重复的方程式。但是限定的条件不好找，所以最后的结果里面还是有重复的方程式，而且存在并未重复却被消去了的方程式。不过最后还是成功地输出了大多能得出24的方程式。经过这次的课程设计，我了解到了即使再简单的一个小游戏如果要变成得以实现的程序的话还是有很大困难的。6参考文献[1]夏红霞.算法设计与分析[M].武汉:武汉大学出版社，2011。[2]闵联营,何克右.C++程序设计[M].北京:清华大学出版社，2010。[3]殷人昆.数据结构[M].北京:清华大学出版社，2005。附页——源程序#include<iostream>#include<Math.h>#include<string.h>#include<stdio.h>#include<stdlib.h>usingnamespacestd;intk=0;//全局变量K用来判定是否有解intt[5][10]={0},ta=0;//用于消去重复charopp[3]={0,0,0};//opp[3]至opp[1]用来储存第一二三个运算符charop[4]={'+','-','*','/'};voidcount(floata[],charopef[][20],intn);//a[]中存放传递的数据，opef[][20]中存放已计算的公式和其余数据，n是进行运算的数的个数voidprint(charopp[],charopef[][20]);//用于消去重复的方程式并输出方程式voidjudge(intt[],charopp[],charopef[][20]);//print函数中重复的部分提取出单独作为函数voidmain(){ cout<<"*************计算点（J.Q.K请用11.12.13代替） floatarraya[4]={0};//存储四个输入的数 charopefor[4][20]={0};//存储原数据 inti,j,d; for(i=0;i<4;i++){ boolflag=false;//作为判断输入合法性的标记 cout<<"请输入第"<<i+1<<"张牌点："; cin>>arraya[i]; do{//进行输入合法性的判断，如果为合法输入置flag为true if(arraya[i]>0&&arraya[i]<14)flag=true; for(j=i-1;j>=0;j--){ if(arraya[i]==arraya[j])flag=false; } if(flag==false){ cout<<"输入错误，请重新输入："; cin>>arraya[i]; } }while(flag==false); } cout<<"输入的牌点为："; for(i=0;i<4;i++)cout<<arraya[i]<<"";//输出已输入的四个数 cout<<"\n\n"; for(d=0;d<4;d++){ sprintf(opefor[d],"%d",(int)arraya[d]); }//将四个数储存到字符串opefor[][]中 count(arraya,opefor,4);//调用count函数 if(k==0)cout<<"该组牌点不能组成点。";//k为判断有无结果的标识，当其为时表示有结果 cout<<endl;}voidcount(floata[],charopef[][20],intn){ inti,j,m,x,y;//循环使用参数 floatb[4];//记录结果和未进行计算的数字 charopeff[4][20];//记录已计算过的方程式和其余的数字 if(n>1){ for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(i==j)continue;//数字不能重复 for(m=0;m<4;m++){//进行四则运算，符号能够重复 switch(m){ case(0): b[0]=a[i]+a[j]; break; case(1): b[0]=a[i]-a[j]; break; case(2): b[0]=a[i]*a[j]; break; case(3): if(a[j]==0)break; b[0]=a[i]/a[j]; break;//除法运算中除数不能为 } if(n==2)sprintf(opeff[0],"%s%c%s",opef[i],op[m],opef[j]);//当运算为最后一层时，方程式不需要括号 elsesprintf(opeff[0],"(%s%c%s)",opef[i],op[m],opef[j]);//不为最后一层都加上括号 opp[n-2]=op[m];//保存当前运算符 for(x=0,y=1;x<n;x++){//保存结果用的数组和保存方程式的数组分别保存各自已计算过和未计算的数据 if(x!=i&&x!=j){ b[y]=a[x]; strcpy(opeff[y],opef[x]); y++; } } count(b,opeff,n-1);//递归调用，进入下一层运算 } } } } if(n==1&&fabs(a[0]-24)<0.00001){//当数据只剩一个且结果近似为时输出各函数 if(ta==0){ cout<<"各方程式为："<<endl; ta++; } print(opp,opef);//调用输出函数 }}voidprint(charopp[],charopef[][20]){ inti=strlen(opef[0]);//取方程式的字符长度 if(opp[0]=='*'&&opef[0][0]=='('&&opef[0][i-1]==')') judge(t[0],opp,opef); elseif(opp[0]=='+'&&opef[0][0]=='('&&opef[0][i-1]==')') judge(t[1],opp,opef); elseif(opp[0]=='*'&&((opef[0][0]!='('&&opef[0][i-1]==')')||(opef[0][0]=='('&&opef[0][i-1]!=')'))) judge(t[2],opp,opef); elseif(opp[0]=='+'&&((opef[0][0]!='('&&opef[0][i-1]==')')||(opef[0][0]=='('&&opef[0][i-1]!=')'))) judge(t[3],opp,opef);//当最后一次为*或+运算时，输出已消去重复后的所有方程式 elseif(opp[2]=='+'&&opp[1]=='+'){//当第一二次运算运算符为+时，第三次每种运算只输出一次 if(opp[0]=='-'&&t[0][5]==0){ cout<<opef[0]<<"=24\n"; k=1; t[0][5]=1; } if(opp[0]=='*'&&t[0][6]==0){ cout<<opef[0]<<"=24\n"; k=1; t[0][6]=1; } if(opp[0]=='/'&&t[0][7]==0){ cout<<opef[0]<<"=24\n"; k=1; t[0][7]=1; } } elseif(opp[2]=='*'&&opp[1]=='*'){//当第一二次运算运算符为*时，最后一次每种运算只输出一次 if(opp[0]=='+'&&t[0][2]==0){ cout<<opef[0]<<"=24\n"; k=1; t[0][2]=1; } if(opp[0]=='-'&&t[0][3]==0){ cout<<opef[0]<<"=24\n"; k=1; t[0][3]=1; } if(opp[0]=='/'&&t[0][4]==0){ cout<<opef[0]<<"=24\n"; k=1; t[0][4]=1; } } else{ cout<<opef[0]<<"=24\n"; k=1; }//输出其余的方程式}voidjudge(intt[],charopp[],charopef[][20]){ if(opp[2]=='+'&&opp[1]=='+'&&t[0]==0){//当第一二次运算符都是+号时，只输出一次 cout<<opef[0]<<"=24\n"; k=1; t[0]=1; } if(opp[2]=='-'&&opp[1]=='-'&&t[1]==0){//当第一二次运算符都是-号时，只输出一次 cout<<opef[0]<<"=24\n"; k=1; t[1]=1; } if(opp[2]=='*'&&opp[1]=='*'&&t[2]==0){//当第一二次运算符都是*号时，只输出一次 cout<<opef[0]<<"=24\n"; k=1; t[2]=1; } if(opp[2]=='/'&&opp[1]=='/'&&t[3]==0){/