汉诺塔问题总结:
三个柱子,若干个圆盘,这个问题想了一天。
分析:
若是将A柱子上的N个圆盘借助B柱子移动到C柱子上,那么直观地(分析时假设圆盘数量大于2),
第一步:我们需要先将A柱子上的前N-1个圆盘移动到柱子B上;
第二步:将A柱子上的最后一个圆盘也就是第N个圆盘移动到C柱子上;
第三步:将B柱子上的N-1个圆盘移动到C柱子上
进一步分析:在第一步中将A柱子上的前N-1个圆盘移动到柱子B上如何实现?
也分为三个步骤:
第一步:我们需要先将A柱子上的前N-2个圆盘移动到柱子C上;
第二步:将A柱子上的第N-1个圆盘移动到B柱子上;
第三步:将C柱子上的N-2个圆盘移动到C柱子上
这样仔细一想的话是不是觉得“进一步分析”没有尽头了,我理解的写递归函数就是找通项,在此问题中写出第N项与第N-1项的关系即可(有的通项可能还会跟N-2项等有关系),递归函数的神奇之处在于它会逐渐递归至首项(N=1),在这个过程中,自然会经历第N-1项到第N-2项的递进,也就是说“进一步分析”的过程会由递归函数来完成。
分析前的酝酿:
百度什么是汉诺塔
找一个汉诺塔的微信小程序玩一玩
对应小游戏的移动步骤在草稿纸上写下移动的步骤并寻找规律,A->C, A->B, B->C……
横看成岭侧成峰,多番比较之后终于在我的草稿纸上出现了N-1、N-2的痕迹。
虽然本节讲的内容是递归,然而面对这个问题的时候我却没有想到递归,一方面是对汉诺塔游戏不熟悉,另一方面对递归函数本身的意义没有那么深刻。即使自己分析一通也不知道如何写这个代码,直到看到了网友@夏天后面是明天的分析中一句话。
“要相信def move(n, A**,** B**,** C**) 就像一个神奇的咒语。虽然还没定义完这个函数,但它已经有了“生命”可以实现我们的愿望了**”(来自网友@夏天后面是明天)
审题:请编写move(n, A, B, C)函数,它接收参数n**,表示3个柱子A、B、C中第1个柱子A的盘子数量,然后打印出把所有盘子从A借助B移动到C的方法**
不禁感叹:秒啊!一个神奇的咒语可以实现我们的愿望了
大声告诉自己:move(n, A, B, C)的意义是什么:
实现将A上的N个盘子借助B移动到C,函数可以打印出把N个盘子从A借助B移动到C过程
那么move(n-1, A, C, B)可以实现的功能是什么:
将A上的N个盘子借助C移动到B,函数可以打印出把N个盘子从A借助C移动到B过程
所以解决这个问题的最大的绊脚石是!理解函数要实现的功能及相关函数参数的关系,或者是递归函数没有理解透彻,所以现在根据分析把代码写出来
def move(n,a,b,c):
#首先阐述一下首项也就是N=1时的情况;
if n==1:
print(a, '-->', c)
else:
#第一步:我们需要先将A柱子上的(前)N-1个圆盘借助C移动到柱子B上;
move(n-1,a, c, b)
#第二步:将A柱子上的最后一个圆盘也就是第N个圆盘移动到C柱子上,本质上是将A柱子上的一个圆盘借助C移动到柱子B上
move(1,a, c, b)
#第三步:将B柱子上的N-1个圆盘借助A移动到C柱子上
move(n-1,b, a, c)
真谛!!!能自己悟出规律来的都是大神
第二步应该是 b a c 吧,好像你打错了
哇好强,突然就理解了
厉害啊,醍醐灌顶的感觉,还真是一个咒语,递归,用自己的咒语解决自己的问题
不过第二步应该是打错了,感觉是a,b,c,不过因该不影响结果,毕竟1都是a-->c
卡了半天了,结合你的文字和游戏,算是弄懂了一点,写出了代码! 谢谢
太强了!!!膜拜大神!!!
Sign in to make a reply
才子的麦穗
汉诺塔问题总结:
三个柱子,若干个圆盘,这个问题想了一天。
分析:
若是将A柱子上的N个圆盘借助B柱子移动到C柱子上,那么直观地(分析时假设圆盘数量大于2),
第一步:我们需要先将A柱子上的前N-1个圆盘移动到柱子B上;
第二步:将A柱子上的最后一个圆盘也就是第N个圆盘移动到C柱子上;
第三步:将B柱子上的N-1个圆盘移动到C柱子上
进一步分析:在第一步中将A柱子上的前N-1个圆盘移动到柱子B上如何实现?
也分为三个步骤:
第一步:我们需要先将A柱子上的前N-2个圆盘移动到柱子C上;
第二步:将A柱子上的第N-1个圆盘移动到B柱子上;
第三步:将C柱子上的N-2个圆盘移动到C柱子上
这样仔细一想的话是不是觉得“进一步分析”没有尽头了,我理解的写递归函数就是找通项,在此问题中写出第N项与第N-1项的关系即可(有的通项可能还会跟N-2项等有关系),递归函数的神奇之处在于它会逐渐递归至首项(N=1),在这个过程中,自然会经历第N-1项到第N-2项的递进,也就是说“进一步分析”的过程会由递归函数来完成。
分析前的酝酿:
百度什么是汉诺塔
找一个汉诺塔的微信小程序玩一玩
对应小游戏的移动步骤在草稿纸上写下移动的步骤并寻找规律,A->C, A->B, B->C……
横看成岭侧成峰,多番比较之后终于在我的草稿纸上出现了N-1、N-2的痕迹。
虽然本节讲的内容是递归,然而面对这个问题的时候我却没有想到递归,一方面是对汉诺塔游戏不熟悉,另一方面对递归函数本身的意义没有那么深刻。即使自己分析一通也不知道如何写这个代码,直到看到了网友@夏天后面是明天的分析中一句话。
“要相信def move(n, A**,** B**,** C**) 就像一个神奇的咒语。虽然还没定义完这个函数,但它已经有了“生命”可以实现我们的愿望了**”(来自网友@夏天后面是明天)
审题:请编写move(n, A, B, C)函数,它接收参数n**,表示3个柱子A、B、C中第1个柱子A的盘子数量,然后打印出把所有盘子从A借助B移动到C的方法**
不禁感叹:秒啊!一个神奇的咒语可以实现我们的愿望了
大声告诉自己:move(n, A, B, C)的意义是什么:
实现将A上的N个盘子借助B移动到C,函数可以打印出把N个盘子从A借助B移动到C过程
那么move(n-1, A, C, B)可以实现的功能是什么:
将A上的N个盘子借助C移动到B,函数可以打印出把N个盘子从A借助C移动到B过程
所以解决这个问题的最大的绊脚石是!理解函数要实现的功能及相关函数参数的关系,或者是递归函数没有理解透彻,所以现在根据分析把代码写出来
def move(n,a,b,c):
#首先阐述一下首项也就是N=1时的情况;
if n==1:
print(a, '-->', c)
else:
#第一步:我们需要先将A柱子上的(前)N-1个圆盘借助C移动到柱子B上;
move(n-1,a, c, b)
#第二步:将A柱子上的最后一个圆盘也就是第N个圆盘移动到C柱子上,本质上是将A柱子上的一个圆盘借助C移动到柱子B上
move(1,a, c, b)
#第三步:将B柱子上的N-1个圆盘借助A移动到C柱子上
move(n-1,b, a, c)