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

[GeekKwok]

U管的这个视频很棒 建议大家多看看 相信会有更深入理解！

[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]

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

[thinkingIsMagic]

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

[ningblue]

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

[zzzhty]

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

[ningblue]

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

[krahets]

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

[xxc111111]

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

[codecat996]

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

[OrdinaryChen]

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

[OrdinaryChen]

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

[nors1993]

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

[akfc58]

递归就是你在造一个有某种功能的锤子，但在造锤子ing的时候，就已经在利用这个锤子的功能完成这个造锤子的任务。等你锤子造好了，任务也可以被顺利完成了。

[Coolllh]

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

[krahets]

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

[chumingqian]

个人觉得让人难以理解的地方是， 当只有 一个 或者两个盘子的时候， 让人可以理解；
而当出现三个盘子的时候，即文中的 f(3) 问题， 此时说的是将 两圆盘从 A移动到B, 同理 将（i-1） 个圆盘从A移动到B, 将多个圆盘 看做一个整体 与 题目中表达的 每次只能移动一个圆盘， 这中思维与题目所表述的思维 两者有矛盾冲突之处， 所以难以让人接收

[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");
    }

[ghost]

妙啊！

[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]

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

[aratakicat]

想请问一下为啥空间复杂度是 O(n) 而不是O(n^2)呢？

[wzl521]

利用数组存储，应该是o（n）吧

[hanwencat]

递归调用不是并行发生的，而是顺序进行的，不会同时占用调用空间。递归树的高度n（盘子的数量）既为调用f函数的最大深度。处理完第一个（n-1）调用后才会处理第二个（n-1），然后再（n-2）、（n-2）、（n-3）、（n-3）。。。

[selfboot]

https://gallery.selfboot.cn/en/algorithms/hanoitower
做了个交互的可视化，支持手动和自动模式来玩汉诺塔，支持从任意初始状态开始。

hanoi.mov

[git-haoyi]

great！

[luxting]

interesting！

[BLackWatch1118]

分享下我对这个问题的理解，无论是汉诺塔问题还是递归都可以借助类似数学归纳法的思路理解，简单来说，对于最基础的前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个盘子和最后一个盘子的转移问题。
这种思路天然适用递归的实现，递归函数需要执行三个步骤，将前n-1个盘子转移到缓冲柱，将最后一个盘子转移到目标柱，将缓冲柱上的盘子转移到目标柱。终止条件为只剩一个盘子时将其转移到目标柱。如果已经证明问题可以分解，并且递归函数对于最后一个盘子也生效的话，只需要确保递归函数成功完成了对问题的划分，那么自然能够达成目标，并不需要过多考虑递归函数到底做了什么。

[pianfan]

纠正一下：
f(2) = f(1) + f(1) + f(1)
f(3) = f(2) + f(1) + f(2)
......
f(n) = f(n-1) + f(1) + f(n-1)

其他说得没问题

[hazukieq]

假设有 n 个圆盘，则：每次把前面 n-1 个当成整体，实际挪动的就只有 n-1 整体和 1 两个圆盘了，从而有： f(n-1)->f(1)->f(n-1)。而 n-1 个又可以继续切分为 n-2 和 1 两个部分....

$f(1)$ 我们可以写成 $f_1(x,y)：x\to y$ ，也就是 move函数，表示 一个圆盘从 x 柱子 挪动到 y 柱子。

然后 根据图12-12的挪动步骤，$f_2(a,b,c) $ 我们可以分解成: $f_1(a,b)\to f_1(a,c)$

$f_3(a,b,c): f_2(a,c,b)\to f_1(a,c)\to f_2(b,a,c)$，其中 $f_2(a,c,b)$ 可以理解为 两个圆盘从 a 挪动 c，然后再挪动到 b.

可知:

$f_n(a,b,c)=f_{n-1}(a,c,b)\to f_1(a,c)\to f_{n-1}(b,a,c)$

$f_{n-1}(a,c,b)=f_{n-2}(a,b,c)\to f_1(a,b) \to f_{n-2}(c,a,b)$

......

$f_3(a,b,c): f_2(a,c,b)\to f_1(a,c)\to f_2(b,a,c)$

$f_2(a,b,c): f_1(a,b)\to f_1(a,c)$

然后，层层返回去替换，即可得到答案.

打印挪动步骤版本:

/**
* x,y 表示柱子.
* move(a,b) 表示 一个圆盘从 a 柱子 挪动到 b 柱子
**/
void move(char x,char y){
          printf("%c->%c\n",x,y);
 }
 
/**
* i 表示 圆盘数量
* a,b,c 表示柱子.
**/
void dfs(int i,char a,char b,char c){
    if(i==1){
             move(a,c);
             return;
    } 
    dfs(i-1,a,c,b);
    move(a,c);
    dfs(i-1,b,a,c);
}

[hazukieq]

$f_2(a,b,c)$ 那里没写全，
应该是 $f_2(a,b,c)=f_1(a,b) \to f_1(a,c) \to f_1(b,c)$

[syutengu]

学习笔记，js版，可视化

[syutengu]

学习笔记，js版，可视化

  /* 递归分治 */
  function hanoi_recur(n) {
    /* for test */
    let status = 0
    /* 初始化，数组模拟三柱，出发柱依次添加[n,1]模拟碟的初始位置 */
    const [a, b, c] = [[], [], []]
    for (let i = n; i > 0; i--) a.push(i)

    log()//初始状态
    move(n, a, b, c) //move(项(碟)数,出发柱,缓冲柱,目标柱)
    log()//完成状态

    function move(n, src, buf, dst) {
      if (n <= 1) return dst.push(src.pop())
      n--
      move(n, src, dst, buf)//为了把最底项移动到目标柱，必须先把上面的n-1项临时移动到缓冲柱
      log()
      move(1, src, buf, dst)//移动最底项，从出发柱直接到目标柱
      log()
      move(n, buf, src, dst)//把n-1项从缓冲柱移动到目标柱
    }

    /* 展示移动过程 */
    function log() {
      console.log(status++, `[${a.join(',')}] / [${b.join(',')}] / [${c.join(',')}]`)
    }
  }

[akiradavidsong]

上一节的内容太难了，所以看这一节时，感觉容易了很多