当前位置：首页 > article >正文

汉诺塔（hanio）--C语言函数递归

article 2024/11/26 8:24:21

文章目录

前言
一、汉诺塔的图解
二、问题分析
总结

前言

什么是汉诺塔？

汉诺塔(Tower of Hanoi)（也称河内塔）是有法国数学家爱德华·卢卡斯于1883年发明的一道智力题。它源于印度的一个古老传说：大梵天创造世界的时候做了三根钻石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令一组牧师把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。据说牧师们夜以继日地工作，当他们完成任务时，那座塔就将坍塌，世界也将毁灭。

一、汉诺塔的图解

设有三个柱子，要把三个盘子从A柱移动到C柱，我们应如何解决呢？

先分步走，当盘子个数为1时，走一步，只需要把盘子从A柱直接挪到C柱（A--->C），如图所示：

当盘子个数为2时，要走三步，先把上面的盘子从A柱挪到B柱（A--->B），再把下面的盘子从A柱挪到C柱（A--->C），最后把B柱上的盘子挪到C柱（B--->C），如图所示：

当盘子个数为3时，要走七步，A--->C；A--->B；C--->B；A--->C；B--->A；B--->C；A--->C 如图所示：

经过上面的步骤，我们会发现移动盘子的次数是指数增长，要移动2^n-1次。

二、问题分析

经过上面的图解发现，设我们要移动n个盘子，当n=1时，只需要把盘子从A柱（起始位置）移到C柱（目的位置）；当n>1时，需要把A柱上n-1个盘子先借助C柱（目的位置）再移到B柱（中转位置）上，A柱上剩下的一个盘子直接移到C柱，再把B柱上n-1个盘子移到C柱上，从而完成n个盘子从A柱到C柱的移动。

首先实现能打印从起始位置到目的位置的过程的函数：

void move(char pos1, char pos2)
{
	printf("%c->%c\n", pos1, pos2);
}

实现汉诺塔函数：

我们可以表示为3个步骤：
1. 将n-1个盘子由A 移到 B；

2.将第n个盘子由 A移到 C；

3.将n-1个盘子由B 移到 C；

n：代表盘子的个数；pos1：起始位置；pos2：中转位置；pos3：目的位置

//        盘子个数   起始      中转       目的
void hanio(int n, char pos1, char pos2, char pos3)
{
	if (n == 1)
	{
		move(pos1, pos3);//移动过程
	}
	else//大化小的过程
	{
		hanio(n - 1, pos1, pos3, pos2);
		move(pos1, pos3);
		hanio(n - 1, pos2, pos1, pos3);
	}
}

实现完整的代码：

#include <stdio.h>

void move(char pos1, char pos2)
{
	printf("%c->%c\n", pos1, pos2);
}

//        盘子个数   起始      中转       目的
void Hanio(int n, char pos1, char pos2, char pos3)
{
	if (n == 1)
	{
		move(pos1, pos3);//移动过程
	}
	else
	{
		Hanio(n - 1, pos1, pos3, pos2);//从起始位置到中转位置再到目的位置
		move(pos1, pos3);
		Hanio(n - 1, pos2, pos1, pos3);
	}
}

int main()
{


	int n = 0;
	char A = 'A';
	char B = 'B';
	char C = 'C';
	printf("请输入要移动盘子的个数>:\n");
	scanf("%d", &n);
	Hanio(n, A, B, C);
	return 0;
}

运行结果：