认识分治算法

分治法在每一层递归上都有三个步骤：

分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
合并：将各个子问题的解合并为原问题的解
借汉罗塔问题深刻理解分治
汉诺塔问题是一种多分支的递归解法，相对于单分支的递归解法（如：阶乘的递归解法）来说，不太容易理解。对于这种多分支的递归算法来说，如果像理解单分支递归那样，在脑海中尽可能的穷举出每一步的移动过程，有时候是很困难的，这样也不符合用递归解决问题的原则

可见其复杂，但是我们可以一步一步分析来看看其中的规律

移动次数为：2^n - 1
我们从n=[1,4]的区间，来看看其中移动的变化，从而看出其中的对称性
（1）n == 1
第1次 A——>C sum = 1 次
（2） n == 2
第1次 A——>B
第2次 A——>C
第3次 B——>C sum = 3 次
（3）n == 3
第1次 A——>C
第2次 A——>B
第3次 C——>B
第4次 A——>C
第5次 B——>A
第6次 B——>C
第7次 A——>C sum = 7 次
（4）n ==4
第1次 A——>B
第2次 A——>C
第3次 B——>C
第4次 A——>B
第5次 C——>A
第6次 C——>B
第7次 A——>B
第8次 A——>C
第9次 B——>A
第10次 B——>C
第11次 A——>C
第12次 B——>A
第13次 C——>B
第14次 C——>A
第15次 B——>A sum = 15次
大家明显可以看到的是，每次都以总数sum的中位数处的A—->C为对称轴的
我再用数学表达出来，你会发现更有趣的
n=1 sum = 1
n=2 sum = 1 + 1 + 1 = 3
n=3 sum = 3 + 1 + 3 = 7
n=4 sum = 7 + 1 + 7 = 15
我就以n=3 和 n=4为例。现在已经知道n=3的时候，总数sum=7
我们现在处在n=4的情况，进行不断换位后，来到关键的一步A——>C。那么现在的汉罗塔分布情况是怎样的？

我觉得我已经讲得清楚，你让我现在分析n=5，必然也是这种情况
n=5 sum = 15 + 1 +15
前15次为了把A柱子中最低端的盘子放到C柱上去做准备，中间1次就是实际意义上的把A柱子中最低端的盘子放到C柱上的操作本身，后15次的操作不用分析，这个时候就等价于分析n=4本身了。所以前半截的目的就是把除开最底端的盘子剩余的盘子移动到B柱，然后把最底端盘子移动到C柱，后半截就相当于由n=5转换到n=4了，我相信你已经看到里面的不断重复操作，直到n=1才算递归结束。也就是说求解 N 和求解 N-1 的思路完全一致，这是保证可以使用递归算法的核心所在。
想必大家就可以看明白下面这张图，而且理解我们下面的代码了

前一行代码就是我们描述的前15次
中间行代码就是我们描述的A——>C
后一行代码就是我们描述的n=5已经转换到n=4本身
这个时候，不就等同于进入盘子等于4的时候吗？我想你已经彻底明白了

#include<stdio.h>
void hnt(int n, char a,  char b, char c){
   if(n == 1){   // 递归出界条件，每个递归必须具备的条件
       printf("%c -- > %c \n", a,c); 
   }else{
       /*
       每一层递归的逻辑都是，借助"目标柱子"，将n-1个 盘子移动到  "中转柱"，然后再将最后一个盘子移动到"目标柱子".
       注意，这里的中转柱是会变化的。
    大家不要被a,b,c名称给迷惑掉，要注意我们的函数怎样定义的
    hnt(int n, char a,  char b, char c)---》总数，起始，中转，目标
    所以谁在变换的过程中，被视为中转就要被放到中间去（char b），谁变成起始就要放到开头(char a)，谁是被放到目标上去就是放到末尾(char c)
       */
       hnt(n-1,a,c,b); // ① 借助 c 柱子将a柱子上的n-1个盘子 移动到 b 柱子上，
    //借助c,所以c放到中间去，把a上的n-1个盘子放到移动到b柱子上，所以b被放到目标柱了
       printf("%c -- > %c \n", a,c); //  ② 将 a柱子上的第n个盘子 移动到 c柱子上，这一步是固定的，前面已经详细分析了
       hnt(n-1, b,a,c);  // ③ 将在b柱子上的n-1个盘子，借助 a 柱子（此时a空闲） 移动到 c 柱子上
    //借助a，所以a放到中间去，把b柱上的n-1个盘子放到移动到c柱子上，所以c被放到目标柱了
   }
}
int main(){
   int n;
   scanf("%d", &n);
   hnt(n,'a','b','c');
   return 0;
}

借助这几篇文章，我认为把汉罗塔分析的一清二楚，甚至包括代码为什么这样写的分析

分治

认识分治算法

借汉罗塔问题深刻理解分治