首页 > 编程语言 > 详细

每天算法一丁点(1)--汉诺塔堆盘子

时间:2019-12-26 19:16:51      阅读:70      评论:0      收藏:0      [点我收藏+]

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

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

 

翻开了递归,求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",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;
}

 

 

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

每天算法一丁点(1)--汉诺塔堆盘子

原文:https://www.cnblogs.com/yinniora/p/12103685.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!