Dotcpp  >  编程教程  >  算法基础  >  用C语言解答汉诺塔问题

用C语言解答汉诺塔问题

点击打开在线编译器,边学边练

汉诺塔相信很多人小时候都玩过这样的游戏,这是源于印度的古老传说,大家可千万不要小看这个游戏,里面体现了古人的大智慧,在这里我们能学到最直观的演示方法,本篇主要是针对汉诺塔的问题进行分析和代码展示。


一、前言

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

汉诺塔问题


二、解题思路

思路很简单:有三根相邻的柱子,从左到右分别为:托盘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

汉诺塔问题

动图演示

0b795385c68d43a88fd535038da4b29a.gif

是不是很简单?

我们从上面移动的过程中,可以看到,托盘B始终作为一个过渡的存在,并且可以把它想象成中转柱;

那么我们就可以这样理解:

托盘A:起始柱A;

托盘B:中转柱B;

托盘C:目标柱C


三、代码实现

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

这是一个非常经典的递归问题。

假设有n个盘子,需要把这些盘子从第一根起始柱A移动到第三根目标柱C中。

(1)首先需要把n-1个盘子移动到第二根中转柱B上;

(2)再把最后一个也就是最大的那一个盘子移动到第三根目标柱C上;

(3)最后再把剩下的n-1个盘子移动到第三根目标柱C上。

我们定义f(n)是需要移动的次数; 

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

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


代码如下:

#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;
}

如果我们编译并运行上述程序,那么它应该产生以下结果:

移动3个盘子的步骤如下↓
盘子1: 从 A柱 移动到 C柱
盘子2: 从 A柱 移动到 B柱
盘子1: 从 C柱 移动到 B柱
盘子3: 从 A柱 移动到 C柱
盘子1: 从 B柱 移动到 A柱
盘子2: 从 B柱 移动到 C柱
盘子1: 从 A柱 移动到 C柱


作业:
2056汉诺塔

本文固定URL:https://www.dotcpp.com/course/949

算法竞赛教程
第一章 算法基础
第二章 搜索算法
第三章 排序算法
第四章 字符串相关
第五章 数学相关
第六章 动态规划
第七章 数据结构
第八章 图论
第九章 计算几何
第十章 其他算法
Dotcpp在线编译      (登录可减少运行等待时间)