C语言函数递归经典题型——汉诺塔问题

一.汉诺塔问题介绍

        Hanoi（汉诺）塔问题。古代有一个梵塔，塔内有3个座A、B、C，开始时Ａ座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从Ａ座移到Ｃ座，但规定每次只允许移动一个盘，且在移动过程中在3个座上都始终保持大盘在下，小盘在上。在移动过程中可以利用B座。要求编程序输出移动一盘子的步骤。

二.解题思路

把A B C分成 起始座 中间座 目标座

        我们先分析两个盘子情况：

①②③

④（先将上面的移到B，再把下面的移到C，最后把B处的移到C）

        我们再来分析三个盘子情况：

①②③

④⑤⑥

⑦⑧

{  首先把这三个盘子分为两部分：最底下的大盘子和上面所有小盘子，然后我们根据两个盘子的情况，考虑先把上面所有小盘子移动到B，把大盘子移动到C，最后把所有小盘子移动到C，而把上面所有小盘子移动到B的步骤和上面我们刚分析的移动两个盘子的情况类似，（只是移动到B而不是C的区别），此时我们可以把C看成中间座，把B看成目标座（也就是说在三个盘子情况下又嵌套一个两个盘子的汉诺塔问题），当把上面所有小盘子移动到B的时候（第⑤步），我们需要把所有小盘子借助A移动到C，此时A看成中间座，C看成目标座，移动方法和上面分析的两个盘子移动情况类似（又嵌套一个两个盘子的汉诺塔问题），此时函数递归的“影子”逐渐清晰。 }

        上面的文字很关键，通过比较两个和三个盘子的步骤找到函数递归的身影！！！

        当盘子个数增加的时候，规律还是一样。

        下面我们通过代码把这个问题解决

代码如下：

#include <stdio.h>
void move(char A, char B)
{
	printf("%c -> %c\n", A, B);
}
void hanoi(int n, char A, char B, char C,int *count)
{
	(*count)++;
	if (n == 1)
	{
		move(A, C);
	}
	else
	{
		hanoi(n - 1, A, C, B,count);
		move(A, C);
		hanoi(n - 1, B, A, C,count);
	}
}
int main()
{
	int count = 0;
	int n=0;
	printf("请输入盘子总数：");
	scanf("%d", &n);
	hanoi(n, 'A', 'B', 'C',&count);
	printf("需要移动总次数%d",count);
	return 0;
}

运行结果：

代码解读：

①使用了move，hanoi函数，并且利用count求需要移动的次数。

②在使用count求传递次数的时候，要调用count的地址，进行函数的传址调用（因为要修改主函数count的值）。（传值传址调用在函数基本知识（一）中有详细的讲解）。

本期汉诺塔问题就分析到这里~~~

往期回顾：

C语言——数组基本知识（二）-CSDN博客

C语言——数组基本知识（一）-CSDN博客

C语言——数组逐元素操作练习-CSDN博客

C语言编程练习：验证哥德巴赫猜想 进制转换 rand函数-CSDN博客

C语言——函数基本知识（三）-CSDN博客

C语言——函数基本知识（二）-CSDN博客

C语言 ——函数基本知识（一）-CSDN博客

C语言穷举法算法经典题型（二）_编写程序,输入x,输出y y= x2+3x-4 (x≤5) =x2-5x+7 (x>5) 输入 一个-CSDN博客

C语言穷举法算法经典题型（一）_c语言穷举法经典例题-CSDN博客