C语言每日一练——第88天:汉诺塔问题(河内塔)

🌟 前言

大家好,我是Edison😎

今天是C语言每日一练,第88天!

Let’s get it!



1. 题目描述

汉诺塔问题

解题之前,我们先来了解一下 汉诺塔 到底是什么?

传说,在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针
 
印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片这就是所谓的汉诺塔
 
不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面
 
僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。
 
我也从网上找了张图片,大致是下面这样的🤔
在这里插入图片描述

2. 解题思路

思路很简单:有三根相邻的柱子,从左到右分别为:托盘A托盘B托盘C
 
托盘A按照“从下到上、从大到小”叠放着3个不同大小的盘子;👇
在这里插入图片描述
第一步:将盘子1从托盘A移动至托盘C👇
在这里插入图片描述
第二步:将盘子2从托盘A移动至托盘B👇
在这里插入图片描述
第三步:将盘子1从托盘C移动至托盘B👇
在这里插入图片描述
第四步:将盘子3从托盘A移动至托盘C👇
在这里插入图片描述
第五步:将盘子1从托盘B移动至托盘A👇
在这里插入图片描述
第六步:将盘子2从托盘B移动至托盘C👇
在这里插入图片描述
第七步:将盘子1从托盘A移动至托盘C👇
在这里插入图片描述
注:此过程图是我从网上找的,实在是难得画啦😂)

3. 动图演示

在这里插入图片描述

是不是很简单?

我们从上面移动的过程中,可以看到,托盘B始终作为一个过渡的存在,并且可以把它想象成中转柱
 
那么我们就可以这样理解:
 
托盘A:起始柱A;
 
托盘B:中转柱B;
 
托盘C:目标柱C
 

4. 代码实现

那么我们怎么用代码来实现呢?

这是一个非常经典的递归问题。
 
假设有n个盘子,需要把这些盘子从第一根起始柱A移动到第三根目标柱C中。
 
1、首先需要把n-1个盘子移动到第二根中转柱B上;
 
2、再把最后一个也就是最大的那一个盘子移动到第三根目标柱C上;
 
3、最后再把剩下的n-1个盘子移动到第三根目标柱C上。
 
我们定义

f

(

n

)

f(n)

f(n)是需要移动的次数;
 

f

(

1

)

=

1

f

(

2

)

=

3

f

(

3

)

=

7

f(1) = 1,f(2) = 3,f(3) = 7

f(1)=1f(2)=3f(3)=7

f

(

n

)

=

2

f

(

n

1

)

+

1

f(n) = 2f(n-1)+1

f(n)=2f(n1)+1

📝代码示例

这里拿3个盘子为例

#include <stdio.h>

void move(int n, char pos1, char pos3)
{
    //打印移动的过程
    // 1代表上面最小的盘子
    // 2代表中间位置的盘子
    // 3代表下面最大的盘子
    printf("盘子%d: 从 %c柱 移动到 %c柱n", n, pos1, pos3);

}

void Hanoi(int n, char pos1, char pos2, char pos3)
{
    //如果是1个盘子,直接从起始柱A移动到目标柱C
    if (n == 1) 
    {
        move(n, pos1, pos3);
    }
    else
    {
        //如果盘子大于1个,需要把n-1个盘子,从起始柱pos1,通过目标柱pos3,移动到中转柱pos2
        Hanoi(n-1, pos1, pos3, pos2); 

        //此时pos1上的n-1个盘子全部移动pos2上去了,那么可以直接把pos1上剩下的1个盘子,直接移动到pos3上
        move(n, pos1, pos3);

        //把pos2剩下的n-1个盘子,通过中转位置pos1,移动到目标位置pos3
        Hanoi(n-1, pos2, pos1, pos3);
    }
}

int main()
{
    //盘子个数
    int n = 3;

    //起始柱A
    char pos1 = 'A';

    //中转柱B
    char pos2 = 'B';

    //目标柱C
    char pos3 = 'C';

    printf("移动%d个盘子的步骤如下↓n", n);

    //汉诺塔函数
    Hanoi(n, pos1, pos2, pos3);

    return 0;
}

运行结果👇

在这里插入图片描述
完整代码贴图👇
在这里插入图片描述

5. 特性总结

回到我们这个题的本身,僧侣要移动64个金片,到底需要多久?
 
对于汉诺塔问题,

f

(

n

)

=

2

64

1

f(n) = 2^{64}-1

f(n)=2641 这是一个什么概念?
 
即使是每微秒移动一次, 也需要5000世纪的时间, 可能到那个时候,世界也许真的将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽🤣
 
不信的话,大家可以去试一试🐶

以上内容如有转载或引用请私聊说明并标明出处😘)

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>