chapter_divide_and_conquer/hanota_problem/

[giscus[bot]]

chapter_divide_and_conquer/hanota_problem/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_divide_and_conquer/hanota_problem/

[zhuasdfg]

这种递归代码看着别人写的简单，自己看的头疼也写不出来

[DXShelley]

知易行难

[krahets]

不断练习，慢慢会好起来的

[i-Remus]

"""
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, src, tar)
"""
这里看不太懂，为啥两次递归src,tar,buf参数的顺序不一样呢。。。？

[krahets]

Hi～ dfs 函数的后三个参数的含义分别为：源柱、辅助柱、目标柱。因为两次移动的子问题是不同的，所以参数输入的顺序不一样，可以对照一下注释仔细理解一下

[i-Remus]

感谢K神！我再仔细理解理解。。。数学底子薄，逻辑思维混乱-_-!

[xhddx]

上面的代码半天都理解不了，后面去油管搜到了这个视频，配合着看，可以把思路理清晰
https://www.youtube.com/watch?v=kEWQj2Hb8kc

[WheatJack]

总结下来就是：
现在有三根柱子 a、b、c（最简单的 就是a柱有三个盘子这种情况）a上面有多少圆盘其实我们不关心的，
1、只需要知道 把a上面的 n-1个圆盘 放到b柱子上， --超级操作-> 可以当作一个整体操作
2、然后再把a上面的最大的移动到c盘上 --微操作-> 就是一步简单操作
3、然后再把b柱子上所有的盘子移动到c盘上. --超级操作-> 可以当作一个整体操作

什么时候结束 那就是当只有一个盘子的时候返回 结束

[rmd1710714107]

贴一个B站的链接，上不了youtobe的看这个【【递归2】如何治疗晕递归?】 https://www.bilibili.com/video/BV1C14y1V77j/?share_source=copy_web&vd_source=db9ae3f53b716cf03347fd29ec2208dd

[lxm520]

大致理解就最小化时候是不是可以理解成这样

// 子问题 f(i-1) ：将 src 顶部 i-1 个圆盘借助 tar 移到 buf
dfsSovleHanota(i - 1, src, tar, buf); // 当i为2时， move(src, buf);
// 子问题 f(1) ：将 src 剩余一个圆盘移到 tar
move(src, tar);
// 子问题 f(i-1) ：将 buf 顶部 i-1 个圆盘借助 src 移到 tar
dfsSovleHanota(i - 1, buf, src, tar); // 当i为2时， move(buf, tar);

就相当于i=2时
move(src, buf);
move(src, tar);
move(buf, tar);

这样就相当于完成了2个的移动，别的只是在递归实现

[qw124341789]

感觉递归的核心思路就是，虽然代码没有实现，但是我相信我自己写的代码，写完他就成立了。

[dbcj2015]

不是只能从顶部一个一个拿吗？为啥直接遍历到地盘直接拿出底层的盘子呢？

[jiandandian2]

先拿n-1个，这n-1个都是一个一个拿的

[ningblue]

请问：
“将 A 顶部的两个圆盘看作一个整体” 和要求中的“每次只能移动一个圆盘。”是否有冲突呢？

[zzzhty]

看作整体，但是每次移动还是一个一个移的，这就是为什么dfs函数里面必须有buf的原因。

[ningblue]

嗯 实际的代码在逻辑中是没问题的,
只不过这个描述在题目的字面上理解,感觉不太精准,如果两个可以看作一个整体,那么每次只能移动一个圆盘的规则限定就显得模糊了

[krahets]

“看作一个整体”代表构建一个“子问题”，当递归到基本情况（1 个圆盘）时，再进行实际的移动操作

[xxc111111]

对与这个游戏的逻辑本身好理解，过程也能轻松掌握，但是代码的执行过程太难理解了，对于递归的代码逻辑云里雾里

[krahets]

试着把递归树画出来看看～

[codecat996]

可以拿一张纸把代码写下开，初始化一个长度为小的数组，按照代码执行的顺序，把数据一步一步的记录下来

[OrdinaryChen]

