自由he阳光 自由he阳光
比较正常
关注数: 1 粉丝数: 82 发帖数: 2,166 关注贴吧数: 9
【老鼠走迷宫】和【骑士走棋盘】两道题目有何异同点? 【老鼠走迷宫】 背景:   “小老鼠走迷宫”游戏,输入一个迷宫地图,在地图内某位置放入一只老鼠,在地图内另一位置一个粮仓,通过算法实现小老鼠经过最短的路径走到粮仓处。 说明: 1.迷宫的墙足够结实老鼠不可穿墙而过; 2.检测输入坐标,如坐标不正确给出提示信息,等待重新输入; 3.遍历从入口到出口的通路,如没有通路则给出“路径无解”提示信息; 4.遍历从入口到出口的通路,如有通路,则给出最短路径。 【骑士走棋盘】 说明: 骑士旅游(Knight tour)在十八世纪初倍受数学家与拼图迷的注意,它什麼时候被提出已不可考,骑士的走法为西洋棋的走法,骑士可以由任一个位置出发,它要如何走完[所有的位置? 解法: 骑士的走法,基本上可以使用递回来解决,但是纯綷的递回在维度大时相当没有效率,一个聪明的解法由J.C.Warnsdorff在1823年提出,简单的说,先将最难的位置走完,接下来的路就宽广了,骑士所要走的下一步,「为下一步再选择时,所能走的步数最少的一步。」,使用这个方法,在不使用递回的情况下,可以有较高的机率找出走法(找不到走法的机会也是有的)。 网上的一般解法是: 【老鼠走迷宫】用递归 【骑士走棋盘】用循环 我觉得两道题目差不多,如果说是因为问题规模不同的话,什么时候用递归合适?什么时候用循环合适?
1 下一页