文档章节

汉诺塔,python递归实现解法步骤

tomicsun
 tomicsun
发布于 2017/08/28 13:17
字数 433
阅读 37
收藏 0
def hanoi(n,x,y,z):#函数实现n个盘子在x,y,z,移动
    
    if n==1:
        print(x, ' --> ', z)
    else:
        hanoi(n-1,x,z,y)#将n-1层个盘子从x移动到y上
        print(x, ' --> ', z)#将最底下的盘子移动到z上
        hanoi(n-1,y,x,z)#将y上的n-1个盘子移动到z上
hanoi(4,'X','Y','Z')# 调用函数输出步骤

def bushu(m): #函数实现m个盘子进行移动需要的步数
    a1 = 1
    if m==1:
        #print(1)
        return 1
    else:
        for i in range(2,m+1):
            a2 = a1*2 + 1
            a1 = a2
        #print (a2)
        return a2

    
i = 1
j = 1
while i< 60*60*24*365:  #如果每一秒移动一次,一年之内可以实现多少个盘子的汉诺塔游戏
    bushu(j)
    i = bushu(j)
    print (i,j)
    j += 1

程序运行后输出结果

#下面是4层的移动步骤,相应的改变n的值就可以

X  -->  Y
X  -->  Z
Y  -->  Z
X  -->  Y
Z  -->  X
Z  -->  Y
X  -->  Y
X  -->  Z
Y  -->  Z
Y  -->  X
Z  -->  X
Y  -->  Z
X  -->  Y
X  -->  Z
Y  -->  Z
#下面输出的内容,左边是步数,右边是层数
步数  层数
1 1
3 2
7 3
15 4
31 5
63 6
127 7
255 8
511 9
1023 10
2047 11
4095 12
8191 13
16383 14
32767 15
65535 16
131071 17
262143 18
524287 19
1048575 20
2097151 21
4194303 22
8388607 23
16777215 24
33554431 25

可以看到,当层数达到25层的时候,需要33554431步,也就是说你不眠不休,一点24小时的移动汉诺塔,一秒移动一步,需要388天,下面是计算公式:

33554431/60/60/24 =388.3614699074074(天)一年多一点

当然每增加一层都是一数量级的倍数增加的

例如说,26层就可能需要你388*2=776(天)

 

© 著作权归作者所有

共有 人打赏支持
tomicsun
粉丝 0
博文 1
码字总数 433
作品 0
庆阳
私信 提问
人人都能学会的python编程教程13:递归函数

话说美食街上有个煎包店,1块钱2个,2块钱3个,3块钱5个,5块钱8个。人们笑称之为斐波拉切煎包。 在数学上,斐波纳契数列被以递归的方法定义:F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n...

编程老司机
2018/05/10
0
0
The Tower of Hanoi(汉诺塔)问题深入研究

汉诺塔问题是一个经典的“重复问题“(recurrent problem),解法也中所周知,最少移动步骤是2^n - 1。 然而,我发现,对这个问题进行进一步的研究也是挺有意思的。 本篇博客目前阐述三个Han...

ChenQi
2012/05/05
0
0
汉诺塔算法和背后的数据结构

汉诺塔是有算法的。 很多问题都有解决办法,汉诺塔也不例外。如果汉诺塔的算法符合 Introduction to algorithms 这本书的观点:在计算机出现以前就有了算法,只不过计算机的出现带来了更多的...

刘思宁
2018/01/10
0
0
汉诺塔自动解题动画中的iOS开发技巧

引 前段时间做了一道题,要求实现汉诺塔游戏的自动解题动画: 汉诺塔游戏应该都了解规则: 1、将盘子全部移动到塔C 2、每次只能移动一个圆盘; 3、大盘不能叠在小盘上面。 要求由用户输入盘子...

cloudox_
2017/05/18
0
0
递归——汉诺塔

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. 递归 一个函数调用其自身,就是递归。 2. 汉诺塔 问题描述 有一个梵塔,塔内有三个座A、B、C,A座上有诺干个盘子,盘子大小不等,大的...

Quincuntial
2017/12/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

通俗易懂解释网络工程中的技术,如STP,HSRP等

导读 在面试时,比如被问到HSRP的主备切换时间时多久,STP几个状态的停留时间,自己知道有这些东西,但在工作中不会经常用到,就老是记不住,觉得可能还是自己基础不够牢固,知识掌握不够全面...

问题终结者
昨天
3
0
看了一下Maven的内容

了解了Maven其实是一个跨IDE的标准构建工具,能推广的原因估计是借了仓库的便利。 另一个作用是可以通过Maven的功能在社区版的IDEA去创建Web项目,下次实践看看

max佩恩
昨天
1
0
day27:expect批量杀进程|

1、linux下当前目录有一个文件ip-pwd.ini,内容如下: [root@localhost_002 shell100]# cat ip-pwd.ini 10.111.11.1,root,xyxyxy10.111.11.2,root,xzxzxz10.111.11.3,root,12345610.......

芬野de博客
昨天
3
0
分布式之数据库和缓存双写一致性方案解析(二)

引言 该文是对《分布式之数据库和缓存双写一致性方案解析》,一文的补充。博主在该文中,提到了这么一句话 应该没人问我,为什么没有先更新缓存,再更新数据库这种策略。 博主当时觉得,这种...

hensemlee
昨天
5
0
druid安装与案例

druid 可以运行在单机环境下,也可以运行在集群环境下。简单起见,我们先从单机环境着手学习。 环境要求 java7 或者更高版本 linux, macOS或者其他unix系统(不支持windows系统) 8G内存 2核C...

hblt-j
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部