鱼C论坛

 找回密码
 立即注册
查看: 3090|回复: 30

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

[复制链接]
发表于 2020-6-11 08:43:05 | 显示全部楼层 |阅读模式
13鱼币
本帖最后由 天下有敌 于 2020-6-17 09:33 编辑

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


最佳答案:
汉诺塔公式:2^k-1(k为盘子数)
把k带进去就算出来了。
  1. count = input("输入盘数,计算步数:")
  2. 2**int(count)-1
复制代码

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-6-14 08:52:07 | 显示全部楼层
汉诺塔公式:2^k-1(k为盘子数)
把k带进去就嫩个算出来了。
  1. count = input("输入盘数,计算步数:")
  2. 2**int(count)-1
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-6-11 08:55:48 | 显示全部楼层
这样是迭代吗
  1. def haino(n,a,b,c):
  2.     if n==1:
  3.         print(a,'---',c)
  4.     else:
  5.         haino(n-1,a,c,b)
  6.         print(a,'---',c)
  7.         haino(n-1,b,a,c)
  8. d=int(input())
  9. haino(d,'a','b','c')
  10.    
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-6-11 09:07:59 | 显示全部楼层

这是递归
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-6-11 09:08:35 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-6-11 09:11:16 | 显示全部楼层
本帖最后由 天下有敌 于 2020-6-11 09:12 编辑


不知道能不能用迭代实现。迭代算的快。递归好慢,等了10多分钟还没有算出来。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-6-11 09:23:25 | 显示全部楼层
天下有敌 发表于 2020-6-11 09:11
不知道能不能用迭代实现。迭代算的快。递归好慢,等了10多分钟还没有算出来。

这是你递归错了,这种不可能十分钟
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-6-11 09:41:18 | 显示全部楼层
本帖最后由 majian890324 于 2020-6-11 09:55 编辑
  1. n = int(input('一共多少层:'))

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

  4. while x < n :
  5.     x += 1
  6.     j = j*2 + 1
  7.     print(j)
复制代码


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

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-6-11 10:09:29 | 显示全部楼层
汉诺塔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阶乘的结果的,而递归是,不达到最后一层,他的中途结果没有什么意义(个人强行说明)
当然,强行迭代,也不是不能实现,毕竟这个问题还是简单的。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-6-11 10:10:55 | 显示全部楼层
majian890324 发表于 2020-6-11 09:41
这样算迭代吗?楼主只说要步数,没说要移动的方法,所以我这算不算投机取巧?

你这个算的步数都是错的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-6-11 10:20:18 | 显示全部楼层
java2python 发表于 2020-6-11 10:09
汉诺塔64个,所需要步数是10的19次方级,按家用机每秒10的9次方次运算,需要10的10次方秒。100个自己想一想 ...

巴拉巴拉听不懂
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-6-11 10:37:27 | 显示全部楼层
这部分总懂吧:
拿一个为了举例而强行递归的阶乘来说明:
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)!的值已经算出来了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-6-11 11:20:54 | 显示全部楼层
递归_迭代.jpg
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-6-11 15:17:46 | 显示全部楼层
inf
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-6-11 16:28:02 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-6-11 16:38:29 | 显示全部楼层
递归实现的结构,和迭代实现的结构,是不同的说明,不懂就算了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-6-11 19:53:21 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-6-13 17:13:12 | 显示全部楼层
本帖最后由 zcn123 于 2020-6-13 17:18 编辑

100个,你疯了,汉诺塔的时间复杂度为O(2^n-1),100个以现在的计算速度估计宇宙毁灭了也算不出来,无论你是递归还是迭代
可以百度一下汉诺塔
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-6-17 09:32:52 | 显示全部楼层
汉诺塔公式:2^k-1(k为盘子数)
把k带进去就算出来了。
  1. count = input("输入盘数,计算步数:")
  2. 2**int(count)-1
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-6-17 16:01:31 | 显示全部楼层

这不是递归吗?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 15:19

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表