文档章节

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

tomicsun
 tomicsun
发布于 2017/08/28 13:17
字数 433
阅读 24
收藏 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...

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

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

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

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

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

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

cloudox_
2017/05/18
0
0
几道Python小程序练习的多种解法,做出来就表示Python入门了!

下面由小编开始设题解题: python斐波那契数列 关于Python编程练习题和答案,斐波那契数列应用的示例。引用百度关于斐波那契数列的介绍,大家先简单来的了解下,什么是斐波那契数列? 斐波那...

Python新世界
07/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

阿里云API网关使用教程

API 网关(API Gateway)提供高性能、高可用的 API 托管服务,帮助用户对外开放其部署在 ECS、容器服务等阿里云产品上的应用,提供完整的 API 发布、管理、维护生命周期管理。用户只需进行简...

mcy0425
25分钟前
4
0
解决远程登陆误按ctrl+s锁屏假死恢复

使用putty时,偶尔发生屏幕假死,不能输入等情况。 后来发现,只要数据ctrl+s,就会假死;输入ctrl+q就可以恢复过来。 很多刚从windows转移到linux上来工作的朋友,在用vi/vim编辑文件时,常常...

HJCui
28分钟前
0
0
@Transactional

事务管理是应用系统开发中必不可少的一部分。Spring 为事务管理提供了丰富的功能支持。Spring 事务管理分为编程式和声明式的两种方式。编程式事务指的是通过编码方式实现事务;声明式事务基于...

asdf08442a
33分钟前
2
0
widows下强制解除8080端口占用问题

使用win+R打开命令窗口 输入以下命令查看哪个任务占用了8080端口 netstat -ano |findstr "8080" 然后通过任务id强制关闭占用该端口的进程 tskill 10044 // 自己的试情况而定,这个ID是LISTE...

_Artisan
42分钟前
2
0
productFlavors简单实用

最近项目中,不同环境需要配置的参数越来越多,为了减少修改代码次数。研究了一下productFlavors的使用方式,总结如下 1. as3.0以上版本使用productFlavors时需要指定一个flavorDimensions,...

火云
44分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部