骑士球员报告.docVIP

骑士球员报告 骑士巡游实验报告 《程序设计实践》报告 学号；姓名；题目来源及序号2012年25 题 ；难度等级_Ｂ级 一、题目 说明：由教师给出 25. 编写程序求解骑士巡游问题：在n行n列的棋盘上（如n=5），假设一位骑士（按象棋中“马走日”的行走法）从初始坐标位置(x1，y1)出发，要遍访（巡游）棋盘中的每一个位置一次。请编一个程序，为骑士求解巡游“路线图”（或告诉骑士，从某位置出发时，无法遍访整个棋盘 — 问题无解）。 当n=5时，意味着要在5行5列的棋盘的25个”点”处，按骑士行走规则，依次将1至25这25个“棋子”（数码）分别摆放到棋盘上（摆满25个位置则成功，否则失败问题无解）。 例如，当n=5且初始坐标位置定为(1，1) — 即最左上角的那个点时，如下是一种巡游“路线图”。程序执行后的输出结果为： (x1,y1)? = (1=5, 1=5) : 1 1 16 15 10 21 149 205 16 1927 22 11 8 13 24 174 25 183 12 23 二、问题分析及求解基本思路 说明：给出题目的分析及初步的解题思路。要求简洁、易懂 （1）“棋盘”可用二维数组B表示。 （2）编制一个具有如下原型的递归函数solve，用于完成任务：从(i,j)点出发，做第k至第n*n（即n的平方）次的移动 — 将k直到n的平方这些数码按规则分别摆放到棋盘即数组B中，若成功则通过引用参数ok返回true，否则返回false。 void solve(int i, int j, int k, boolamp; ok)； （3）编制主函数，让用户输入作为巡游起点的初始坐标位置(x1,y1)，在该处摆放“棋子”（数码）1，而后进行调用“solve(x1, y1, 2, ok);”来完成所求任务。 欲处理的初始问题为：从某点(x1,y1)出发，按所给行走规则，作24次移动，遍访棋盘中没被访问过的各点（或发现无路可走）。 可分解化简为如下两个子问题（正是形成递归函数的基础）： ① 由点(x1,y1)出发，按所给行走规则作1次移动到达(g,h)（或发现无路可走）； ② 从(g,h)点出发，按所给行走规则，作23次移动，遍访棋盘中没被访问过的各点（或发现无路可走）。 solve函数具体实现时，若由(i,j)点出发已“无路可走”，则将引用参数ok置为false而递归出口；否则，先“迈一步”到达(g,h)点，而后再进行递归调用：solve(g, h, k+1, ok)；以实现从新点(g,h)出发，将k+1直到25这些“棋子”（数码）分别摆放到棋盘上，若成功则通过引用参数ok返回true（否则返回false）。 主要才用了递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法。其次用到了回溯算法：问题的每个解都包含N部分，先给出第一部分，再给出第二部分，……直到给出第N部分，这样就得到了一个解。若尝试到某一步时发现已经无法继续，就返回到前一步，修改已经求出的上一部分，然后再继续向后求解。这样，直到回溯到第一步，并且已经将第一步的所有可能情况都尝试过之后，即可得出问题的全部解。 三、问题求解的整体框架结构 说明：围绕求解目标给出具体的模块。要求简洁、易懂 Main()流程 Solve()流程 四、主要算法 说明：要求用自然语言描述算法。要求简洁、易懂 （1）首先定义setw()的头文件,setw(n) 设域宽为n个字符，并定义一个宏并赋初值，定义全局性的二维数组int b[5][5]; 保存步数，bool a[5][5]记录某一点是否已经走过，num记录方案数int dx[]={0,1,1,-1,-1,2,2,-2,-2}; int dy[]={0,2,-2,2,-2,1,-1,1,-1}; 提供每一步的走法，把每种走法的可能写出来，并且把数组中的数全部按“日”的走法一共８种可能输入到给定的棋盘。 #include iostream #include iomanip #define N 12 using namespace std; int b[5][5]; 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,boolamp;ok,int n)函数，定义变量参数，通过循环判断x是否在棋盘内，判断y是否在棋盘内，通过a[x1][y1]=false;记录该点是否已经走过，并重复调用solve(x1,y1,k+1,ok,n) 递归调用该函数，将数组全部数输写到棋内，并且把棋盘从而形成不同方案。 void solve(int i,int j,i