词语大全 > 骑士旅游

骑士旅游

骑士旅游(Knight tour)在十八世纪初倍受数学家与拼图迷的注意,它什么时候被提出已不可考,骑士的走法为西洋棋的走法,骑士可以由任一个位置出发,它要如何走完所有的位置?

骑士的走法,基本上可以使用递归来解决,但是纯的递归在维度大时相当没有效率,一个聪明的解法由J.C. Warnsdorff在1823年提出,简单的说,先将最难的位置走完,接下来的路就宽广了,骑士所要走的下一步,「为下一步再选择时,所能走的步数最少的一步。」,使用这个方法,在不使用递归的情况下,可以有较高的机率找出走法(找不到走法的机会也是有的)。

在一个n m 格子的棋盘上,有一只国际象棋的骑士在棋盘的左下角,骑士只能根据象棋的规则进行移动,要么横向跳动一格纵向跳动两格,要么纵向跳动一格横向跳动两格。 例如, n=4,m=3 时,若骑士在格子(2;1) ,则骑士只能移入下面格子:(1;3),(3;3) 或 (4;2);对于给定正整数n,m,I,j值 (m,n<=50,I<=n,j<=m) ,你要测算出从初始位置(1;1) 到格子(i;j)最少需要多少次移动。如果不可能到达目标位置,则输出"NEVAR"。

骑士旅游的伪码:

FOR(m = 2; m <= 总步数; m++)

[

测试下一步可以走的八个方向,记录可停留的格数count。

IF(count == 0)

[

游历失败

]

ELSE IF(count == 1)

[

下一步只有一个可能

]

ELSE

[

找出下一步的出路最少的格子

如果出路值相同,则选第一个遇到的出路。

]

走最少出路的格子,记录骑士的新位置。

]

相关解释:

词语大全 8944.net

copyright ©right 2010-2021。
词语大全内容来自网络,如有侵犯请联系客服。zhit325@126.com