Python汉诺塔程序怎么用迭代方式写出来？
本帖最后由 天下有敌 于 2020-6-17 09:33 编辑我想知道汉诺塔100个最少要走几步。。。{:10_254:}
最佳答案：
汉诺塔公式：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')
小甲鱼的铁粉 发表于 2020-6-11 08:55
这样是迭代吗
这是递归 skyddy 发表于 2020-6-11 09:07
这是递归
额{:10_250:} 本帖最后由 天下有敌 于 2020-6-11 09:12 编辑
小甲鱼的铁粉 发表于 2020-6-11 09:08
额
{:10_256:}不知道能不能用迭代实现。迭代算的快。递归好慢，等了10多分钟还没有算出来。 天下有敌 发表于 2020-6-11 09:11
不知道能不能用迭代实现。迭代算的快。递归好慢，等了10多分钟还没有算出来。
这是你递归错了，这种不可能十分钟 本帖最后由 majian890324 于 2020-6-11 09:55 编辑
n = int(input('一共多少层：'))
x = 3 # x是初始层数
j = 7 # j 是初始步数
while x < n :
x += 1
j = j*2 + 1
print(j)
这样算迭代吗？楼主只说要步数，没说要移动的方法，所以我这算不算投机取巧？
汉诺塔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个自己想一想 ...
巴拉巴拉听不懂 这部分总懂吧：
拿一个为了举例而强行递归的阶乘来说明：
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)!的值已经算出来了
inf java2python 发表于 2020-6-11 11:20
这是神马？ 递归实现的结构，和迭代实现的结构，是不同的说明，不懂就算了。 {:10_266:} 本帖最后由 zcn123 于 2020-6-13 17:18 编辑
100个，你疯了，汉诺塔的时间复杂度为O（2^n-1）,100个以现在的计算速度估计宇宙毁灭了也算不出来，无论你是递归还是迭代
可以百度一下汉诺塔
汉诺塔公式：2^k-1（k为盘子数）
把k带进去就算出来了。count = input("输入盘数，计算步数：")
2**int(count)-1 小甲鱼的铁粉 发表于 2020-6-11 08:55
这样是迭代吗
这不是递归吗？
页:
[1]
2