每天算法一丁点（1）--汉诺塔堆盘子

愚笨的我开始慢慢的学习算法之路。  既然开始的太晚，又不像大佬那般勤奋

索性每天就一点点，进步一点点也是好的呀

 

翻开了递归，求n阶倒是很快写完了，接下来便是汉诺塔堆盘子。。。

遇到这个问题就像小学时遇到 鸡兔同笼。似懂非懂。三个四个盘子还是数得过来的，直接要堆64个。。

这啥呀！直接摔书！         

根据书上的解释，用递归可以妥妥的解决这个问题。（《算法设计与实现》）

开始有64个盘子吭！3根柱子A、B、C。 要把摞好的64个盘子全部从A转移到C，并且中途只能小盘子压大盘子。 （直接一记嚎呦根）

老和尚要开始了，但是老和尚真的6：

1. 他想让第二个和尚把63个盘子移到柱B，然后自己把剩下的一个盘子移到柱C上，最后再第二个和尚把63个盘子移到柱C。

2. 第二个和尚也学习老和尚，让小和尚把62个盘子移到柱C，自己把一个盘子移到柱B，最后让小和尚把62个盘子移到柱B。。

3. 就这样一层层向下，赤裸裸压榨啊有木有！

不得不说这是个好方法，教会了我们要争做老和尚！

假设只有3个盘子，和尚们也这样划分任务。那第三个和尚只需移动一个盘子，不需要划分任务了。

这就是边界值，停止递归的条件。（最后一个和尚只需移动一个盘子）

综上所述，把n个盘子从柱A移动到柱C：

1. 把柱A上（n-1）个盘子移动到柱B
2. 把柱A上的第n个盘子移动到柱C
3. 把柱B上（n-1）个盘子移动到柱C

接下来上代码了：

#include <iostream>
using namespace std;

//分析：    把柱A上（n-1）个盘子利用柱C从A放到柱B； (n-1) A -> B
//         把柱A的一个盘子放到柱C；               1    A -> c
//         把柱B的（n-1）个盘子利用柱A从B放到柱C； (n-1) B -> C

void move(int n,char a,char b){
    printf("将第%d个盘子从%c运到%c
",n,a,b);
}
int hanoi(int n,char a,char b, char c){
    if(n==1){
        move(1,a,c);
    }
    else{
        hanoi(n-1,a,c,b);
        move(n,a,c);
        hanoi(n-1,b,a,c);
    }
    return 0;
}
int main(){
    int num;
    while(scanf("%d",&num)!=EOF){
        hanoi(num,'A','B','C');
    }
    return 0;
}

呜呜呜。。。少时不努力，老大不会打代码。。