扑克牌游戏2.doc

本科学生实验报告C+课程设计组长姓名 黄跃武 组长学号 0104024 专 业 软件工程 班级 软件105班 实验项目 扑克牌游戏问题 实验类别 综合性实验 指导教师 严军勇 开课学期 2011 至 2012 学年 第一 学期一、 实验设计方案实验名称：扑克牌游戏问题实验时间： 2011-11-122011-11-26实验场地： w101软件环境： VC6.0/Windows XP小组成员姓名与学号：黄强 01040261、 实验内容与目的（简单介绍实验内容，说明实验目的）实验目的：实现扑克牌游戏：对于任意的四个1到13的整数（四张扑克牌），求能算出24的表达式；运算符有()+-*/；若无解则输出相应的信息。实验内容：文件输入（input.txt）输出(output.txt)，输出全部结果；输入输出格式自定。2、 实验准备工作（阐述解决问题所涉及的算法思想，至少要画一个算法流程图来说明）算法思想：本实验采用类似于穷举法，结合堆栈来实现的。首先是穷举法的过程，采用+、-、*、/、（、）使四个数计算成24，可以将表达式分为3种情况：1. 无括号，组成的表达式中只有四个数和三个运算符，总共7个字符；2. 有一个括号，组成的表达式中有四个数、三个运算符、一个括号，总共9个字符；3. 有两个括号，组成的表达式中有四个数、三个运算符、两个括号，总共11个字符将输入的四个数进行全排列，根据四个数字中有多少个相同数字将全排列后的组数可以分4种情况：1. 四个数都不相同，全排列后的种数为4*3*2*1=24；2. 四个数中有两个相同，全排列后的种数为4*3*2*1/(2*1)=12；3. 四个数中有三个相同，全排列后的种数为4*3*2*1/(3*2*1)=4;4. 四个数中有三个相同，全排列后的种数为4*3*2*1/(4*3*2*1)=4;为避免全排列的中有相同的排列，首先将四个数24种全排列存放在二维数组中（sort244），此时若属于第2、3、4种情况时，sort244中有重复的排列，则利用循环语句将sort244中的排列转存至ZL_sort244（元素初值全为24），并用m计算二维数组ZL_sort244中的排列数，下次比较时将sort中的元素与ZL_sort进行比较，若sort中的这种排列与ZL_sort中的24种排列都不相同，则写入ZL_sort中，并成为第m+1个元素。处理没有括号的情况，此时需要进行三步运算，运算符的选取方法总共有4*4*4=64种情况，用一个二维数组char_sort643存储选取的64种运算符。那么表达式的排列有m*64种，将这m*64种情况存入二维数组x15368(1536表示m取最大值24时m*64=1536,8表示4个数、3个运算符、#，#在处理堆栈时应用)，且处理时满足条件则n+（n初始值为0）。处理一个括号的情况，可以分为（ab）cd、a(bc)d、ab(cd)、(abc)d、a(bcd)五种情况，所有的排列种数为4*4*4*5种情况，显然存在许多不必要排列，例如:(a+b)+c+d、(a*b)+c-d、a+(b*c)-d没有必要添加括号，可以当作无括号的情况处理，经过分析之后，总共有112种情况。那么表达式的排列有m*112种，将这m*112种情况存入二维数组x1268810(2688表示m取最大值24时m*122=2688,10表示4个数、3个运算符、（、）、#，#在处理堆栈时应用)。因为括号分为5种情况所以处理时也须将这五种情况一一考虑，且处理时满足条件则w+（w初始值为0），w在这5种情况中连续使用。处理两个括号时情况，此时只有(ab)(cd)这种情况时括号才有意义，也不和前面的表达式重复，总共有2*2*2=8种情况。那么表达式的排列有m*8种，将这m*8种情况存入二维数组x19212(192表示m取最大值24时m*8=192,12表示4个数、3个运算符、2个括号、#，#在处理堆栈时应用)，且处理时满足条件则v+（v初始值为0）。利用穷举法已经将所有的表达式给出，此时只需将表达式植入堆栈中进行运算即可。处理堆栈运算首先要建立两个栈类型，一个是整形用来存放数字，一个字符型用来存放运算符；然后创建两个空栈，在字符栈中首先压入字符#，以便一个表达式执行完后（表达式中最后一个字符为#和首先压入的#抵消）退出；最后进行表达式的运算，表达式的运算是出栈和入栈的操作：若读入数据为数字，则直接入操作数栈，若读入的数据是字符，则与栈中栈顶元素进行优先级比较，小于则直接入栈，等于则消去栈顶元素，大于则取出操作数栈中的栈顶元素和次栈顶元素进行运算。算法流程图：4个数全排列：i,j,k,l取0-3中不同的值将si.sj.sk.sl依次存入二维数组sortm(0.1.23)中将sortm0.sortm1.sortm2.sortm3与ZL_sort中0-24进行比较全部不相同ZL_sortn=sortm,m+，n+m=24否结束是运算符间的优先关系：表达式求值：二、实验步骤、测试与结果分析1、源程序的设计（在此附上源程序（cpp文件）清单）#include#includeusing namespace std;#define STACK_INIT_SIZE 100 /栈申请分配存储空间的大小#define STACKINCREMENT 10 /栈分配空间不足时增加存储空间int c4; /输入的4个数char s4; /+、-、*、/四种运算符int sort244; /4个数的24种全排列int ZL_sort244; /整理后4个数的全排列char char_sort643; /无括号时运算符排列char x15368; /无括号时表达式排列char x1268810; /一个括号时表达式排列char x219212; /两个括号时表达式排列int i,j,k,l; int m; /整理后4个数的全排列数int n; /无括号时表达式排列数int w; /一个括号时表达式排列数int v; /两个括号时表达式排列数/=24种全排列=void Sort(int h)int count=0; /整形变量计算种类的多少for(i=0;i4;i+)for(j=0;j4;j+)for(k=0;k4;k+)for(l=0;l4;l+)if(l!=k&l!=j&l!=i&k!=i&k!=j&i!=j) /取不同的数sortcount0=ci; sortcount1=cj; sortcount2=ck; sortcount3=cl;count+;/=24种排列中去掉重复的排列=void ZL_Sort()int count1=24;int count2=0;int type24;for(i=0;i24;i+)typei=14;for(i=0;i24;i+)for(l=0;l24;l+)if(i!=typel)for(j=i+1;j24;j+)if(sortj0=sorti0)&(sortj1=sorti1)&(sortj2=sorti2)&(sortj0=sorti0) /没有重复则写入数组中for(k=0;k4;k+) sortjk=0; count1-;typecount1=j;for(i=0;i24;i+)if(sorti0!=0)&(sorti1!=0)&(sorti2!=0)&(sorti3!=0)ZL_sortcount20=sorti0;ZL_sortcount21=sorti1;ZL_sortcount22=sorti2;ZL_sortcount23=sorti3;count2+;m=count2;/=无括号时的运算符排列=void ZF_Sort()s0=+;s1=-;s2=*;s3=/;int count9=0;for(i=0;i4;i+)for(j=0;j4;j+)for(k=0;k=S.stacksize) /如果存储空间不足，再次申请 S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char); if(!S.base) exit(0); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; /插入的元素为新的栈顶元素 return 1;/=在数字栈中插入元素=int Push_N(SqStack_N &S,int e) if(S.top-S.base=S.stacksize)S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int); if(!S.base) exit(0); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return 1;/=栈顶元素赋值给常数e=int Pop_T(SqStack_T &S,char &e) if(S.top=S.base) return 0; /栈为空e=*-S.top;return 1;int Pop_N(SqStack_N &S,int &e) if(S.top=S.base) return 0;e=*-S.top;return 1;/=取栈顶元素=char GetTop_T(SqStack_T S) char e;if(S.top=S.base) return 0; /栈为空e=*(S.top-1);return e;int GetTop_N(SqStack_N S) int e;if(S.top=S.base) return 0;e=*(S.top-1);return e;/=运算符优先级=char OP77=, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , E, , , , , , , , E, =;/=对两个数进行运算=int GetOperator(char Operator) int r; r=-1; switch(Operator) case +: r=0;break; case -: r=1;break; case *: r=2;break; case /: r=3;break; case (: r=4;break; case ): r=5;break; case #: r=6;break; return r;/=比较两个运算符的优先级=char Precede(char c1, char c2)int Operator1,Operator2; Operator1=GetOperator(c1); Operator2=GetOperator(c2); if(Operator16|Operator26) exit(0); /不是合法运算符，退出 return OPOperator1Operator2; /返回两运算符的关系/=对两个数进行运算=int Operate(int a,char theta,int b)int s;switch(theta)case +:s=a+b;break;case -:s=a-b;break;case *:s=a*b;break;case /: if(b!=0) s=a/b; else break;return s;/-/=无括号时的组合=void ZL_2sort()/Sort();/ZL_Sort();/ZF_Sort();n=0;for(i=0;im;i+)for(j=0;j64;j+)xn0=ZL_sorti0+0;xn2=ZL_sorti1+0;xn4=ZL_sorti2+0;xn6=ZL_sorti3+0;xn1=char_sortj0;xn3=char_sortj1;xn5=char_sortj2; xn7=#;n+; /*for(i=0;in;i+)for(j=0;j8;j+)coutxij ;coutendl;*/=一个括号时的组合=void ZL_1KSort()/Sort();/ZL_Sort();w=0;for(i=0;im;i+)for(j=0;j2;j+)for(k=2;k4;k+)for(l=0;l4;l+)x1w0=(;x1w1=ZL_sorti0+0;x1w2=sj;x1w3=ZL_sorti1+0;x1w4=);x1w5=sk;x1w6=ZL_sorti2+0;x1w7=sl;x1w8=ZL_sorti3+0;x1w9=#;w+;for(i=0;im;i+)for(j=1;j4;j=j+2)for(k=0;k2;k+)for(l=0;l4;l+)x1w0=ZL_sorti0+0;x1w1=sj;x1w2=(;x1w3=ZL_sorti1+0;x1w4=sk;x1w5=ZL_sorti2+0;x1w6=);x1w7=sl;x1w8=ZL_sorti3+0;x1w9=#;w+;for(i=0;im;i+)for(j=0;j3;j=j+2)for(k=0;k2;k+)for(l=2;l4;l+)x1w0=ZL_sorti0+0;x1w1=sj;x1w2=(;x1w3=ZL_sorti1+0;x1w4=sk;x1w5=ZL_sorti2+0;x1w6=);x1w7=sl;x1w8=ZL_sorti3+0;x1w9=#;w+;for(i=0;im;i+)for(j=0;j4;j+)for(k=1;k4;k+)for(l=0;l2;l+)x1w0=ZL_sorti0+0;x1w1=sj;x1w2=ZL_sorti1+0;x1w3=sk;x1w4=(;x1w5=ZL_sorti2+0;x1w6=sl;x1w7=ZL_sorti3+0;x1w8=);x1w9=#;w+;for(i=0;im;i+)for(j=0;j2;j+)for(k=0;k4;k+)for(l=2;l4;l+)x1w0=(;x1w1=ZL_sorti0+0;x1w2=sj;x1w3=ZL_sorti1+0;x1w4=sk;x1w5=ZL_sorti2+0;x1w6=);x1w7=sl;x1w8=ZL_sorti3+0;x1w9=#;w+;for(i=0;im;i+)for(j=2;j4;j+)for(k=0;k2;k+)for(l=2;l4;l+)x1w0=(;x1w1=ZL_sorti0+0;x1w2=sj;x1w3=ZL_sorti1+0;x1w4=sk;x1w5=ZL_sorti2+0;x1w6=);x1w7=sl;x1w8=ZL_sorti3+0;x1w9=#;w+;for(i=0;im;i+)for(j=1;j4;j=j+2)for(k=0;k2;k+)for(l=0;l4;l+)x1w0=ZL_sorti0+0;x1w1=sj;x1w2=(;x1w3=ZL_sorti1+0;x1w4=sk;x1w5=ZL_sorti2+0;x1w6=sl;x1w7=ZL_sorti3+0;x1w8=);x1w9=#;w+;for(i=0;im;i+)for(j=1;j4;j=j+2)for(k=2;k4;k+)for(l=0;l2;l+)x1w0=ZL_sorti0+0;x1w1=sj;x1w2=(;x1w3=ZL_sorti1+0;x1w4=sk;x1w5=ZL_sorti2+0;x1w6=sl;x1w7=ZL_sorti3+0;x1w8=);x1w9=#;w+;/=两个括号时的组合=void ZL_2KSort()/Sort();/ZL_Sort(); v=0;for(i=0;im;i+)for(j=0;j2;j+)for(k=2;k4;k+)for(l=0;l2;l+)x2v0=(;x2v1=ZL_sorti0+0;x2v2=sj;x2v3=ZL_sorti1+0;x2v4=);x2v5=sk;x2v6=(;x2v7=ZL_sorti2+0;x2v8=sl;x2v9=ZL_sorti3+0;x2v10=);x2v11=#;v+;/=判断是否为运算符=int In(char Y)if(Y=+)|(Y=-)|(Y=*)|(Y=/)|(Y=()|(Y=)|(Y=#) return 1; return 0;/=表达式求值=int EvaluateExpression(char ch)SqStack_T OPTR; SqStack_N OPND; int a,b,y;int e; char c,theta; InitStack_T(OPTR); Push_T(OPTR,#); InitStack_N(OPND);int COUNT=0; c=ch0; while(c!=#|GetTop_T(OPTR)!=#)if(!In(c) /c是数字y=c-0;Push_N(OPND,y);COUNT+;c=chCOUNT;while(!In(c)Pop_N(OPND,e);e=e*10+c-0;Push_N(OPND,e);COUNT+;c=chCOUNT;elseswitch(Precede(GetTop_T(OPTR),c) /c是字符case:Pop_T(OPTR,theta);Pop_N(OPND,b);Pop_N(OPND,a);Push_N(OPND,Operate(a,theta,b);break;return GetTop_N(OPND);int main()ofstream outfile(output.txt,ios:out);/定义文件流对象，打开output.txt文件if(!outfile) /如果打开文件失败，outfile返回0值cout文件打开失败！endl;exit(1);outfile.close();char f;ifstream infile(input.txt,ios:in);if(!infile) /如果打开文件失败，infile返回0值cout“input.txt”打开失败。是否创建“input.txt”？f;if(f=Y|f=y)ofstream output(input.txt);if(!output)cout“input.txt”文件创建失败！endl;exit(1);else cout“input.txt”创建成功，请在“input.txt”中写入数据后重启本程序。endl;output.close();system(PAUSE);return 0;elsesystem(pause);return 0;for(i=0;i4;i+)ci=0;int z;int t;int num;while(!infile.eof()for(i=0;ici; for(j=0;j4;j+)if(cj=0)cout未读到有效数据，请写入数据后再打开本程序。endl;system(PAUSE);return 0;ofstream output(output.txt,ios:app);if(!output)cout文件打开失败！endl;exit(1);outputendl;num=0;for(i=0;i4;i+)outputci ;output等于24的表达式：endl;Sort(c); ZL_Sort(); ZF_Sort(); ZL_2sort();char ch8; /cout无括号时的解：endl; for(i=0;in;i+)for(j=0;j8;j+)chj=xij;z=EvaluateExpression(ch); if(z=24)num+;outputnum.;for(k=0;k7;k+)if(!In(chk)t=chk-0;outputt;