福州大学数学与计算机科学学院
科研实训
专 业：数学与应用数学年 级：学 号：姓 名：唐昌宏指导教师：林华 2008级 030801218
目录
情景描述--------------------------------------------------------------------3 编写程序求解骑士走棋盘问题的思路--------------------------------3 设计心得总结--------------------------------------------------------------4 相关算法简介--------------------------------------------------------------4 源代码-----------------------------------------------------------------------5 时空分析--------------------------------------------------------------------6 心得体会--------------------------------------------------------------------7
课题：骑士走棋盘算法探究
一 情景描述
骑士旅游在十八世纪初倍受数学家与拼图迷得注意，骑士的走法为西洋棋的走法，骑士可以由任意位置出发，它要如何走完所有的位置？
骑士走法简介：
首先，国际象棋的棋盘如下
骑士的走法为：先横或竖1或2格,再竖或横2或1格，没有中国象棋蹩脚的限制。 如：从图中的（a，1）格跳到（b,3）或（c，2）格
二 编写程序求解骑士走棋盘问题的思路
编写程序求解骑士走棋盘问题的思路：在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 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表示；
编制一个具有如下原型的递归函数digui，用于完成任务：从起点(i,j)点出发，做第k至第n*n（即n的平方）次的移动 — 将k直到n的平方这些数码按规则分别摆放到棋盘中，函数如下：
void digui(int i, int j, int k)；
（3）编制主函数，让用户输入作为巡游起点的初始坐标位置(x1,y1)，在该处摆放“棋子”（数码）1，而后进行调用“digui(x1, y1, 1)来完成所求任务。
欲处理的初始问题为：从某点(x1,y1)出发，按所给行走规则，作24次移动，遍访棋盘中没被访问过的各点（或发现无路可走则输出找不到符合条件的走法）。 可分解化简为如下两个子问题（正是形成递归函数的基础）：
① 由点(x1,y1)出发，按所给行走规则作1次移动到达(g,h)（或发现无路可走）；
② 从(g,h)点出发，按所给行走规则，作23次移动，遍访棋盘中没被访问过的各点（或发现无路可走）。
digui函数具体实现时，若由(i,j)点出发已“无路可走”，则返回上一层继续寻找；否则，先“迈一步”到达(g,h)点，而后再进行递归调用：digui(g, h, k+1)；以实现从新点(g,h)出发，将k+1直到25这些“棋子”（数码）分别摆放到棋盘上，若成功则按格式输出结果。
四 相关算法简介
递归算法：在函数或子过程的内部，直接或间接地调用自己的算法。
回溯算法：问题的每个解都包含N个部分，先给出第一部分，再给出第二部分，……直到给出第N部分，这样就得到了一个解。若尝试到某一步时发现已经无法继续，就返回到前一步，修改已经求出的上一部分，然后再继续向后求解。这样，直到回溯到第一步，并且已经将第一步的所有可能情况都尝试过后，即可得出问题的全部解。
五 源代码
#include
#include //setw()的头文件 #define N 5 //定义一个宏并赋初值 using namespace std;
int b[N][N]; //定义全局性的二维数组保存步数 bool a[N][N]; //记录某一点是否已经走过 int num=0; //记录方案数
int dx[]={0,1,1,-1,-1,2,2,-2,-2};
int dy[]={0,2,-2,2,-2,1,-1,1,-1}; //提供每一步的走法 void solve(int i,int j,int k,bool&ok) //计算走法 {
int m,x1,y1,n1,n2; bool t1,t2;
for(m=1;m
x1=i+dx[m]; y1=j+dy[m];
t1=((x1>=0)&&(x1=0)&&(y1
a[x1][y1]=false; //记录该点已经走过 b[x1][y1]=k; if(k
solve(x1,y1,k+1,ok); } else {
num++; //方案数加一 ok=true;
cout
for(n2=0;n2
cout
cout
}
//return; }
a[x1][y1]=true; } } }
int main() {
int i,j,row,col; bool ok=false ; for(i=0;i
for(j=0;j
cout>row>>col;
b[row-1][col-1]=1; //设置起始点 a[row-1][col-1]=false;
solve (row-1,col-1,2,ok); //调用函数计算结果 if(!ok)
cout
六 时空分析
时间频度度
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才知道。但是我们不可能也没有必要对每个算法都上机测试，只需知道那个算法花费的时间多，那个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比，那个算法中语句执行次数多，它花费的时间就多。一个算法中的语句执行次数即为语句频度或时间频度。记为T(n).
时间复杂度
时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复
杂度，简称时间复杂度。
在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。 按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
本题的时间复杂度为O(8^n*n-1)
空间复杂度
类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地\"进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元。
本题的空间复杂度为：O(n^2)
七 心得体会
通过此次实践，我充分体会到学好专业基础课对解决实际问题的重要性。正是由于本人对数据结构等相关知识的生疏，导致在完成本题时常常无处下手。还有，实践与理论之间是有差距的，程序编写离不开上机，有时看上去没问题，可在上机时才发现代码存在着这样与那样的漏洞，一段代码往往要经过许多次的研读与修改，才能最终得以顺利运行。过程是艰辛的，但我收获颇多，不仅仅是技术的掌握，还有一些实践与做事的心态，也许正因为过程的枯燥艰辛，才更觉得成功的喜悦。
福州大学数学与计算机科学学院
科研实训
专 业：数学与应用数学年 级：学 号：姓 名：唐昌宏指导教师：林华 2008级 030801218
目录
情景描述--------------------------------------------------------------------3 编写程序求解骑士走棋盘问题的思路--------------------------------3 设计心得总结--------------------------------------------------------------4 相关算法简介--------------------------------------------------------------4 源代码-----------------------------------------------------------------------5 时空分析--------------------------------------------------------------------6 心得体会--------------------------------------------------------------------7
课题：骑士走棋盘算法探究
一 情景描述
骑士旅游在十八世纪初倍受数学家与拼图迷得注意，骑士的走法为西洋棋的走法，骑士可以由任意位置出发，它要如何走完所有的位置？
骑士走法简介：
首先，国际象棋的棋盘如下
骑士的走法为：先横或竖1或2格,再竖或横2或1格，没有中国象棋蹩脚的限制。 如：从图中的（a，1）格跳到（b,3）或（c，2）格
二 编写程序求解骑士走棋盘问题的思路
编写程序求解骑士走棋盘问题的思路：在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 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表示；
编制一个具有如下原型的递归函数digui，用于完成任务：从起点(i,j)点出发，做第k至第n*n（即n的平方）次的移动 — 将k直到n的平方这些数码按规则分别摆放到棋盘中，函数如下：
void digui(int i, int j, int k)；
（3）编制主函数，让用户输入作为巡游起点的初始坐标位置(x1,y1)，在该处摆放“棋子”（数码）1，而后进行调用“digui(x1, y1, 1)来完成所求任务。
欲处理的初始问题为：从某点(x1,y1)出发，按所给行走规则，作24次移动，遍访棋盘中没被访问过的各点（或发现无路可走则输出找不到符合条件的走法）。 可分解化简为如下两个子问题（正是形成递归函数的基础）：
① 由点(x1,y1)出发，按所给行走规则作1次移动到达(g,h)（或发现无路可走）；
② 从(g,h)点出发，按所给行走规则，作23次移动，遍访棋盘中没被访问过的各点（或发现无路可走）。
digui函数具体实现时，若由(i,j)点出发已“无路可走”，则返回上一层继续寻找；否则，先“迈一步”到达(g,h)点，而后再进行递归调用：digui(g, h, k+1)；以实现从新点(g,h)出发，将k+1直到25这些“棋子”（数码）分别摆放到棋盘上，若成功则按格式输出结果。
四 相关算法简介
递归算法：在函数或子过程的内部，直接或间接地调用自己的算法。
回溯算法：问题的每个解都包含N个部分，先给出第一部分，再给出第二部分，……直到给出第N部分，这样就得到了一个解。若尝试到某一步时发现已经无法继续，就返回到前一步，修改已经求出的上一部分，然后再继续向后求解。这样，直到回溯到第一步，并且已经将第一步的所有可能情况都尝试过后，即可得出问题的全部解。
五 源代码
#include
#include //setw()的头文件 #define N 5 //定义一个宏并赋初值 using namespace std;
int b[N][N]; //定义全局性的二维数组保存步数 bool a[N][N]; //记录某一点是否已经走过 int num=0; //记录方案数
int dx[]={0,1,1,-1,-1,2,2,-2,-2};
int dy[]={0,2,-2,2,-2,1,-1,1,-1}; //提供每一步的走法 void solve(int i,int j,int k,bool&ok) //计算走法 {
int m,x1,y1,n1,n2; bool t1,t2;
for(m=1;m
x1=i+dx[m]; y1=j+dy[m];
t1=((x1>=0)&&(x1=0)&&(y1
a[x1][y1]=false; //记录该点已经走过 b[x1][y1]=k; if(k
solve(x1,y1,k+1,ok); } else {
num++; //方案数加一 ok=true;
cout
for(n2=0;n2
cout
cout
}
//return; }
a[x1][y1]=true; } } }
int main() {
int i,j,row,col; bool ok=false ; for(i=0;i
for(j=0;j
cout>row>>col;
b[row-1][col-1]=1; //设置起始点 a[row-1][col-1]=false;
solve (row-1,col-1,2,ok); //调用函数计算结果 if(!ok)
cout
六 时空分析
时间频度度
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才知道。但是我们不可能也没有必要对每个算法都上机测试，只需知道那个算法花费的时间多，那个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比，那个算法中语句执行次数多，它花费的时间就多。一个算法中的语句执行次数即为语句频度或时间频度。记为T(n).
时间复杂度
时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复
杂度，简称时间复杂度。
在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。 按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
本题的时间复杂度为O(8^n*n-1)
空间复杂度
类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地\"进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元。
本题的空间复杂度为：O(n^2)
七 心得体会
通过此次实践，我充分体会到学好专业基础课对解决实际问题的重要性。正是由于本人对数据结构等相关知识的生疏，导致在完成本题时常常无处下手。还有，实践与理论之间是有差距的，程序编写离不开上机，有时看上去没问题，可在上机时才发现代码存在着这样与那样的漏洞，一段代码往往要经过许多次的研读与修改，才能最终得以顺利运行。过程是艰辛的，但我收获颇多，不仅仅是技术的掌握，还有一些实践与做事的心态，也许正因为过程的枯燥艰辛，才更觉得成功的喜悦。