汉诺塔问题

问题:大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

分析:主要就是递归的思想;
题目要求是将所有圆盘最终从A号柱移动到C号柱,对于问题规模为n的情况,可将问题分解为三步:
1.将顶上的n-1个黄金圆盘从A号柱通过C号柱移动到B号柱上。
2.将A号柱子上的最后一个圆盘移动到C号柱上。
3.将B号柱上的n-1个圆盘通过A移动到C号柱上。

代码:
#include<stdio.h>
int move_times=0;
//把盘子从a移动到c
void Hanoi(int num_disk,char a,char b,char c)
{
if(num_disk==0) return;
else if(num_disk==1)
{
move_times++;
printf("move the disk %d from %c to %c\n",num_disk,a,c);
return;
}
else {
Hanoi(num_disk-1,a,c,b);
printf("move the disk %d from %c to %c\n",num_disk,a,c);
move_times++;
Hanoi(num_disk-1,b,a,c);
}

}
int main()
{
    int num_disk;
    printf("input the number of disk:\n");
    scanf("%d",&num_disk);
    Hanoi(num_disk,'a','b','c');
    printf("the move times is %d\n",move_times);
    return 0;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 起源 汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子...
    小白frankie阅读 8,832评论 0 2
  • 文章也同时在个人博客 http://kimihe.com/[http://kimihe.com/2016/12/2...
    QihuaZhou阅读 7,156评论 0 2
  • 汉诺塔是指这个: 目标是要把所有的盘子从最左边(柱子A)移动到最右边(柱子C),条件是 1)每次只能移动一个盘子 ...
    mouse33333阅读 7,983评论 7 8
  • 1. Introduction 大梵天创造世界的时候做了三根柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆...
    MangoDai阅读 3,698评论 0 0
  • 都说高考会是人生中一次难忘的经历,可是随着时间的流逝我怕我会忘记,我怕我会渐渐记不清那些让我最珍惜的时刻。现在有时...
    热泪xrs阅读 2,750评论 0 0