骑士巡游问题c报告

《骑士巡游问题c报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、软件课程设计1报告姓名：学号：姓名：学号：专业：计算机科学与技术设计题目：写程序求解骑士巡游问题指导教师：2010年07月01日10中国矿业大学徐海学院课程设计综合成绩表班级计算机08-2姓名沈志伟学号22080381题目名称写程序求解骑士巡游问题成绩分项分数1、程序运行是否通过在线裁判系统（25分）①题目难度系数（15分）②通过与否系数（10分）①②2、算法分析报告（45分）①报告格式、版面是否清晰（10分）②解题思路是否清晰，算法介绍是否详细（15分）③流程图、算法时空复杂度分析详细程度（15分）④源代码的格式、注释情况（5分）①②③④3、答辩情况（30分）①算法思路讲

2、述清晰（15分）②回答问题情况（15分）①②总评成绩综合评定成绩课程设计负责人签字：年月日10目录《ConstructingRoads》解题与算法分析报告一、题目描述5二、解题思路8三、相关算法介绍8四、主要数据结构8五、流程图9六、源程序11七、时空分析1310一、题目描述编写程序求解骑士巡游问题：在n行n列的棋盘上（如n=5），假设一位骑士（按象棋中“马走日”的行走法）从初始坐标位置(x1，y1)出发，要遍访（巡游）棋盘中的每一个位置一次。请编一个程序，为骑士求解巡游“路线图”（或告诉骑士，从某位置出发时，无法遍访整个棋盘—问题无解）。输入输入n行n列的棋盘的大小（1<=

3、N<=12），建立一个n*n的数组，数组[i][j]棋盘,再输入骑士巡游的初始位置(i,j)。输出例如，当n=5且初始坐标位置定为(1，1)—即最左上角的那个点时，如下是一种巡游“路线图”。程序执行后的输出结果为：16151021149205161927221181324174251831223二、解题思路（1）“棋盘”可用二维数组B表示。（2）编制一个具有如下原型的递归函数solve，用于完成任务：从(i,j)点出发，做第k至第n*n（即n的平方）次的移动—将k直到n的平方这些数码按规则分别摆放到棋盘即数组B中，若成功则通过引用参数ok返回true，否则返回false。vo

4、idsolve(inti,intj,intk,bool&ok)；10（3）编制主函数，让用户输入作为巡游起点的初始坐标位置(x1,y1)，在该处摆放“棋子”（数码）1，而后进行调用“solve(x1,y1,2,ok);”来完成所求任务。欲处理的初始问题为：从某点(x1,y1)出发，按所给行走规则，作24次移动，遍访棋盘中没被访问过的各点（或发现无路可走）。可分解化简为如下两个子问题（正是形成递归函数的基础）：①由点(x1,y1)出发，按所给行走规则作1次移动到达(g,h)（或发现无路可走）；②从(g,h)点出发，按所给行走规则，作23次移动，遍访棋盘中没被访问过的各点（或发现

5、无路可走）。solve函数具体实现时，若由(i,j)点出发已“无路可走”，则将引用参数ok置为false而递归出口；否则，先“迈一步”到达(g,h)点，而后再进行递归调用：solve(g,h,k+1,ok)；以实现从新点(g,h)出发，将k+1直到25这些“棋子”（数码）分别摆放到棋盘上，若成功则通过引用参数ok返回true（否则返回false）。三、相关算法介绍递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法。回溯算法：问题的每个解都包含N部分，先给出第一部分，再给出第二部分，……直到给出第N部分，这样就得到了一个解。若尝试到某一步时发现已经无法继续，就返回到前

6、一步，修改已经求出的上一部分，然后再继续向后求解。这样，直到回溯到第一步，并且已经将第一步的所有可能情况都尝试过之后，即可得出问题的全部解。四、主要数据结构全局性的二维数组b[][]，a[][]一维数组dx[]，dy[]五、流程图main()流程inti,j,row,col,n;j=0i++10i=0i

7、x1][y1]=false;(t1==true)&&(t2==true)&&(a[x1][y1]==true)m++m<=8m=1intm,x1,y1,n1,n2;10YNx1=i+dx[m];YNYNn1#include//I/O流控制头文件,setw()的头文件,setw(n)设域宽为n个字符#defineN12//定义一个宏并赋