先有递归时候你在装套娃，你一直在等第一个人真的把东西放进第一个盒子开始装然后交给第二个人，直到你。一定要有一种没轮到你你在干等着的感觉才行。我发现很多人无法想象这个线性的等待，对于同时分裂出来的事情总有一种他在做这个的时候那之前那个呢的臆想从而变得非常混乱。线性，不理解直接想想你在把A的n-1移动到B但是怎么移，你不知道，你外包给别人我在干等，那那个人呢 ，他在干等n-2，那n-（n-1）呢，哦，他在把顶上那一块放到C，然后做两个f（2）把他移动成A上少两个B上有一个小C上一个大，然后叫第三个人移动呢，你呢，反正就这种感觉。。。我扯扯淡 希望能帮到你。。。。

[OrdinaryChen]

你炒菜要等放酱油，酱油呢，有个人在等晒，为什么要等，因为黄豆在地里没收，现在第三个人在收了。。。然后顺着链路重新想象我先收黄豆，然后这时候返回上一次命令我收黄豆的人那里，然后他做酱油再给你做菜，我都是这样想的。。。。

[nors1993]

递归的逻辑本身很简单，就是不停的在n和n-1迭代计算到最后一个，但是从代码上看调用自身，感觉啥也没写，却又很神奇。。。。。。。。。。。

[Coolllh]

我刚开始在n==1那里判断的时候有疑惑，但是当我仔细思考，走了一遍这个流程以后，我发现汉诺塔实际上，不管有多少个盘子，我们都可以把他理解为要把两个盘子移到另一个盘子上面，由于游戏规则规定，小的必须在大的上面，所以我们要借用缓冲柱来完成目标，先将小的移走，大的放到目标柱的底部，再将小的放上去。如果是有多个盘子的时候，其实问题也不大，因为这个游戏他是从上至下的，所以先移动的盘子往往是最小的，不会触及小的在大的上面的规则，因此在后面我们也会借用源柱来作为缓冲柱，在不同的移动中对于源住缓冲柱，目标柱的定义也是不同的，比如我们要移六个盘子，那我们要先把上面五个移走，要移走五个则要先移走上面4个，如此往复到最后则是要先移走最上面的盘子，然后第二个盘子再移走，但是实际上用整体的思维来看，他永远都只在移动两个盘子而已

[krahets]

是的，一直在“移动” n-1 个盘子 和 1 个盘子，重点是将 n-1 个盘子看作一个整体来处理。

[RightNode]

这可比以前学这个的时候清晰多了！

[OnlyAPI]

private static void hnt_move(int n, String a, String b, String c) {
if (n == 1) {
System.out.println(a + " ---> " + c);
return;
}

    hnt_move(n - 1, a, c, b);
    System.out.println(a + " ---> " + c);
    hnt_move(n - 1, b, a, c);

}

可以打印移动过程

[OnlyAPI]

private static void hnt_move(int n, String a, String b, String c) {
        if (n == 1) {
            System.out.println(a + " ---> " + c);
            return;
        }

        hnt_move(n - 1, a, c, b);
        System.out.println(a + " ---> " + c);
        hnt_move(n - 1, b, a, c);

    }

[OnlyAPI]

public static void main(String[] args) {
        int n = 3;
        hnt_move(n, "A", "B", "C");
    }

[NormanCarrie]

妙啊！

[OrdinaryChen]

我们假设用一定的方式能把顶部的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即可。这样会好理解一点。我的思路是不管什么问题，要先寻找他能形成一个重新变回原来一模一样问题状态的时刻，在实现了这个东西的原则下，再去寻找没有区别的多余步骤去优化。否则我们思路就会停留在会汉诺塔，但是换个塔就不知道怎么分割为递归的尴尬情况了。毕竟天才能直接想到的很少，遵循总结套路更适合像我一样的普通人

[480284856]

授之以渔，赞！

[HuaWang135608]

复杂度过高，f(21) 和章节中的 f(32) 的复杂度差不多了

[HuaWang135608]

不知道各位看不看得懂😂
汉诺塔理解图