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

C++骑士巡游问题

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

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
提示: 
(1)“棋盘”可用二文数组B表示。
 (2)编制一个具有如下原型的递归函数solve,用于完成任务:从(i,j)点出发,做第k至第n*n(即n的平方)次的移动 — 将k直到n的平方这些数码按规则分别摆放到棋盘即数组B中,若成功则通过引用参数ok返回true,否则返回false。
  void solve(int i, int j, int k, bool& ok);
(3)编制主函数,让用户输入作为巡游起点的初始坐标位置(x1,y1),在该处摆放“棋子”(数码)1,而后进行调用“solve(x1, y1, 2, ok);”来完成所求任务。
    欲处理的初始问题为:从某点(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(否则返回false)。
点评:原文请找腾讯752018766辣,文-论'文.网http://www.751com.cn
 (1)也可编制第二种解法的主函数:将棋盘上的n平方个点依次作为巡游起点的初始坐标位置(x1,y1),判断从每一位置出发是否有解或无解(输出“OK!”或“NO!”,但并不输出“路线图”)。
 (2)若更改程序中的n值(如改为4或6等),便可求解其他阶数的巡游“路线图”。
 (3)可改用非递归方法设计并编写solve函数,那样的话,通常要增加一个记录摆放“棋子”信息的数组,可记录下是沿着什么方向到达了当前的什么位置(在那儿摆放了“棋子”)等,而且对上述数组可按照栈(stack)的方式来使用(栈总是采用FILO即所谓的先进后出使用方式),以便在“无路可走”的情况下,回退(回溯)到上一个位置,接着按照另外的方向去寻找其他的“行走”方法。
14.2概要设计:
本程设计思路: 将整个二文数组先前部初始化。然后用递归函数solve,实现从(i,j)点出发,做第k至第n*n(即n的平方)次的移动 — 将k直到n的平方这些数码按规则分别摆放到棋盘即数组B中,若成功则通过引用参数ok返回true,否则返回false
程序流程图(如左图):
14.3   详细设计与编码:
见上传程序。
 14.4  调试分析:
      在写solve函数时,在考虑骑士的跳步时忘了考虑一中情况,致使最后的结果出不来正确的。
 程序执行的结果:
14.5   用户使用说明:
      按提示先输入是棋盘的大小,输入骑士的起始位置,然后若是要一个一个解的看就输入数字就行,若是想看全部,就直接输入非数字。

14.6  设计心得:
     写程序的时候需要非常的细心,要考虑到每一种可能的情况,一点点的小失误都是不能忽视的。应当做到一丝不苟,特别是在写程序时,一旦是写好了,因为照思文的惯性很难找出自己所犯的错误。1837

[1] [2] 下一页

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

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