骑士游历课程设计报告

一、题目给你一个8*8的棋盘,骑士的开始位置,结束位置,让你求得骑士从开始位置开始揍到结束位置需要最小的步数是多少？（注意,骑士走日字）要求：（1）输入：输入包含多组数据，每一行都是一组开始位置和结束位置,位置由两个字符组成,一个是小写字母(a-h),一个是数字(1-8),起始位置结束位置由一个空格隔开.（2）输出：输出从起始位置到结束位置,骑士所要走过的最小的步数.（3）所设计的数据结构应尽可能节省存储空间。（4）程序的运行时间应尽可能少。二、问题分析本程序需要完成如下要求：给一个8*8的棋盘，一骑士从一开始位置按日字行走到一结束位置，所需要的最小的步数是多少。测试数据输入时应满足：可以输入测试多组数据，且每组数据的第一个数据表示骑士的开始位置，第二个数据表示结束位置；数据输出时应满足：输出的数据为骑士从一开始位置按日字行走到一结束位置所需要的最小的步数。实现本程序要解决如下几个问题：如何表示骑士的开始位置和结束位置怎样实现让骑士按日字行走如何计算骑士从开始位置到结束位置所走的步数如何保证所得步数为最小的步数输入多组数据时，每组数据的第一个数据表示骑士的开始位置，第二个数据表示结束位置把最小的步数输出解决本程序的问题的关键在于如何让骑士按日字行走，如何计算骑士从开始位置到结束位置所走的步数以及如何保证所得的步数为骑士从开始位置到结束位置所需要的最小的步数，并且可以输入多组数据测试多组最小的步数。首先，由于棋盘只有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进行取绝对值，最后相加得出最小步数。为了实现上述程序功能需要:声明函数求绝对值intf(inta)主函数main（）INPUT样例：e2e4a1b2b2a1h8a1h7h8a1b1c3f6f6OUTPUT样例：Togetfrome2toe4takes2knightmoves.Togetfroma1tob2takes4knightmoves.Togetfromb2toc3takes2knightmoves.Togetfroma1toh8takes6knightmoves.Togetfroma1toh7takes5knightmoves.Togetfromh8toa1takes6knightmoves.Togetfromb1toc3takes1knightmoves.Togetfromf6tof6takes0knightmoves.四、算法思想根据题目，可以设结束位置和开始位置的横坐标和纵坐标之差分别为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，b，c，d列两个方程：a+2b+2c+d=x2a+b-c-2d=y得c=(-4a-5b+2x+y)/3和d=(5a+4b-x-2y)/3a+2b,2x+y模3同余对b，a枚举得出c，d|a|+|b|+|c|+|d|是否为最小？NY输出最小步数结束（1）由于骑士从开始位置到结束位置所走的步数是一个非负数，所以要对每个方向的次数求绝对值之后再相加，所以，需要声明一个函数，来求绝对值。intf(inta)//求绝对值{if(a<0)return0-a;returna;}（2）当骑士的当开始位置和结束位置分别为a1，b2或a8，b7或g2，h1或g7，h8，这几种特殊情况时，所需要的最小步数不能用算法计算出来，应该单独列举出来，最小的步数为4步。while(cin>>s1>>s2){if((s1=="a1"&&s2=="b2")||(s1=="b2"&&s2=="a1")||(s1=="g2"&&s2=="h1")||(s1=="h1"&&s2=="g2")){cout<<"Togetfrom"<<s1<<"to"<<s2<<"takes4knightmoves."<<endl;continue;}if((s1=="a8"&&s2=="b7")||(s1=="b7"&&s2=="a8")||(s1=="g7"&&s2=="h8")||(s1=="h8"&&s2=="g7")){cout<<"Togetfrom"<<s1<<"to"<<s2<<"takes4knightmoves."<<endl;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和dd=(5*a+4*b-x-2*y)/3;｝（4）数据的输出：输出所走的最小的步数。六、上机调试情况记录错误及修改：容易出现错误的地方有：子函数和变量的定义，关键字和函数名称的书写，以及一些库函数的规范使用。这些问题均可以根据编译器的警告提示，对应的将其解决。另外，由于角落问题，一般情况下，设计算法时，容易出现把这些问题忽略而出现算法错误，所以对于这些角落问题，要单独列举出来，并且把所需要的最小的步数标示出来。修改之后的正确输出为：七、测试用例、结果及其算法性能分析算法性能分析：由于该算法所需要的存储空间较小，系统需要指明分配给该程序的内存也相对小一些，所以该算法的空间复杂度较好；而且执行该算法所需要的时间比较少，所以该算法的时间性能也比较好，时间复杂度为O(1)。八、用户使用说明本程序运行时没有提示说明，所以输入数据时要谨慎一些，否则很有可能出现错误。首先，应先输入骑士的开始位置和结束位置，中间用空格隔开，例如：“a1b2”，然后按一下enter键就可以得到所需要的步数，如“Togetfroma1tob2takes4knightmoves.”九、参考文献[1]王昆仑，李红.数据结构与算法.北京：中国铁道出版社，2006年5月.[2]胡学钢.数据结构与算法设计指导.北京：清华大学出版社，1999.[3]耿国华.数据结构：C语言描述.西安：西安电子科技大学，2004.[4]郑莉，董渊，何江舟.C++语言程序设计.清华大学出版社，2010.[5]百度文库，百度百科。十、附录完整源程序如下：#include<iostream>#include<string>usingnamespacestd;intf(inta)//求绝对值{if(a<0)return0-a;returna;}intmain(){strings1,s2;inta,b,c,d,x,y,s,m;while(cin>>s1>>s2){if((s1=="a1"&&s2=="b2")||(s1=="b2"&&s2=="a1")||(s1=="g2"&&s2=="h1")||(s1=="h1"&&s2=="g2")){cout<<"Togetfrom"<<s1<<"to"<<s2<<"takes4knightmoves."<<endl;continue;}if((s1=="a8"&&s2=="b7")||(s1=="b7"&&s2=="a8")||(s1=="g7"&&s2=="h8")||(s1=="h8"&&s2=="g7")){cout<<"Togetfrom"<<s1<<"to"<<s2<<"takes4knightmoves."<<endl;continue;}x=s2[0]-s1[0];//横坐标差值s=9999;y=s2[1]-s1[1];//纵坐标差值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和dd=(5*a+4*b-x-2*y)/3;