目 录
1.问题分析………………………………………… 2
1.1问题描述…………………………………… 2
1.2问题分析…………………………………… 2
2.开发平台………………………………………… 3
3.程序设计………………………………………… 3
3.1用来消去重复的全局变量的定义………… 3
3.2主程序设计………………………………… 3
3.3算法设计…………………………………… 5
4.程序调试………………………………………… 7
4.1程序错误…………………………………… 7
4.2运行结果…………………………………… 8
5.自我评价和总结………………………………… 10
6.参考文献………………………………………… 10
7.附录……………………………………………… 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、15
2 开发平台
Microsoft Visual Studio 20## 专业版
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(float a[],char opef[][25],int n)函数。其参数a[]传递的是已计算后得出的结果和未计算的数字,opef[][25]传递的是已计算的公式和未计算的数字,n是a[]中有效的的数字个数。
此外函数还有print(char opp[],char opef[][25]), judge(int t[],char opp[],char opef[][25])这两个函数,print函数用来输出已消去部分重复后的所有方程式,judge函数是print函数中的重复部分,单独弄成函数是为了方程的简洁。
count函数的算法为:
count(float a[],char opef[][25],int n)
begin
1. float b[4]
2. char opeff[4][25]
3. if n=1&&|a[0]-24|<0.00001
4. then print(opp,opef)
5. else begin
6. for i ←0 to n
7. for j ←0 to n
8. begin
9. if i=j
10. then continue;
11. else for m ←0 to 4
12. begin
13. switch(m){
14. case(0):b[0]←a[i]+a[j];
15. break;
16. case(1):b[0]←a[i]-a[j];
17. break;
18. case(2):b[0]←a[i]*a[j];
19. break;
20. case(3):if a[j]= 0
21. then break;
22. b[0]←a[i]/a[j];
23. break;
24. end
25. if n=2
26. then opeff[0]←’opef[i]’+’op[m]’+’opef[j]’;
27. else opeff[0]←’(‘+’opef[i]’+’op[m]’+’opef[j]’+’)’;
28. opp[n-1]←op[m];
29. y←1
30. for x←0 to n
31. begin
32. if x!=i&&x!=j
33. b[y]←a[x];
34. strcpy(opeff[y],opef[x]);
35. y++;
36. end
37. count(b,opeff,n-1);
38. end
39. end
40. end
print函数消去重复方程式的限定条件有:
(1) 三个运算符全为*或+只输出一次;
(2) 前两次运算符全为*或+的,第三次的运算符每种只输出一次;
(3) 最后一次运算符为*或+的,前两次的运算符各种不同的组合输出一次;
(4) 其余的全部输出;
(5) 当有输出时将k改为1。
judge函数作用是对print函数中第三步的两个运算符的不同组合进行筛选。
4 程序调试
4.1 程序错误
调试过程中出现了两种错误,一种是语法错误,一种是算法错误,现摘录部分错误。
4.1.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:\visual studio 2008\projects\24点\24点.cpp(37) : error C2124: 被零除或对零求模
(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>
using namespace std;
int k=0;//全局变量K用来判定是否有解
int t[5][10]={0},ta=0;//用于消去重复
char opp[3]={0,0,0};//opp[3]至opp[1]用来储存第一二三个运算符
char op[4]={'+','-','*','/'};
void count(float a[],char opef[][20],int n);//a[]中存放传递的数据,opef[][20]中存放已计算的公式和其余数据,n是进行运算的数的个数
void print(char opp[],char opef[][20]);//用于消去重复的方程式并输出方程式
void judge(int t[],char opp[],char opef[][20]);//print函数中重复的部分提取出单独作为函数
void main(){
cout<<"*************计算点(J.Q.K请用11.12.13代替)*************"<<endl;
float arraya[4]={0};//存储四个输入的数
char opefor[4][20]={0};//存储原数据
int i,j,d;
for(i=0;i<4;i++){
bool flag=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;
}
void count(float a[],char opef[][20],int n){
int i,j,m,x,y;//循环使用参数
float b[4];//记录结果和未进行计算的数字
char opeff[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]);//当运算为最后一层时,方程式不需要括号
else sprintf(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);//调用输出函数
}
}
void print(char opp[],char opef[][20]){
int i=strlen(opef[0]);//取方程式的字符长度
if(opp[0]=='*'&&opef[0][0]=='('&&opef[0][i-1]==')')
judge(t[0],opp,opef);
else if(opp[0]=='+'&&opef[0][0]=='('&&opef[0][i-1]==')')
judge(t[1],opp,opef);
else if(opp[0]=='*'&&((opef[0][0]!='('&&opef[0][i-1]==')')||(opef[0][0]=='('&&opef[0][i-1]!=')')))
judge(t[2],opp,opef);
else if(opp[0]=='+'&&((opef[0][0]!='('&&opef[0][i-1]==')')||(opef[0][0]=='('&&opef[0][i-1]!=')')))
judge(t[3],opp,opef);//当最后一次为*或+运算时,输出已消去重复后的所有方程式
else if(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;
}
}
else if(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;
}//输出其余的方程式
}
void judge(int t[],char opp[],char opef[][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){//当第一二次运算符都是/号时,只输出一次
cout<<opef[0]<<"=24\n";
k=1;
t[3]=1;
}
if(((opp[2]=='+'&&opp[1]=='-')||(opp[2]=='-'&&opp[1]=='+'))&&t[4]==0){//当第一二次运算符为+-或-+时,只输出一次
cout<<opef[0]<<"=24\n";
k=1;
t[4]=1;
}
if(((opp[2]=='+'&&opp[1]=='*')||(opp[2]=='*'&&opp[1]=='+'))&&t[5]==0){//当第一二次运算符为+*或*+时,只输出一次
cout<<opef[0]<<"=24\n";
k=1;
t[5]=1;
}
if(((opp[2]=='+'&&opp[1]=='/')||(opp[2]=='/'&&opp[1]=='+'))&&t[6]==0){//当第一二次运算符为+/或/+时,只输出一次
cout<<opef[0]<<"=24\n";
k=1;
t[6]=1;
}
if(((opp[2]=='-'&&opp[1]=='*')||(opp[2]=='*'&&opp[1]=='-'))&&t[7]==0){//当第一二次运算符为-*或*-时,只输出一次
cout<<opef[0]<<"=24\n";
k=1;
t[7]=1;
}
if(((opp[2]=='-'&&opp[1]=='/')||(opp[2]=='/'&&opp[1]=='-'))&&t[8]==0){//当第一二次运算符为-/或/-时,只输出一次
cout<<opef[0]<<"=24\n";
k=1;
t[8]=1;
}
if(((opp[2]=='*'&&opp[1]=='/')||(opp[2]=='/'&&opp[1]=='*'))&&t[9]==0){//当第一二次运算符为*/或/*时,只输出一次
cout<<opef[0]<<"=24\n";
k=1;
t[9]=1;
}
}
课程设计说明书课程名:《数据结构课程设计》题目:一元多项式运算系统20##年1月一、课程认识数据结构课程主要是研究非数值计算的程序…
程序设计心得体会做了一个星期的程序设计终于做完了,在这次程序设计课中,真是让我获益匪浅,我突然发现写程序还挺有意思的。由于上学期的…
安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称课题名称用三元组实现稀疏矩阵的转置相加相乘专业计算机科学与技术班级学号AA姓…
课程设计总结一周的课程设计结束了,在这次的课程设计中不仅检验了我所学习的知识,也培养了我如何去把握一件事情,如何去做一件事情,又如…
西安郵電學院数据结构课程设计报告题目校园导航系统院系名称计算机学院专业名称计算机科学与技术班级学生姓名学号8位指导教师设计起止时间…
“数据结构与算法”课程学习总结报告1004012033陈孝婕10计本3“数据结构与算法”这门课程对于计算机科学与技术系的学生来说是…
程序设计心得体会做了一个星期的程序设计终于做完了,在这次程序设计课中,真是让我获益匪浅,我突然发现写程序还挺有意思的。由于上学期的…
课程设计总结一周的课程设计结束了,在这次的课程设计中不仅检验了我所学习的知识,也培养了我如何去把握一件事情,如何去做一件事情,又如…
数据结构与算法课程学习总结报告11计本一班许雪松1104013018数据结构与算法是计算机程序设计的重要理论技术基础,它不仅是计算…
《数据结构》优秀课程建设结项工作总结一、课程建设指导思想、定位和特色1.学科地位《数据结构》是计算机科学与技术专业和信息管理与信息…