专业方向设计报告

1专业方向设计报告课程名称：通信工程专业方向设计设计名称：求迷宫中从入口到出口的路径姓名：恒迹学号:班级：指导教师：起止日期：2方向设计任务书学生班级：学生姓名：学号：设计名称：求迷宫中从入口到出口的路径起止日期：指导教师：设计要求：假设如图所示的迷宫，试编写算法求解从入口到出口的路径。编程语言：C语言。拓展要求：可手动输入一个矩阵来表示迷宫，字符0表示通路，字符1表示障碍物，不能通过。方向设计学生日志时间设计内容2014/12/25安装VC++软件2014/12/29查阅相关资料2014/12/30初步完成代码编写2015/1/4完善程序2015/1/6完成报告填写3课程设计评语表指导教师评语：成绩：指导教师：年月日4求迷宫中从入口到出口的路径一、摘要用C语言编程实现从迷宫入口到出口的路径，通常采用堆栈或队列的形式来记录所走过的路径，而这里采用的是与地图同等大小的二维数组来记录路径。从迷宫入口开始，采用向右、向下、向左、向上的先后优先遍历顺序逐个遍历地图，途中经过的路径标记为*，如果遍历途中遇到死角，则返回上一步继续遍历直到迷宫出口，那么从迷宫入口到出口的路径就是这个与地图同等大小的二维数组中*所表示的路径。二、设计目的和意义通过这个题目，不仅可以锻炼和提高学生的代码能力，还可以提高学生的逻辑思维能力。随着无人机器人的发展，可以把这个算法思路加入到机器人里面，对于一个陌生的环境或者一些特殊环境可以先让机器人探测一下路况。总之，这个题目具有很好的理论和现实意义。三、设计原理这个题目实际上是一个寻路题，只需要从入口开始逐个遍历地图，如果可以从入口遍历到出口则表示有通路，如果不能从入口遍历到出口，则表示没有通路。首先应该完成的是题目中所要求的迷宫从入口到出口的路径，然后在次基础之上实现手动输入矩阵并实现从入口到出口的路径。最后所有功能都实现之后，可以考虑一下代码的优化。这个题目总的来说不是很难，关键在于从迷宫入口到出口的遍历过程。由于题目没有任何比较苛刻的要求，这里采取了简单粗暴的方法。这里按照右、下、左、上的优先顺序先后检测，如果向右为通路，则向右移一格，然后继续检测四周的通路情况；如果向右为障碍物，则向下检测是否为通路，若向下为通路，则向下移一格，然后继续检测四周的通路情况；如果向下为障碍物，则向左检测是否为通路，如向左为通路，则向左移一格，然后继续检测四周的通路情况；如果向左为障碍物，则向上检测是否为通路，如向上为通路，则向上移一格，然后继续检测四周的通路情况。如果四周都是障碍物，没有通路，则向后退一步，重复上述检测，直到到达迷宫出口为止。如果迷宫没有从入口到出口的路径，最后会回到起始点，则输出提示该迷宫没有从入口到出口的路径。四、详细设计步骤1、在电脑上安装VC++6.0软件。2、打开软件并建立一个空白工程。3、写出整个工程的框架程序。Function:Find_RouteDescription:寻找从迷宫入口到出口的路径。遍历方式采取右、下、左、上的优先顺序。voidFind_Path(void){}Function:ResultDescription:输出结果。5voidResult(void){}Function:mainDescription:主函数。intmain(){}4、实现题目中的迷宫从入口到出口的路径。Function:ExampleDescription:用特定地图检验是否正确。voidExample(void){｝5、实现手动输入迷宫并完成迷宫从入口到出口的路径。Function:In_Put_MazeDescription:先输入两个数字m、n（m、n均大于3且小于10），表示迷宫的大小为m行n列；然后输入一个m*n的矩阵，要求输入值为0或1，1表示此处有障碍，不能通过；0表示此处为通路。voidIn_Put(void){}6、优化程序。总程序见附录。五、设计结果及分析如图1所示，为示例迷宫从入口到出口的路径。图1示例迷宫从入口到出口的路径6如图2所示，为手动输入一个4*4矩阵迷宫，实现了从迷宫入口到出口路径的遍历。图2手动输入矩阵迷宫并实现从迷宫入口到出口路径的遍历如图3所示，为手动输入的一个没有通路的3*3的矩阵迷宫，输出提示为“Thereisnowaytoout!!!”。图3手动输入一个没有通路的矩阵迷宫7六、总结这个题目总的来说不是很难，关键在于从迷宫入口到出口的遍历过程。由于题目没有任何比较苛刻的要求，这里采取了简单粗暴的方法。虽然完成了题目的要求，但从迷宫入口到出口的路径并不是最优路径，要想得到最优路径还有很多地方需要优化，最直接的暴力法是肯定行不通的，至于需要用什么算法，还需要更深入的学习。七、体会通过这个题目的练习，我深刻的体会到理论联系实际的重要性。在真正动手写程序之前，我以为这个题很简单，可以一口气直接写出来，结果在写的过程中碰到了很多问题，不得不多次停下来认真思考，一边想着怎么写，一边想着怎么优化。最后经过不懈努力总算是完成了题目的要求。八、参考文献[1]谭浩强著.C程序设计（第四版）.北京：清华大学出版社，2010[2]刘汝佳著.算法竞赛入门经典.北京：清华大学出版社，20098九、附录/*****************************************************************Filename:寻找迷宫出口Description:用一个矩阵来表示迷宫，矩阵值为1表示此处有障碍，不能通过；矩阵值为0表示此处为通路。若迷宫没有出路则输出“Thereisnowaytoout!!!”否则输出整个迷宫以及从迷宫入口到出口的通路。Date:2014/12/30Other:无*****************************************************************/#includestdio.h#includestring.h#includemath.h/*m、n表示迷宫大小；trance[100]记录遍历信息；Flag标记是使用示例地图还是手动输入地图。Maze[10][10]用于存储迷宫信息；Ans[10][10]用于存储结果信息；*/intm,n,Flag,result,trance[100];charMaze[11][11],Ans[11][11];/*****************************************************************Function:In_Put_MazeDescription:先输入两个数字m、n（m、n均大于3且小于10），表示迷宫的大小为m行n列；然后输入一个m*n的矩阵，要求输入值为0或1，1表示此处有障碍，不能通过；0表示此处为通路。*****************************************************************/voidIn_Put(void){inti,j,flag;flag=1;if(Flag){printf(\n请输入两个数m、n表示迷宫的大小：);while(flag){scanf(%d%d,&m,&n);if(m3||m10||n3||n10){printf(\n输入错误！请重新输入：);}else{flag=0;}}printf(\n请输入一个%d*%d大小的迷宫：\n\n,m,n);for(i=0;im;i++){printf(请输入%d第行，中间用空格隔开：,i+1);9for(j=0;jn;j++){scanf(%c,&Maze[i][j]);Ans[i][j]=Maze[i][j];}}}/*把最右边一列和最后一行赋值为1，表示边界不能通过。*/for(i=0;im;i++){Maze[i][n]=Ans[i][n]='1';}for(i=0;in;i++){Maze[m][i]=Ans[m][i]='1';}for(i=0;i100;i++){trance[i]=0;}}/*****************************************************************Function:Find_RouteDescription:寻找从迷宫入口到出口的路径。遍历方式采取右、下、左、上的优先顺序。*****************************************************************/voidFind_Path(void){inti,j,k,flag;i=j=k=0;flag=3;while(flag){/*找到迷宫出路，退出遍历*/if(i==m-1&&j==n-1){result=1;break;}/*如果在遍历过程中，三次经过起始位置，则证明此迷宫没有出路。*/elseif(i==0&&j==0){flag--;if(flag==0){result=0;}10}/*向右遍历为通路*/if(Maze[i][j+1]=='0'&&Ans[i][j+1]!='*'){trance[k]=i*10+j;k++;Ans[i][j]='*';j++;continue;}/*向右遍历为障碍，向下遍历*/elseif(Maze[i+1][j]=='0'&&Ans[i+1][j]!='*'){trance[k]=i*10+j;k++;Ans[i][j]='*';i++;continue;}/*向右、下遍历为障碍，向左遍历*/elseif(Maze[i][j-1]=='0'&&Ans[i][j-1]!='*'&&j0){trance[k]=i*10+j;k++;Ans[i][j]='*';j--;continue;}/*向右、下、左遍历为障碍，向上遍历*/elseif(Maze[i-1][j]=='0'&&Ans[i-1][j]!='*'&&i0){trance[k]=i*10+j;k++;Ans[i][j]='*';i--;continue;}/*走到死角往回退一步。*/else{Maze[i][j]='1';k--;i=trance[k]/10;j=trance[k]%10;Ans[i][j]='0';}11}}/*****************************************************************Function:ResultDescription:输出结果。*****************************************************************/voidResult(void){inti,j;if(result){Ans[m-1][n-1]='*';printf(\n正确路线为：\n);for(i=0;im;i++){for(j=0;jn;j++){printf(%c,Ans[i][j]);}printf(\n);}printf(\nGoodjob\n);}else{printf(\nThereisnowaytoout!!!\n);}}/*****************************************************************Function:ExampleDescription:用特定地图检验是否正确。*****************************************************************/voidExample(void){inti,j;m=n=8;charExa[][8]={{'0','0','1','0','0','0','1','0'},{'0','1','1','0','0','0','1','0'},{'0','0','0','0','1','1','0','0'},{'0','1','1','1','0','0','0','0'},{'0','0','0','1','0