文档章节

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

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

没有更多内容

加载失败,请刷新页面

加载更多

TypeScript基础入门之JSX(一)

转发 TypeScript基础入门之JSX(一) 介绍 JSX是一种可嵌入的类似XML的语法。 它旨在转换为有效的JavaScript,尽管该转换的语义是特定于实现的。 JSX在React框架中越来越受欢迎,但此后也看到了...

durban
21分钟前
0
0
JavaScript使用原型判断对象类型

1. constructor属性 在JavaScript创建对象(二)——构造函数模式中,我们说过可以使用对象的constructor属性判断对象的类型:p1.constructor === Person,可能当时就有细心的读者会想,我们...

Bob2100
22分钟前
1
0
10-《深度拆解JVM》JVM是怎么实现invokedynamic的?(下)

一、问题引入 上回讲到,为了让所有的动物都能参加赛马,Java 7 引入了 invokedynamic 机制,允许调用任意类的“赛跑”方法。不过,我们并没有讲解 invokedynamic,而是深入地探讨了它所依赖...

飞鱼说编程
43分钟前
2
0
457. Circular Array Loop

Description Difficulty : Medium You are given an array of positive and negative integers. If a number n at an index is positive, then move forward n steps. Conversely, if it's n......

52iSilence7
58分钟前
1
0
MySQL SQL 常见用法

某字段重复记录 select a.fieldA from tableA a group by a.fieldA having count(a.fieldA)>1;==select * from (select a.fieldA, count(1) as faCount from tableA a group......

园领T
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部