跳马 VC++ 程序 贪心算法

时间:2014-08-01 04:08:41
【文件属性】:

文件名称:跳马 VC++ 程序 贪心算法

文件大小:2KB

文件格式:CPP

更新时间:2014-08-01 04:08:41

VC++ 跳马

运 用 贪 心 算 法 ,vc++ 语 言 编 写 , 可 单 步 输 出 结 果 【问题描述】 跳马问题也称骑士遍历、马踏棋盘问题:在8*8方格的棋盘上,从任意指定的方格出发,为象棋中的马寻找一条走遍棋盘每一格并且只经过一次的一条路径。 考虑国际象棋棋盘上某个位置的一只马,它是否可能只走63步,正好走过除起点外的其他63个位置各一次?如果有一种这样的走法,则称所走的这条路线为一条马的周游路线。试设计一个算法找出这样一条马的周游路线。 在一个8×8的方格棋盘中,按照国际象棋中马的行走规则从棋盘上的某一方格出发,开始在棋盘上周游,如果能不重复地走遍棋盘上的每一个方格, 这样的一条周游路线在数学上被称为国际象棋盘上马的哈密尔顿链。请你设计一个程序,从键盘输入一个起始方格的坐标,由计算机自动寻找并打印 【算法描述】 本题有较多方法求解,在此仅对回溯法进行分析。 一只马在棋盘的某一点,它可以朝8个方向前进,方向向量分别是:(2,1)、(2,-1)、(1,2)、(1,-2)、(-2,1)、(-2,-1)、(-1,2)、(-1,-2)。从中任选择一个方向前进,到达新的位置。在从新的位置选择一个方向前进,继续,直到无法前进为止。无法前进可能有如下原因:下一位置超出边界、下一位置已经被访问过。当马已经无法前进时,就回退到上一位置,从新选择一个新的方向前进;如果还是无法前进,就再回退到上一位置……


网友评论

  • 写的不错蛮精炼的
  • 很有用~值得下载