网站赏析案例,wordpress登录空白页,网站中文模板,广州企业信息查询系统注#xff1a; 本系列仅为个人学习笔记#xff0c;学习内容为《算法小讲堂》#xff08;视频传送门#xff09;#xff0c;通俗易懂适合编程入门小白#xff0c;需要具备python语言基础#xff0c;本人小白#xff0c;如内容有误感谢您的批评指正 汉诺塔#xff08;To… 注 本系列仅为个人学习笔记学习内容为《算法小讲堂》视频传送门通俗易懂适合编程入门小白需要具备python语言基础本人小白如内容有误感谢您的批评指正 汉诺塔Tower of Hanoi又称河内塔是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定在小圆盘上不能放大圆盘在三根柱子之间一次只能移动一个圆盘。 首先考虑A座最下面的盘子移动到C座如果能将上面的63个盘子从A座借助C座移到B座再将63个盘子从B座借助A座移到C座那任务即可完成以此类推~直到仅有一个盘子的情形则将一个盘子从一个座移动到另一个座问题也就全部得到解决。而这就是典型的递归问题可以理解为套娃代码是从最大的娃往里一层一层套到最小的那个输出是把最小到最大的一层层摆出来 由以上描述我们可以知道递归算法的一些特征为了求解规模为 N 的问题应先设法将该问题分解成一些规模较小的问题从这些较小问题的解可以方便地构造出大问题的解。同时这些规模较小的问题也可以采用同样的方法分解成规模更小的问题并能从这些规模更小的问题的解中构造出规模较小问题的解。特别地当 N1 时可直接获得问题的解。 现在我们来找出解决问题的方法定义一个递归函数hanno(N,A,B,C)该方法表示将N个盘子从A座借助B座移动到C座盘子的初始个数为N。具体步骤为
若 A 座上只有 1 个盘子此时 N1则可直接将盘子从 A 座移动到 C 座上问题得到解决。若 A 座上有 1 个以上的盘子即 N1此时需要再考虑 3 个步骤 1先将 N-1 个盘子从 A 座借助 C 座移动到 B 座上。显然这 N-1 个盘子不能作为一个整体移动而是要按照要求来移动。此时可递归调用函数 hanoi(N-1,A,C,B)。需要注意的是这里借助 C 座将 N-1 个盘子从 A 座移动到 B 座A 是源B 是目标。 2将 A 座上剩下的第 N 个盘子移动到 C 座上。 3将 B 座上的 N-1 个盘子借助 A 座移动到 C 座上。此时递归调用函数 hanoi(N-1,B,A,C)。需要注意的是这里借助于 A 座将 N-1 个盘子从 B 座移动到 C 座B 是源C 是目标。 完成了这 3 步就可以实现预期的效果在 C 座上按照正确的次序叠放好所有的盘子。
代码实现如下
def hanno(N,A,B,C):if N1:print(将盘子1从{}移到{}.format(A,C))else:hanno(N-1,A,C,B)print(将盘子{}从{}移到{}.format(N,A,C))hanno(N-1,B,A,C)if __name____main__:hanno(3,A,B,C)输出结果
将盘子1从A移到C
将盘子2从A移到B
将盘子1从C移到B
将盘子3从A移到C
将盘子1从B移到A
将盘子2从B移到C
将盘子1从A移到C注递归这里不能简单的认为A,C一直等于最开始传入的实参本篇参考汉诺塔(图文结合)超好理解可自行阅读原文
