网站建设和维护人员职责,网站建设大宇,苏州做网站最好公司,网站流量的重要性#x1f308;个人主页: Aileen_0v0 #x1f525;系列专栏:PYTHON数据结构与算法学习系列专栏#x1f4ab;没有罗马,那就自己创造罗马~ 汉诺塔
两层汉诺塔的演示 三层汉诺塔的走法演示 我不知道有没有朋友跟我一样有一个疑问,如果我们顶端的先放到中间柱子呢?…
个人主页: Aileen_0v0 系列专栏:PYTHON数据结构与算法学习系列专栏没有罗马,那就自己创造罗马~ 汉诺塔
两层汉诺塔的演示 三层汉诺塔的走法演示 我不知道有没有朋友跟我一样有一个疑问,如果我们顶端的先放到中间柱子呢? 但是实际上汉诺塔问题解决方案都是最优解,我们不走弯路,我们的目的性非常强,我们最终目的都是移动到c,所以我们可以先让顶端的木块直接到c
解题思路:
不妨将这个问题拆解,n个汉诺塔,我们可以把最底下最大那个看成单独的一个,上面的(n - 1)个,看成一个整体.这样子最底下那个可以直接从 A 移动到 C,剩下上面的 ( n - 1 ) 个汉诺塔我们可以先从A 通过 C 移动到 B . 再从B通过 A 移动到 C.
这样子不断进行递归,问题规模就可以逐层减小.
代码:
def hanoi(n,a,b,c):#n为层数 a,b,c是杆子if n0:#将中间 n - 1 个盘子当成一个整体,通过c盘从a移动到b盘hanoi(n-1,a,c,b) # 中间柱子变目标print(Moving from %s to %s %(a,c)) # 对应一个柱子的时候hanoi(n-1,b,a,c) # 最后一个柱子变成目标hanoi(1,A,B,C) 运行结果: 青蛙跳台阶 总结一下规律:
我们可以发现
跳 n 个台阶的台阶数对应的跳法 跳 (n - 1)个台阶时候的跳法 跳 (n - 2)个台阶时候的跳法.
这有点像我们的斐波那契数列.
青蛙跳台阶的问题相当于动态规划的问题 .
动态规划:用上一步的结果,来快速计算得到下一步的结果.
递归的思路:
当只有1个台阶时只有一种跳法当有2个台阶时有两种跳法当台阶数大于2时青蛙可以选择跳一步到第n-1个台阶也可以选择跳两步到第n-2个台阶所以总的跳法数是跳到第n-1个台阶的跳法数加上跳到第n-2个台阶的跳法数。
这里是青蛙跳台阶的Python递归实现
def frog_jump(n):if n 1:return 1elif n 2:return 2else:return frog_jump(n-1) frog_jump(n-2)其中n表示台阶数函数返回青蛙跳到第n个台阶的跳法数。
需要注意的是这种递归实现虽然简单易懂但是时间复杂度为指数级别的所以不能用于大规模的数据处理。
