【C语言程序设计】汉诺塔问题，用C语言实现汉诺塔！

蔚落 2022-11-07 05:27 180阅读 0赞

汉诺塔问题是指：一块板上有三根针 A、B、C。A 针上套有 64 个大小不等的圆盘，按照大的在下、小的在上的顺序排列，要把这 64 个圆盘从 A 针移动到 C 针上，每次只能移动一个圆盘，移动过程可以借助 B 针。

> 但在任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上。从键盘输入需移动的圆盘个数，给出移动的过程。

### 算法思想 ###

对于汉诺塔问题，当只移动一个圆盘时，直接将圆盘从 A 针移动到 C 针。

若移动的圆盘为 n(n>1)，则分成几步走：把 (n-1) 个圆盘从 A 针移动到 B 针（借助 C 针）；A 针上的最后一个圆盘移动到 C 针；B 针上的 (n-1) 个圆盘移动到 C 针（借助 A 针）。

每做一遍，移动的圆盘少一个，逐次递减，最后当 n 为 1 时，完成整个移动过程。

因此，解决汉诺塔问题可设计一个递归函数，利用递归实现圆盘的整个移动过程，问题的解决过程是对实际操作的模拟。

### 程序代码 ###

#include <stdio.h>
    
    int main()
    
    {
    
        int hanoi(int,char,char,char);
    
        int n,counter;
    
        printf("Input the number of diskes：");
    
        scanf("%d",&n);
    
        printf("\n");
    
        counter=hanoi(n,'A','B','C');
    
        return 0;
    
    }
    
    int hanoi(int n,char x,char y,char z)
    
    {
    
        int move(char,int,char);
    
        if(n==1)
    
            move(x,1,z);
    
        else
    
        {
    
            hanoi(n-1,x,z,y);
    
            move(x,n,z);
    
            hanoi(n-1,y,x,z);
    
        }
    
        return 0;
    
    }
    
    int move(char getone,int n,char putone)
    
    {

### 调试运行结果： ###

当移动圆盘个数为 3 时，具体移动步骤如下所示：

> Input the number of diskes：3
> 
> 1:  1 \# A---C
> 
> 2:  2 \# A---B
> 
> 3:  1 \# C---B
> 
> 4:  3 \# A---C
> 
> 5:  1 \# B---A
> 
> 6:  2 \# B---C
> 
> 7:  1 \# A---C

### 总结： ###

本实例中定义的 hanoi() 函数是一个递归函数，它有四个形参"n""x""y""z"。

"n" 是移动的圆盘个数，"x""y""z" 分别表示三根针，其功能是把 x 上的 n 个圆盘移动到 z 上。

▶ 当 n=1 时，直接把 x 上的圆盘移到 z 上，输出"x---Z"。

▶ 当 n!=1 时，则递归调用 hanoi() 函数，把 (n-1) 个圆盘从 x 移到 y，输出"x—-z"；再递归调用 hanoi() 函数，把 (n-1) 个圆盘从 y 移到 z。

在递归调用函数的过程中"n=n-1"，n 的值逐次递减，最后 n=1，终止递归调用，逐层返回，移动过程结束。

![4cfdceac58eb45a5d88ee280e51493ae.gif][]

不管你是转行也好，初学也罢，进阶也可，如果你想学编程，进阶程序员~

【**值得关注**】我的 **[编程学习交流俱乐部][Link 1]！【点击进入】**

![1b3c3f17fa7bc9a1e41d2f94017b040b.png][]

[4cfdceac58eb45a5d88ee280e51493ae.gif]: /images/20221023/cabebad2f38941d0a7e1839ccbfd8568.png
[Link 1]: https://jq.qq.com/?_wv=1027&k=teZNipK1
[1b3c3f17fa7bc9a1e41d2f94017b040b.png]: /images/20221023/56b9093b49124bc187bcb3e386e7809c.png