16-数据结构_递归_汉诺塔-图解与实现

缺乏、安全感 2021-11-26 12:50 201阅读 0赞

# 一, 图解 #

![SouthEast][]

![SouthEast 1][]

![SouthEast 2][]

![SouthEast 3][]

![SouthEast 4][]

![SouthEast 5][]

# 二, 实现 #

#include <stdio.h>
    
    /*
    n: 需要移动的盘子数
    A: 存放盘子的柱子, 即需要被移动 n 个盘子的柱子
    B: 临时 存放盘子的柱子
    C: 把盘子n个盘子移动到那个柱子
    */
    void hanoiTower(int n, char A, char B, char C)
    {
    /*
        if ( 只有一个盘子 ) // 此时盘子的编号为 1
        {
            直接将A柱子上的盘子移动到C柱子   
            返回
        }
        1, 先将A柱子上的 n-1 个盘子, 借助 C柱子, 移动到B柱子 
           --此时, A上只有最大的那个盘子, B上有n-1个盘子, C上没盘子
    
        2, 直接将A柱子上的 最后那个盘子 移动到 C柱子
           --此时, A上没盘子, B上有n-1个盘子, C上有最大的那个盘子 
    
        3, 最后将B柱子上的n-1个盘子借助A柱子移动到C柱子
           --此时, 完成
    */
    
        if (1 == n)
        {
            printf("柱%c-盘%d ==> 柱%c\n", A, n, C);
            return;
        }
        
        hanoiTower(n-1, A, C, B);
    
        printf("柱%c-盘%d ==> 柱%c\n", A, n, C);
    
        hanoiTower(n-1, B, A, C);
    
    }
    
    int main(void)
    {
        char A = 'A';
        char B = 'B';
        char C = 'C';
        int acount;
        
        printf("盘子数: ");
        scanf("%d", &acount);
        
        hanoiTower(acount, A, B, C);
    
        return 0;
    }

[SouthEast]: /images/20211126/7020218372c64ed0a93a82db7b6107b4.png
[SouthEast 1]: /images/20211126/c5863bb8497c47e2b4180814884e0d3f.png
[SouthEast 2]: /images/20211126/234e39efbee942659b8a9f6fd42a7d1c.png
[SouthEast 3]: /images/20211126/2667a2f69921410fad54a85ff43aa116.png
[SouthEast 4]: /images/20211126/c0731f9e46c64a49ae35881956824f3d.png
[SouthEast 5]: /images/20211126/aebdc5099d2845118e8ce127790da409.png