递归—汉诺塔

Akari2023-11-072024-01-10

57 _ 递归8 _ 汉诺塔_1_哔哩哔哩
趁热打铁，记录下来，后续有什么再补充。

问题引入：

分析

主要是运用递归的思想。将规模为n的问题转为为规模为n-1的问题，直到可以一步解决。

伪代码

如果是1个盘子
    直接将A柱子上的盘子移到C上
否则
    先将A柱子上的n-1个盘子借助C移到B
    直接将A柱子上编号为n的盘子移到C
    最后将B柱子上的n-1个盘子借助A移到C

C版本：

/**
 * @brief: 
 * @version:  
 * @author: @Shiel
 * @date: 2023-11-7 22:12:17
 **/
#include <stdio.h>

//依次表示 要移动的盘子个数、盘子所在柱子、借助的柱子、目标柱子
void Hannuota( int n, char A, char B, char C );

int main(void)
{
	//定义三个柱子 和 要移动的盘子个数
	char ch1 = 'A';
	char ch2 = 'B';
	char ch3 = 'C';
	int n;
	
	printf("输入要移动的盘子个数：");
	scanf("%d", &n);
	Hannuota(n, 'A', 'B', 'C');
	
	return 0;
}

void Hannuota( int n, char A, char B, char C )
{
	if( n == 1 )
	{
		printf("将编号为%d的盘子从%c直接移到%c上\n", n, A, C);
	}
	else
	{
		Hannuota( n - 1, A, C, B );
		printf("将编号为%d的盘子从%c直接移到%c上\n", n, A, C);
		Hannuota( n - 1, B, A, C );
	}	
}