汉诺塔,python递归实现解法步骤
博客专区 > tomicsun 的博客 > 博客详情
汉诺塔,python递归实现解法步骤
tomicsun 发表于9个月前
汉诺塔,python递归实现解法步骤
  • 发表于 9个月前
  • 阅读 15
  • 收藏 0
  • 点赞 0
  • 评论 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(天)

 

标签: 汉诺塔 递归 python
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 1
码字总数 433
×
tomicsun
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: