chapter_divide_and_conquer/hanota_problem/ #616
Replies: 17 comments 26 replies
-
这种递归代码看着别人写的简单,自己看的头疼也写不出来 |
Beta Was this translation helpful? Give feedback.
-
""" |
Beta Was this translation helpful? Give feedback.
-
上面的代码半天都理解不了,后面去油管搜到了这个视频,配合着看,可以把思路理清晰 |
Beta Was this translation helpful? Give feedback.
-
大致理解就最小化时候是不是可以理解成这样 // 子问题 f(i-1) :将 src 顶部 i-1 个圆盘借助 tar 移到 buf 就相当于i=2时 这样就相当于完成了2个的移动,别的只是在递归实现 |
Beta Was this translation helpful? Give feedback.
-
感觉递归的核心思路就是,虽然代码没有实现,但是我相信我自己写的代码,写完他就成立了。 |
Beta Was this translation helpful? Give feedback.
-
不是只能从顶部一个一个拿吗?为啥直接遍历到地盘直接拿出底层的盘子呢? |
Beta Was this translation helpful? Give feedback.
-
请问: |
Beta Was this translation helpful? Give feedback.
-
对与这个游戏的逻辑本身好理解,过程也能轻松掌握,但是代码的执行过程太难理解了,对于递归的代码逻辑云里雾里 |
Beta Was this translation helpful? Give feedback.
-
我刚开始在n==1那里判断的时候有疑惑,但是当我仔细思考,走了一遍这个流程以后,我发现汉诺塔实际上,不管有多少个盘子,我们都可以把他理解为要把两个盘子移到另一个盘子上面,由于游戏规则规定,小的必须在大的上面,所以我们要借用缓冲柱来完成目标,先将小的移走,大的放到目标柱的底部,再将小的放上去。如果是有多个盘子的时候,其实问题也不大,因为这个游戏他是从上至下的,所以先移动的盘子往往是最小的,不会触及小的在大的上面的规则,因此在后面我们也会借用源柱来作为缓冲柱,在不同的移动中对于源住缓冲柱,目标柱的定义也是不同的,比如我们要移六个盘子,那我们要先把上面五个移走,要移走五个则要先移走上面4个,如此往复到最后则是要先移走最上面的盘子,然后第二个盘子再移走,但是实际上用整体的思维来看,他永远都只在移动两个盘子而已 |
Beta Was this translation helpful? Give feedback.
-
这可比以前学这个的时候清晰多了! |
Beta Was this translation helpful? Give feedback.
-
private static void hnt_move(int n, String a, String b, String c) {
可以打印移动过程 |
Beta Was this translation helpful? Give feedback.
-
我们假设用一定的方式能把顶部的n-1层从A移动到B,然后将最大的那片移动到C。此时不要按照作者思路,我们假设将n-1层从B移动回到A,这时候再看,此时C是最大的那一片,那对于A的n-1那一摞来说和不存在这一片有什么区别呢?那问题就会变成一件非常简单的反复执行的事情这时候你就很容易理解这是一个递归或者循环的问题。此时的递归应当是 dfs(i - 1, src, tar, buf);
// 子问题 f(1) :将 src 剩余一个圆盘移到 tar
move(src, tar);
// 子问题 f(i-1) :将 buf 顶部 i-1 个圆盘借助 src 移到 tar
dfs(i - 1, buf, tar, src);//把i-1个盘子从B柱子移动回到A
dfs(i - 1, src, buf, tar);//然后变成一个全部重来的问题怎么把他从A移动到C 但是有个问题在于我并不需要把他移动到A再移动到C 而是直接移动到C就行,因为对于柱子来说他们本质没有区别,所以就从我的f(1),3个f(n-1)变为了2个n-1即可。这样会好理解一点。我的思路是不管什么问题,要先寻找他能形成一个重新变回原来一模一样问题状态的时刻,在实现了这个东西的原则下,再去寻找没有区别的多余步骤去优化。否则我们思路就会停留在会汉诺塔,但是换个塔就不知道怎么分割为递归的尴尬情况了。毕竟天才能直接想到的很少,遵循总结套路更适合像我一样的普通人 |
Beta Was this translation helpful? Give feedback.
-
不知道各位看不看得懂😂 |
Beta Was this translation helpful? Give feedback.
-
想请问一下为啥空间复杂度是 O(n) 而不是O(n^2)呢? |
Beta Was this translation helpful? Give feedback.
-
https://gallery.selfboot.cn/en/algorithms/hanoitower hanoi.mov |
Beta Was this translation helpful? Give feedback.
-
分享下我对这个问题的理解,无论是汉诺塔问题还是递归都可以借助类似数学归纳法的思路理解,简单来说,对于最基础的前3个盘子,1个盘子的移动最简单,2和3个盘子的移动都可以借助辅助柱分解为对1个盘子的操作,记作 f(2) = f(1) + f(1),f(3) = f(2) + f(1),而如果 f(n) = f(n-1) + f(1),成立,那么自然f(n-1) = f(n-2) + f(1)成立,所以对n个盘子的转移问题就可以转化为对n-1个盘子和最后一个盘子的转移问题。 |
Beta Was this translation helpful? Give feedback.
-
chapter_divide_and_conquer/hanota_problem/
动画图解、一键运行的数据结构与算法教程
https://www.hello-algo.com/chapter_divide_and_conquer/hanota_problem/
Beta Was this translation helpful? Give feedback.
All reactions