骑士巡游实验报告

1、程序设计实践报告学号；姓名；题目来源及序号2012年25 题 ；难度等级_级一、题目说明：由教师给出25. 编写程序求解骑士巡游问题：在n行n列的棋盘上（如n=5），假设一位骑士（按象棋中“马走日”的行走法）从初始坐标位置(x1，y1)出发，要遍访（巡游）棋盘中的每一个位置一次。请编一个程序，为骑士求解巡游“路线图”（或告诉骑士，从某位置出发时，无法遍访整个棋盘 问题无解）。当n=5时，意味着要在5行5列的棋盘的25个“点”处，按骑士行走规则，依次将1至25这25个“棋子”（数码）分别摆放到棋盘上（摆满25个位置则成功，否则失败问题无解）。例如，当n=5且初始坐标位置定为(1，1) 即最左上角

2、的那个点时，如下是一种巡游“路线图”。程序执行后的输出结果为：(x1,y1)? = (1=5, 1=5) : 1 1 1 6 15 10 21 14 9 20 5 16 19 2 7 22 11 8 13 24 17 4 25 18 3 12 23二、问题分析及求解基本思路说明：给出题目的分析及初步的解题思路。要求简洁、易懂（1）“棋盘”可用二维数组B表示。（2）编制一个具有如下原型的递归函数solve，用于完成任务：从(i,j)点出发，做第k至第n*n（即n的平方）次的移动 将k直到n的平方这些数码按规则分别摆放到棋盘即数组B中，若成功则通过引用参数ok返回true，否则返回false。vo

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

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

5、经求出的上一部分，然后再继续向后求解。这样，直到回溯到第一步，并且已经将第一步的所有可能情况都尝试过之后，即可得出问题的全部解。三、问题求解的整体框架结构说明：围绕求解目标给出具体的模块。要求简洁、易懂Main()流程 inti,j,row,col,n;j=0i+i=0inYNjnYAij=truej+cout请输入起始位置的坐标:;!okNYCout从点（.return0;Solve()流程n2=0n1=0num+;solve(x1,y1,k+1,ok,n);ax1y1=true;kn*nax1y1=false;(t1=true)&(t2=true)&(ax1y1=true)m+m=8m=1

6、intm,x1,y1,n1,n2;YNx1=i+dxm;YNYNn1nNYn2nNYcoutsetw(4)bn1n2;n2+coutendl;n1+结束四、主要算法说明：要求用自然语言描述算法。要求简洁、易懂（1）首先定义setw()的头文件,setw(n) 设域宽为n个字符，并定义一个宏并赋初值，定义全局性的二维数组int b55; 保存步数，bool a55记录某一点是否已经走过，num记录方案数int dx=0,1,1,-1,-1,2,2,-2,-2; int dy=0,2,-2,2,-2,1,-1,1,-1; 提供每一步的走法，把每种走法的可能写出来，并且把数组中的数全部按“日”的走法

7、一共种可能输入到给定的棋盘。#include #include #define N 12 using namespace std; int b55; int num=-255; int dx=0,1,1,-1,-1,2,2,-2,-2; int dy=0,2,-2,2,-2,1,-1,1,-1; （2）编写solve(int i,int j,int k,bool&ok,int n)函数，定义变量参数，通过循环判断x是否在棋盘内，判断y是否在棋盘内，通过ax1y1=false;记录该点是否已经走过，并重复调用solve(x1,y1,k+1,ok,n) 递归调用该函数，将数组全部数输写到棋内，并且

8、把棋盘从而形成不同方案。void solve(int i,int j,int k,bool&ok,int n) int m,x1,y1,n1,n2; bool t1,t2; for(m=1;m=0)&(x1=0)&(y1n); if(t1=true)&(t2=true)&(ax1y1=true) ax1y1=false; bx1y1=k; if(kn*n) solve(x1,y1,k+1,ok,n); else num+; ok=true; cout方案num :endl; for(n1=0;n1n;n1+) for(n2=0;n2n;n2+) coutsetw(4)bn1n2; couten

9、dl; ax1y1=true; （）输写主函数以及menu（）函数的编写，编制主函数，让用户输入作为巡游起点的初始坐标位置(x1,y1)（该坐标可以为棋盘内的任意一坐标点，在该处摆放“棋子”（数码）1，而后进行调用“solve(x1, y1, 2, ok);”来完成所求任务。处理的初始问题为：从某点(x1,y1)出发，按所给行走规则，作24次移动，遍访棋盘中没被访问过的各点（或发现无路可走）返回输出“无法遍历”。int menu()int i,j,row,col; bool ok=false ; int n=5; for(i=0;in;i+) for(j=0;jn;j+) aij=true;

10、coutrowcol; brow-1col-1=1; /设置起始点 arow-1col-1=false; solve (row-1,col-1,2,ok,n); /调用函数计算结果 if(!ok) cout从点(row,col)出发无法遍访endl; return 0;void man () char input; cout =MENU（骑士巡游问题）=n;cout 1:Only Whole Result（只提取任意坐标情况的全部结果）n;cout 2: Else Result（提取任意坐标的结果，然后继续）n;cout 3:Continue（清屏继续）n;cout 4: NO(结束）n;co

11、ut input;cout =n;switch (input)case 1:menu();break;case 2: menu(),man();break;case 3:system(cls),man();break;case 4:cout结束endl;break;void main()man();(1)时间复杂度：时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)(2)时间复杂度本题的时间复杂度为O(8n*n-1)。空间复杂度：本题的空间复杂度为O(n*n)。五、测试说明