毕业论文论文范文课程设计实践报告法律论文英语论文教学论文医学论文农学论文艺术论文行政论文管理论文计算机安全
您现在的位置: 毕业论文 >> 课程设计 >> 正文

C++骑士巡游源码

更新时间:2011-5-11:  来源:毕业论文

C++骑士巡游源码
编写程序求解骑士巡游问题:在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

(一) 需求分析:
这一道编程题比较有难度,在骑士巡游巡游的过程中如果遇到无路可走的情况的时候要回溯,使用回溯法,然后在继续寻找出路,直到找出一条完整的路。
(二) 概要分析:
题目的目标很明确,给骑士巡游问题:在5行5列的棋盘上寻找出路。在这个过程中必然用到回溯法。
(三) 详细设计:
有前面的分析知道就是把这几个方法实现出来void TrackBoard::onePath(int i,int j,int &g,int &h,int dir)  //下一步的方向选择
void TrackBoard::solve(int i, int j, int k, bool& ok)     //看问题能否解决void TrackBoard::init(int i,int j)    //初始化棋盘还开始位置
bool TrackBoard::hasPath(int i,int j,int &g,int &h,int dir)  // 下一步的方向控制void TrackBoard::print()                   //打印出棋盘
(四) 调试分析:
在这个程序中因为用到类,这样解决问题时比较方便的调用方法
(五) 用户使用说明:
这是为测试马走日问题编制的一个函数,看看在什么样的情况下有解,这个程序的主要用处是帮使用者解决在什么样的情况下骑士巡游会有解。马走的步伐有八个方向,因此就有多解,但是不是每一个都会有出路。这里是主要测试几个位置(1,1)或者(5,5)  如何输入其他的可能没有解决方案时便会输出no!。
(六) 测试结果:
 
(七) 源程序:(见上传代码提高题17.cpp)
(八) 编程体会:
这一题是比较难的题目,考虑的问题比较多,花的时间也比较长,但是我学会了如何去把大的问题分解成小的问题,利用回溯的方法解决这样的问题。1826

[1] [2] 下一页

C++骑士巡游源码下载如图片无法显示或论文不完整,请联系qq752018766
设为首页 | 联系站长 | 友情链接 | 网站地图 |

copyright©lwfree.cn 六维论文网 严禁转载
如果本毕业论文网损害了您的利益或者侵犯了您的权利,请及时联系,我们一定会及时改正。