Python汉诺塔程序怎么用迭代方式写出来？

天下有敌

我想知道汉诺塔100个最少要走几步。。。


最佳答案：
汉诺塔公式：2^k-1（k为盘子数）
把k带进去就算出来了。

count = input("输入盘数，计算步数：")
2**int(count)-1

天下有敌

汉诺塔公式：2^k-1（k为盘子数）
把k带进去就嫩个算出来了。

count = input("输入盘数，计算步数：")
2**int(count)-1

小甲鱼的铁粉

这样是迭代吗

def haino(n,a,b,c):
    if n==1:
        print(a,'---',c)
    else:
        haino(n-1,a,c,b)
        print(a,'---',c)
        haino(n-1,b,a,c)
d=int(input())
haino(d,'a','b','c')
    

skyddy

小甲鱼的铁粉 发表于 2020-6-11 08:55
这样是迭代吗

这是递归

小甲鱼的铁粉

skyddy 发表于 2020-6-11 09:07
这是递归

额

天下有敌

小甲鱼的铁粉 发表于 2020-6-11 09:08
额

不知道能不能用迭代实现。迭代算的快。递归好慢，等了10多分钟还没有算出来。

v.ki

天下有敌 发表于 2020-6-11 09:11
不知道能不能用迭代实现。迭代算的快。递归好慢，等了10多分钟还没有算出来。

这是你递归错了，这种不可能十分钟

majian890324

n = int(input('一共多少层：'))

x = 3 # x是初始层数
j = 7 # j 是初始步数

while x < n :
    x += 1
    j = j*2 + 1
    print(j)

这样算迭代吗？楼主只说要步数，没说要移动的方法，所以我这算不算投机取巧？

java2python

汉诺塔64个，所需要步数是10的19次方级，按家用机每秒10的9次方次运算，需要10的10次方秒。100个自己想一想需要多少时间？
这个问题递归非常简单，移动N个从A->C，就是三步：移动N-1个从A->B，然后第N个从A->C，然后N-1个从B->C，以此类推，直到问题简化成1个的移动。
这问题，实际可能不存在迭代解法。可以用自己搞这个栈，但本质上栈就是递归。
迭代可以实现的结构，不是N复杂度，化为N-1复杂度问题。
拿一个为了举例而强行递归的阶乘来说明：
N！=N*(N-1)！
因为这个根本不需要递归来实现，一个循环就解决的问题（所以说是强行递归），展开后：
N！=N*(N-1)*(N-2)...3*2*1
感觉上按照迭代法是这样的：
N！=(N-1)！*N
展开后
N！=1*2*3...*(N-2)*(N-1)*N
这不一样吗，实际不一样，迭代法，是每一步可以算出N-m阶乘的结果的，而递归是，不达到最后一层，他的中途结果没有什么意义（个人强行说明）
当然，强行迭代，也不是不能实现，毕竟这个问题还是简单的。

天下有敌

majian890324 发表于 2020-6-11 09:41
这样算迭代吗？楼主只说要步数，没说要移动的方法，所以我这算不算投机取巧？

你这个算的步数都是错的

天下有敌

java2python 发表于 2020-6-11 10:09
汉诺塔64个，所需要步数是10的19次方级，按家用机每秒10的9次方次运算，需要10的10次方秒。100个自己想一想 ...

巴拉巴拉听不懂

java2python

这部分总懂吧：
拿一个为了举例而强行递归的阶乘来说明：
N！=N*(N-1)！
因为这个根本不需要递归来实现，一个循环就解决的问题（所以说是强行递归），展开后：
N！=N*(N-1)*(N-2)...3*2*1
感觉上按照迭代法是这样的：
N！=(N-1)！*N
展开后
N！=1*2*3...*(N-2)*(N-1)*N
递归的时候N！=N*(N-1)！，执行的时候，只是刚开始，(N-1)!的值是不知道的
而迭代N！=(N-1)！*N，做到这一步，已经是最后一步了，(N-1)!的值已经算出来了

java2python

Python_Aaron

inf

天下有敌

java2python 发表于 2020-6-11 11:20

这是神马？

java2python

递归实现的结构，和迭代实现的结构，是不同的说明，不懂就算了。

天下有敌

zcn123

100个，你疯了，汉诺塔的时间复杂度为O（2^n-1）,100个以现在的计算速度估计宇宙毁灭了也算不出来，无论你是递归还是迭代
可以百度一下汉诺塔

天下有敌

汉诺塔公式：2^k-1（k为盘子数）
把k带进去就算出来了。

count = input("输入盘数，计算步数：")
2**int(count)-1

lingedu

小甲鱼的铁粉 发表于 2020-6-11 08:55
这样是迭代吗

这不是递归吗？