《骑士球员报告》由会员分享，可在线阅读，更多相关《骑士球员报告（16页珍藏版）》请在金锄头文库上搜索。
1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划骑士球员报告程序设计实践报告学号；姓名；题目来源及序号XX年25题；难度等级_级一、题目说明：由教师给出25.编写程序求解骑士巡游问题：在n行n列的棋盘上，假设一位骑士从初始坐标位置(x1，y1)出发，要遍访棋盘中的每一个位置一次。请编一个程序，为骑士求解巡游“路线图”。当n=5时，意味着要在5行5列的棋盘的25个“点”处，按骑士行走规则，依次将1至25这25个“棋子”分别摆放到棋盘上。例如，当n=5且初始坐标位置定为(1，1)即最左上角的那个点时，如下是一种巡游“路线图”。程序执行
2、后的输出结果为：(x1,y1)?=(1=5,1=5):11二、问题分析及求解基本思路说明：给出题目的分析及初步的解题思路。要求简洁、易懂“棋盘”可用二维数组B表示。编制一个具有如下原型的递归函数solve，用于完成任务：从(i,j)点出发，做第k至第n*n次的移动将k直到n的平方这些数码按规则分别摆放到棋盘即数组B中，若成功则通过引用参数ok返回true，否则返回false。voidsolve(inti,intj,intk,bool&ok)；编制主函数，让用户输入作为巡游起点的初始坐标位置(x1,y1)，在该处摆放“棋子”1，而后进行调用“solve(x1,y1,2,ok);”来完成所求任务。
3、欲处理的初始问题为：从某点(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。主要才用了递归算法
4、：在函数或子过程的内部，直接或者间接地调用自己的算法。其次用到了回溯算法：问题的每个解都包含N部分，先给出第一部分，再给出第二部分，直到给出第N部分，这样就得到了一个解。若尝试到某一步时发现已经无法继续，就返回到前一步，修改已经求出的上一部分，然后再继续向后求解。这样，直到回溯到第一步，并且已经将第一步的所有可能情况都尝试过之后，即可得出问题的全部解。三、问题求解的整体框架结构说明：围绕求解目标给出具体的模块。要求简洁、易懂Main()流程Solve()流程四、主要算法说明：要求用自然语言描述算法。要求简洁、易懂首先定义setw()的头文件,setw(n)设域宽为n个字符，并定义一个宏并赋初值
5、，定义全局性的二维数组intb55;保存步数，boola55记录某一点是否已经走过，num记录方案数intdx=0,1,1,-1,-1,2,2,-2,-2;intdy=0,2,-2,2,-2,1,-1,1,-1;提供每一步的走法，把每种走法的可能写出来，并且把数组中的数全部按“日”的走法一共种可能输入到给定的棋盘。#include#include#defineN12usingnamespacestd;intb55;intnum=-255;intdx=0,1,1,-1,-1,2,2,-2,-2;intdy=0,2,-2,2,-2,1,-1,1,-1;编写solve(inti,intj,intk,
6、bool&ok,intn)函数，定义变量参数，通过循环判断x是否在棋盘内，判断y是否在棋盘内，通过ax1y1=false;记录该点是否已经走过，并重复调用solve(x1,y1,k+1,ok,n)递归调用该函数，将数组全部数输写到棋内，并且把棋盘从而形成不同方案。voidsolve(inti,intj,intk,bool&ok,intn)intm,x1,y1,n1,n2;boolt1,t2;for(m=1;m=0)&(x1=0)&(y1rowcol;brow-1col-1=1;/设置起始点arow-1col-1=false;solve(row-1,col-1,2,ok,n);/调用函数计算结果
7、if(!ok)coutinput;cout难在有限的时间内找到解。然后尝试贪心、动态规划、图论等硬做的算法，但这些算法都在预料之中以失败告终。最后，看来只有必经之路数学方法才能可以解决这个问题。【确定总算法和研究对象】用数学方法解决等价转化等题目的方法还是不胜枚举的。例如有归纳法，有总体法，有解方程法，有数形结合。对于这个题目，我们应选取什么数学方法好呢？注意到，如果任意的三个向量都可以与某两个向量等价，那么便可以从n(n2)个向量中任选三个向量出来，用与它们等价的两个向量代替它们，从而变成n-1个向量。不断重复上述的过程，直到只剩下两个向量为止，这时剩下的两个向量便是一个可行解。而由问题描述
8、可以知道：对于任意三个向量都存在两个向量与它们等价。这便意味这种方法是可行的。于是，就可以确定下总算法不断化三为二，同时也产生了我们的研究对象如何把三个向量等价替换为两个向量？【分析研究对象】因为满足条件的解是无限多个的，解的范围没有多少限制，而我们仅仅需要这样一个解，所以这时确定下来的研究对象虽然看起来简洁明了，可是要解决该问题的难度依然相当大。【“约制”思想确定新任务】既然研究对象的条件、限制还是那么宽松，因而可先且放下研究对象，而尝试做些更“细”的工作把两个向量等价转化为具有某些性质的两个向量新任务。【寻找两个向量的规律】为了更加容易地找到两个向量的一般性质，可以先从一些小数据着手，试着
9、找出有用的规律。比如当两个向量分别为,时，在直角坐标系中能被这两个向量表示的点的位置如下图：由此我们可以观察很多重要的性质：1、所有的点都在且只在直线x?2k?k?Z?和直线y?k?k?Z?上；2、在Y轴上，所有的点都出现且只出现在(0,4k)?k?Z?上；3、直线x?2k?k?Z?上的点都可通过平移Y轴而得到。于是我们归纳出任意两个不在Y轴上的向量(a1,b1)和(a2,b2)能表示的点的一般性质：所有的点分布在且只在直线x?gcd(a1,a2)?k(k?Z)和直线y?gcdb1(,b2)?k(k?Z)上；在Y轴上，所有的点都出现且只出现在(0,a1b2?a2b1gcd(a1,a2)k)?k
10、?Z?上；直线x?gcd(a1,a2)?k(k?Z)上的点都可通过平移Y轴而得到。性质的证明：1、充分性(0,a1b2?a2b1gcd(a1,a2)k)?k?Z?位置上都有点的证明：对于任意的k?Z，令t1?a2gcd(a1,a2)k,t2?a1gcd(a1,a2)k，则(a1,b1)t1?(a2,b2)t2=(0,b1t1?b2t2)=(0,a1b2?a2b1gcd(a1,a2)a1b2?a2b1gcd(a1,a2)k)所以(0,证毕。k)?k?Z?位置上都有点。2、必要性在Y轴上,所有的点都只出现在(0,明：a1b2?a2b1gcd(a1,a2)k)?k?Z?上的证设在Y轴上能用这两个向量
11、表示的任意一点为(0,y)?y?Z?，则必存在两个整数t1和t2，使得由式得t1a1?t2a2?t1a1a2?t2因为?t2为整数，所以a2|t1a1?a2gcd(a1,a2)a2gcd(a1,a2)|t1a1gcd(a1,a2)因为与a1gcd(a1,a2)互质，所以a2gcd(a1,a2)|t1令t1?a2gcd(a1,a2)k?k?Z?，则可以推出t2?a1gcd(a1,a2)k,所以y?t1b1?t2b2?a1b2?a2b1gcd(a1,a2)k所以必定存在一个整数k使得y?a1b2?a2b1gcd(a1,a2)k，也就是说在Y轴上,所有的点都只出现在(0,证毕。a1b2?a2b1gc
12、d(a1,a2)k)?k?Z?上。综上所述，可以得出性质。证毕。【“约制”思想解决新任务】有了上面富有价值的性质之后，摆在眼前的问题便是，如何利用性质恰当地约束转化后的两个向量？虽然约束的方式不可胜数，但是绝大数对解题并没有什么任何作用。此时就要取其精华了。注意到在每一条有点的坚直直线上，一个显眼的性质是，上面的点都是相隔定长出现的。这催人从直觉上觉得，转化后的一个向量可以是一个坚直向量。这种感觉正确吗？正确！更重要的是，正因为这种“约制”思想，使解题的思路开始走出模糊、步入明晰。下面给出转化后其中一个向量是坚直向量的转化方法：设须要等价转化的两个向量分别为(a1,b1)和(a2,b2)。1、
13、如果a1?0或者a2?0，则可令转化后的两个向量为(a1,b1)和(a2,b2)；2、如果a1?0或者a2?0，综合性质和性质，可以大胆地约制其中一个向量为(0,a1b2?a2b1gcd(a1,a2),因为每一条直线x?gcd(a1,a2)?k(k?Z)上的点都是相隔|a1b2?a2b1gcd(a1,a2)|个单位出现的。此时，另一个向量应该是什么呢？由性质可以推测，如果能找到一个向量，只用这个向量能且只能表示每一条直线x?gcad1,a(2)?k(k?Z)上一个骑士能到达的点，那么问题就解决了。要找的这个向量的横坐标无疑可以是gcd(a1,a2)，于是顺理成章地想到用扩展的欧几里德算法快速地
14、找出两个整数p和q使得a1p?a2q?gcd(a1,a2)则向量(a1,b1)p?(a2,b2)q?(gcd(a1,a2),b1p?b2q)就是我们要找的另一个向量了。下面证明(gcd(a1,a2),b1p?b2q)和(a2,b2)。价于(a1,b1)和证明：1、对于任意的整数t1和t2，总存在两个整数T1和T2使得(a1,b1)t1?(a2,b2)t2?(gcd(a1,a2),b1p?b2q)T1?(0,的证明：对于任意的整数t1和t2，令整数T1?a1t1?a2t2gcd(a1,a2)a1b2?a2b1gcda(1,a2)T2。因为骑士通过向量(a1,b1)和(a2,b2)能够到达位置(a1,b1)t1?(a2,b2)t2?(a1t1?a2t2,b1t2?b2t2)和位置(gcd
