相似华容道的算法.doc

程序设计综合课程设计报告程序设计基础课程设计相似华容道的算法课程设计目的和要求经过一个学期对C+的学习，根据课堂老师教的内容和平时自学的知识，学生做相应的自我练习，根据所给题目，编写出程序，在此过程中，消化所学知识，把所学知识变成自己的，并且熟练应用C+编程，在进行课程设计的同时，锻炼学生的编程能力与思维能力，培养用计算机解决实际问题的能力；要求为根据要求在三个星期之内用C+编写出不少于300行的程序。课程设计任务内容用C+编写一个类似华容道的程序，使得程序能实现任意给出9个数字08的3*3矩阵的开始状态，再给出你想要的此矩阵经过排序后的最终状态，按回车后，电脑就会显示出此矩阵从开始状态变为最终状态的每一个步骤，并且显示经过的最短路程共经过了多少个步骤，其中排序的规则是0表示空位，只有与0相临的数字才能与之交换，规则有点像古典游戏华容道的规则。如矩阵1， 0 ，2，3，4，5，6，7，8按规则排完序变为矩阵6，8，7，3，4，5，1，0，2所经过的最短路程为28次。详细设计说明（一）需求分析在编写类似华容道的程序的过程中，需要用到数组，结构体，类，goto语句，system(“cls”)语句，switch语句，还有重要的for循环语句等。（二）算法设计和0相邻的数字可以与0交换位置，一直循环到矩阵的最终状态。（三）主要流程输入08九个数字的3*3矩阵，再输入此矩阵的最终状态，电脑根据规则一步一步地交换，最后得到交换后的新矩阵，并且显示最短的路程是多少，按X系统清屏。（四）数据结构设计设计一个3*3的矩阵用来放9个数字。（五）功能函数设计order2number( ),number2order( ),memset( ),memcpy( ),Getleft( ),getdown( ),getup( ),quicktest( ),validinput( ),outputstate( ),inputstate( ),input( ),isqueue2empty( ),sizeofqueue1( ),sizeofqueue2( ),getqueue1( ),getqueue2( ),putqueue1( ),putqueue2( ),endinq1( ),endinq2( ),（六）函数调用流程输入矩阵开始状态，再输入矩阵最终状态，判断是否能变换，如果能，继续下一步，如果不能就返回，下一步电脑自动根据规则排序，一直排到矩阵的最终状态停止，最后计算出经过的最短路程是多少。（七）编码和实现使用microsoft visual c+ 6.0运行本程序。（八）调试和运行打开microsoft visual c+ 6.0运行本程序，程序运行结果如下：输入矩阵开始状态与最终状态，程序开始运算：未完，接下图：下图是上图的连续：未完，接下图：下图是上图的连续：运行结果如上面的三个图，给出矩阵的最初状态与最终状态，系统根据规则一步一步地把数字交换后的结果显示出来，最后再显示出共经过的次数。课程设计心得与体会我经过一个学期学习C+程序设计，我学习了不少基本理论知识，并且学习了编程思想，很好地锻炼了我的编程能力，这个学期学习的C+程序设计给我的C+课程设计打下了坚实的基础，在课程设计中，运用到了不少我们所学到的知识，如所学的for循环语句，switch语句等，其中我觉得for循环语句用得很广泛。通过这次C+课程设计，不仅检测了我这个学期下来的学习成果，更重要的是让我找到了自己在学习中的不少漏洞，使我在设计的课程中得到弥补，这次C+课程设计，锻炼了我的编程思想，更进一步掌握了C+这门知识。经过为期3个星期的C+课程设计，在此期间，我学到了不少东西，首先我更进一步地熟练了这个学期所学的C+知识，弥补了我在学习期间的不少漏洞。在设计期间，我翻阅了不少关于C+的不少资料，从中学到了书本外的不少新知识，如goto语句，系统清屏用system(“cls”)等新知识，这些知识，都是课本上很少提到的提到的。刚刚拿到C+课程设计题目的时候，感觉相当困难，压力觉得也相当大，可是等到我开始设计的时候，感觉其实还是很有意思的，虽然过程确实很困难，但是给我的乐趣不少，每当攻破一个难关的时候，感觉相当高兴与激动，慢慢地激发了我对C+的热情与兴趣，更深一层的实践与知识相结合的问题，这并不是我们平时只靠课本，就可以轻易解决的。所以，锻炼了我面对难题，学会用自己掌握的知识去解决具体问题的能力。通过这次C+课程设计，使我收获到了不少东西。附录1：参考文献谭浩强著，C+程序设计（第二版），北京：清华大学出版社，1999刘光著，趣味程序导学C+builder，北京：清华大学出版社，2002美Robert Lafore著，C+面向对象程序设计（第四版），北京：中国电力出版社，2004美Bjaene Stroustrup著，C+语言的设计与演化，北京：机械工业出版社，2002美Leen Ammeraal著，C+程序设计教程（第三版），北京：中国铁道出版社，2003附录2：程序清单#include #include#include #define E_SIZE 3 #define N (E_SIZE*E_SIZE) #define TOTAL_STATE 362880 using namespace std;int order2number(char orderN) int number=0,i,j; for(i=0;iN-1;i+)int t=orderi; for(j=0;ji;j+) if(orderj=0;i-) orderi=number%(N-i); number/=N-i; usedorder0=1; for(i=1;iN;i+)for(j=0;j+)if(usedj)orderi+; if(j=orderi)usedj=1; break; int GetRight(const char orderN) char norderN; int i; memcpy(norder,order,N*sizeof(char); for(i=0;iN;i+)if(orderi=0)break;if(i%E_SIZE=0)return -1;elsenorderi=norderi-1; norderi-1=0; return order2number(norder); int GetLeft(const char orderN) char norderN; int i; memcpy(norder,order,N*sizeof(char); for(i=0;iN;i+)if(orderi=0)break;if(i%E_SIZE=E_SIZE-1)return -1; elsenorderi=norderi+1; norderi+1=0; return order2number(norder); int GetDown(const char orderN) char norderN; int i; memcpy(norder,order,N*sizeof(char); for(i=0;iN;i+)if(orderi=0)break;if(iE_SIZE)return -1; elsenorderi=norderi-E_SIZE; norderi-E_SIZE=0; return order2number(norder); int GetUp(const char orderN) char norderN; int i; memcpy(norder,order,N*sizeof(char); for(i=0;i=E_SIZE*(E_SIZE-1)return -1; elsenorderi=norderi+E_SIZE; norderi+E_SIZE=0; return order2number(norder); typedef int (*MoveFun)(const char orderN); MoveFun funs4=GetLeft,GetRight,GetUp,GetDown; int quicktest(const char nInputN,const char nOutputN) /快速移动函数 char inputN; int i,o,ix,iy,ox,oy; memcpy(input,nInput,sizeof(input); for(o=0;oN;o+)if(nOutputo=0)break;for(i=0;iN;i+)if(inputi=0)break;ox=o%E_SIZE; oy=o/E_SIZE; ix=i%E_SIZE; iy=i/E_SIZE; while(ixox)inputix+iy*E_SIZE=inputix+1+iy*E_SIZE; inputix+1+iy*E_SIZE=0; ix+; while(iyox)inputix+iy*E_SIZE=inputix-1+iy*E_SIZE; inputix-1+iy*E_SIZE=0; ix-; while(iyoy) inputix+iy*E_SIZE=inputix+(iy-1)*E_SIZE; inputix+(iy-1)*E_SIZE=0; iy-; o=0; for(i=0;iN;i+)if(nOutputi!=inputi)int j; for(j=i+1;jN;j+) if(inputj=nOutputi) break; inputj=inputi; inputi=nOutputi; o+; return (o&1)=0; int ValidInput(const char inputN) char nMaskN;int i; memset(nMask,0,sizeof(nMask); for(i=0;iN;i+)if(inputi=N|nMaskinputi) return 0; nMaskinputi=1; return 1; void OutputState(const char outputN) /输出状态 int i,j; for(i=0;iE_SIZE;i+)for(j=0;jE_SIZE;j+)printf(%d ,outputi*E_SIZE+j); coutendl; void InputState(char inputN) /输入数字函数int i; for(i=0;iN;i+)scanf(%d,input+i); char bSearchedTOTAL_STATE; short nDistanceTOTAL_STATE; int nPrevTOTAL_STATE; int nQueueTOTAL_STATE; int nHead1; int nTail1; int nHead2; int nTail2; int nStart; int nEnd; char x;void Input()char nInputN; char nOutputN; cout =欢迎使用=！;coutendl;cout太原科技大学计算机科学与技术学院;coutendl;coutendl;cout计算机082001班;coutendl;coutendl;cout学号：200820010123;coutendl;coutendl;cout姓名：杨霖;coutendl;coutendl;startstate: cout请输入数字08的3*3矩阵开始状态:;coutendl; InputState(nInput);if(!ValidInput(nInput) cout无效输入!:;coutendl; goto startstate; endstate: cout请输入你想要的此矩阵的最终状态:;coutendl; InputState(nOutput); if(!ValidInput(nOutput) cout无效输入!;coutendl; goto endstate; if(!quicktest(nInput,nOutput) cout不能移动的状态!;coutendl; cout建议交换两个非0数字。;coutendl; goto endstate; nStart=order2number(nInput); nEnd=order2number(nOutput); int IsQueue1Empty()return nHead1=nTail1; int IsQueue2Empty()return nHead2=nTail2; int SizeOfQueue1()return nTail1-nHead1;int SizeOfQueue2()return nHead2-nTail2;int GetQueue1()return nQueuenHead1+; int GetQueue2() return nQueuenHead2-; int PutQueue1(int i)if(bSearchedi=1) return 0; if(bSearchedi=2) return 1; nQueuenTail1+=i; bSearchedi=1; return 2; int PutQueue2(int i)if(bSearchedi=2) return 0; if(bSearchedi=1) return 1; nQueuenTail2-=i; bSearchedi=2; return 2; void EndInQ1(int cur,int prev) int nSave; char stateN; int nShortest=nDistancecur+nDistanceprev+1; nSave=cur; while(nPrevprev!=-1)int n; n=nSave; nSave=prev; prev=nPrevprev; nPrevnSave=n; nPrevprev=nSave; nSave=prev; coutendl; while(nSave!=-1)number2order(nSave,state); OutputState(state); coutendl; nSave=nPrevnSave; coutendl;coutnShortest; void EndInQ2(int cur,int prev) int nSave; char stateN; int nShortest=nDistancecur+nDistanceprev+1; nSave=prev; while(nPrevcur!=-1)int n; n=nSave; nSave=cur; cur=nPrevcur; nPrevnSave=n; nPrevcur=nSave; nSave=cur; coutendl; while(nSave!=-1)number2order(nSave,state); OutputState(state); coutendl; nSave=nPrevnSave; cout经过的次数为：nShortest次!; coutendl;cout按x键系统清屏:;coutx;if(x=x)system(cls);int main() Input(); nHead2=nTail2=TOTAL_STATE-1; if(nStart=nEnd)cout输入是输出的相同:;coutendl;return 0; memset(nDistance,-1,sizeof(nDistance); memset(nPrev,-1,sizeof(nPrev); nDistancenStart=nDistancenEnd=0; PutQueue1(nStart); PutQueue2(nEnd); while(1)int size,i; size=SizeOfQueue1(); f