骑士游历课程设计报告.docx

本文格式为Word版，下载可任意编辑骑士游历课程设计报告 一、题目 给你一个8*8的棋盘,骑士的开头位置,终止位置,让你求得骑士从开头位置开头揍到终止位置需要最小的步数是多少？（留神,骑士走日字） 要求：（1）输入：输入包含多组数据，每一行都是一组开头位置和终止位置,位置由两个字符组成,一个是小写字母(a-h),一个是数字(1-8),起始位置终止位置由一个空格隔开. （2）输出：输出从起始位置到终止位置,骑士所要走过的最小的步数. （3）所设计的数据布局应尽可能节省存储空间4）程序的运行时间应尽可能少 二、问题分析 本程序需要完成如下要求：给一个8*8的棋盘，一骑士从一开头位置按日字行走到一终止位置，所需要的最小的步数是多少测试数据输入时应得志：可以输入测试多组数据，且每组数据的第一个数据表示骑士的开头位置，其次个数据表示终止位置；数据输出时应得志：输出的数据为骑士从一开头位置按日字行走到一终止位置所需要的最小的步数 实现本程序要解决如下几个问题： 1、 如何表示骑士的开头位置和终止位置 2、 怎样实现让骑士按日字行走 3、 如何计算骑士从开头位置到终止位置所走的步数 4、 如何保证所得步数为最小的步数 5、 输入多组数据时，每组数据的第一个数据表示骑士的开头位置，其次个数据表示结 束位置 6、 把最小的步数输出 解决本程序的问题的关键在于如何让骑士按日字行走，如何计算骑士从开头位置到终止位置所走的步数以及如何保证所得的步数为骑士从开头位置到终止位置所需要的最小的步数，并且可以输入多组数据测试多组最小的步数。

首先，由于棋盘只有8行8列，骑士不能跳到棋盘之外，所以，当开头位置和终止位置为a1，b2或a8，b7或g2，h1或g7，h8时，为特殊处境，不能用算法计算出来，理应单独列举出来，所需要的最小的步数为4步；另外，当不是这几种特殊处境时，从一开头位置到一终止位置可能有好几种走法，相应的所走的步数也可能不一致，应选取其中的最小的数为最小步数 三、数据布局的选择和概要设计 由于，对于一个给定的开头位置，可以选取多个位置作为终止位置，相应的，对于一个给定的终止位置，也可以选取多个位置作为开头位置，所以，数据的规律布局可以为图形布局，相应的存储布局也可以选为邻接表，用邻接表来存储骑士的开头位置和终止位置对比便当，而且可以存储多组开头位置和终止位置 首先，骑士从开头位置到终止位置行走时，有八个方向可供选择，但是又有两个方向在同一条直线上，所以可以选取四个方向，每个方向所走的次数分别为a，b，c，d，当它们为负数时表示所走的方向为其反方向另外，由于所走的步数为非负数，所以要声明一个函数，求次数的十足值结果，分别对b和a举行枚举，得出c和d，然后加起来得出步数，再判断得出的步数是否为最小的步数。

由上可以看出，理应先设四个方向所得次数为a，b，c，d，然后对b枚举，利用a+2b和2x+y模3同余，再对a举行枚举，进而得出c和d，然后再对a，b，c，d举行取十足值，结果相加得出最小步数 为了实现上述程序功能需要: 1、 声明函数求十足值int f(int a) 2、 主函数main（） INPUT样例： e2 e4 a1 b2 b2 c3 a1 h8 a1 h7 h8 a1 b1 c3 f6 f6 OUTPUT样例： To get from e2 to e4 takes 2 knight moves. To get from a1 to b2 takes 4 knight moves. To get from b2 to c3 takes 2 knight moves. To get from a1 to h8 takes 6 knight moves. To get from a1 to h7 takes 5 knight moves. To get from h8 to a1 takes 6 knight moves. To get from b1 to c3 takes 1 knight moves. To get from f6 to f6 takes 0 knight moves. 四、算法思想 根据题目，可以设终止位置和开头位置的横坐标和纵坐标之差分别为x和y，设方向向量为（1,2）,（2,1）,（2,-1）,（1,-2）的次数分别为a，b，c，d，其中a，b，c，d也可以为负数，为负数时表示其反方向向量。

于是，可以列出两个方程a+2b+2c+d=x和2a+b-c-2d=y，要求的是|a|+|b|+|c|+|d|的最小值首先把a，b看做常量，解得：c=(-4a-5b+2x+y)/3，d=(5a+4b-x-2y)/3，那么有a+2b和2x+y模3同余，现在2x+y已知，对于b举行枚举，由于-n/2> s1 >> s2){ if ((s1==\ s2==\ (s1==\ { cout << \get from \<< s1 << \to \<< s2 << \takes 4 knight moves.\<< endl; continue; } if ((s1==\ s2==\ { cout << \ moves.\ continue; } (3) 对b，a枚举，然后求出c，d的值 for (b=-4;b<=4;b++)｛ //对b枚举 m=y+2*x-2*b+30; //a模3的余数 m%=3; for (a=m-6;a<=m+6;a+=3)｛ //对a枚举 c=(2*x+y-4*a-5*b)/3; //求出c和d d=(5*a+4*b-x-2*y)/3; ｝ （4）数据的输出：输出所走的最小的步数。

六、上机调试处境记录 错误及修改：轻易展现错误的地方有：子函数和变量的定义，关键字和函数名称的书写，以及一些库函数的模范使用这些问题均可以根据编译器的警告提示，对应的将其解决另外，由于角落问题，一般处境下，设计算法时，轻易展现把这些问题疏忽而展现算法错误，所以对于这些角落问题，要单独列举出来，并且把所需要的最小的步数标示出来 修改之后的正确输出为： 七、测试用例、结果及其算法性能分析 算法性能分析：由于该算法所需要的存储空间较小，系统需要指明调配给该程序的内存也相对小一些，所以该算法的空间繁杂度较好；而且执行该算法所需要的时间对比少，所以该算法的时间性能也对比好，时间繁杂度为O(1) 八、用户使用说明 本程序运行时没有提示说明，所以输入数据时要精心一些，否那么很有可能展现错误首先，应先输入骑士的开头位置和终止位置，中间用空格隔开，例如：“a1 b2”，然后按一下enter键就可以得到所需要的步数，如“To get from a1 to b2 takes 4 knight moves.”而且本程序可以测试多组最小步数，对比便当。