有趣的数据结构算法1——汉诺塔问题的C语言实现及其解析

朱雀 2021-12-12 01:43 155阅读 0赞

### 汉诺塔问题的C语言实现及其解析 ###

*  题目复述
 *  题目分析
 *  具体实现代码
 *  GITHUB下载连接

# 题目复述 #

汉诺塔问题是一个经典的递归问题，其有3根柱子分别是：A，B，C。第一根柱子A上有n个盘子，从上到下依次增大，要第一根柱子A上的所有的盘子移动到第三根柱子C上，整个过程都必须满足一根柱子上的盘子从上到下依次增大。  
初学数据结构与算法，这个问题真的是噩梦。  
![在这里插入图片描述][20190723165955317.jpg_pic_center]

# 题目分析 #

对于汉诺塔问题而言，题目一共给予了我们A、B、C三个杆子，而不是两个杆子，这是为什么呢？这里有一个很重要的思路就是：

**可以通过利用杆子B，将A上的盘子移动到C上。**

再了解了以上这个思路后，我们便可以将汉诺塔问题分为三步完成。  
（假设初始状态下杆子A上的盘子数量为n）  
1、将杆子A上的n-1个盘子通过杆子C移动到杆子B，此时杆子A上的盘子有一个，杆子B上的盘子有n-1个。  
2、将杆子A上剩余的一个盘子移动到杆子C，此时杆子C上的盘子有一个，杆子B上的盘子有n-1个。  
3、将杆子B上的n-1个盘子通过杆子A移动到杆子C，该步骤可以重复上述两个步骤的过程。

汉诺塔问题利用递归函数解决的关键在于建立一个函数，函数的内容为：  
void hannuota(int n,char A,char B,char C)  
该函数表示的是——>将A杆子上的n个盘子，利用B杆子作为媒介，转移到C杆子。

此时如果利用代码来表述上列的执行过程，则如下所示：

hannuota(n - 1, A, C, B); //将A杆子上的n-1个盘子，利用C杆子作为媒介，转移到B杆子。
    printf("%c --> %c\n", A, C);//将杆子A上剩余的一个盘子移动到杆子C
    hannuota(n - 1, B, A, C);//将B杆子上的n-1个盘子，利用A杆子作为媒介，转移到C杆子。

# 具体实现代码 #

#include <stdio.h>
     void hannuota(int,char,char,char);
     
     //该函数表示的是——>将A杆子上的n个盘子，利用B杆子作为媒介，转移到C杆子。
     void hannuota(int n,char A,char B,char C){
        
     	if (n == 1){
        
     		printf("%c --> %c\n", A, C);
     	}
     	else{
        
     		hannuota(n - 1, A, C, B);//将A杆子上的n-1个盘子，利用C杆子作为媒介，转移到B杆子。
     		printf("%c --> %c\n", A, C);//将杆子A上剩余的一个盘子移动到杆子C
     		hannuota(n - 1, B, A, C);//将B杆子上的n-1个盘子，利用A杆子作为媒介，转移到C杆子。
     	}
     }
     
     int main(){
        
     	int layer;
     	printf("请输入汉诺塔的层数：");
     	scanf("%d", &layer);
     	hannuota(layer, 'A', 'B', 'C');
     	return 0;
     }

# GITHUB下载连接 #

[https://github.com/bubbliiiing/Data-Structure-and-Algorithm/tree/master][https_github.com_bubbliiiing_Data-Structure-and-Algorithm_tree_master]

希望得到朋友们的喜欢。

[20190723165955317.jpg_pic_center]: /images/20211211/75d1122f9f4245419b1fabed9827ac38.png
[https_github.com_bubbliiiing_Data-Structure-and-Algorithm_tree_master]: https://github.com/bubbliiiing/Data-Structure-and-Algorithm/tree/master