服务器之家

服务器之家 > 正文

C语言实现汉诺塔(图文详解)

时间:2021-12-15 14:17     来源/作者:流浪孤儿

汉诺塔的游戏规则:

有三根金刚石柱子A、B、C,在A柱子上从下往上按照大小依次减小的顺序摞着64片黄金环。大梵天命令婆罗门把环从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在任何一个柱子上,小环上不能放大环,在三根柱子之间一次只能移动一个环。

即将A柱子上全部的环通过中间柱子B(B柱子作为中介)移动到C柱子上

当A只有一个环的时候:

A->C

C语言实现汉诺塔(图文详解)

当A只有两个环的时候:

A->B A->C B->C

C语言实现汉诺塔(图文详解)

当A只有三个环的时候:

A->C A->B C->B A->C B->A B->C A->C

C语言实现汉诺塔(图文详解)

 

思路:

1、将 n-1个环先放到B柱子上
2、将A柱子上的最后一个环移动到C柱子上
3、将n-1个环从B柱子移动到C柱子上

当n=1时:

1、将0个环先放到B柱子上

2、将A柱子上的最后一个环移动到C柱子上:A->C

3、将0个环从B柱子移动到C柱子上

当n=2时:

1、将1个环先放到B柱子上:A->B

2、将A柱子上的最后一个环移动到C柱子上:A->C

3、将1个环从B柱子移动到C柱子上:B->C

当n=3时:

1、将2个环先放到B柱子上:使用递归将2个环放到B上,因为A柱子的最后一个环是最大的因此可以先不理会,递归重复当n=2时的步骤,不过是从将2个环从A放到C上改为将2个环从A放到B上了

2、将A柱子上的最后一个环移动到C柱子上:A->C

3、将2个环从B柱子移动到C柱子上:使用递归将2个环从B柱子移动到C柱子上,此时C柱子上已经有了最大的一个环因此可以不用再理会了,递归重复当n=2的步骤,不过是从将2个环从A放到C上改为将2个环从B放到C上了

当n=4时:

1、将3个环先放到B柱子上:递归重复n=3的步骤,不过是从将3个环从A放到C上改为将3个环从A放到B上了

2、将A柱子上的最后一个环移动到C柱子上:A->C

3、将3个环从B柱子移动到C柱子上:递归重复当n=3的步骤,不过是从将3个环从A放到C上改为将3个环从B放到C上了

 

见代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void move(char X, char Y)
{
	printf("%c->%c ", X, Y);
}

void HanoiTower(int n, char A, char B, char C)
{
	if (n == 1)//递归终止条件
	{
		move(A, C);
		return;
	}
		
	else
	{
		HanoiTower(n - 1, A, C, B);//将n-1个环从A柱子放到B柱子上,C柱子作为中介
		move(A, C);//将A柱子上的最后一个环移动到C柱子上
		HanoiTower(n - 1, B, A, C);//将n-1个环从B柱子放到C柱子上,A柱子作为中介
	}
}


int main()
{
	printf("请确认A柱子上一共有多少个环:\n");
	int n = 0;
	scanf("%d", &n);
	HanoiTower(n, 'A','B','C');//将n个环从A柱子放到C柱子上,B柱子作为中介
}

 

运行截图

C语言实现汉诺塔(图文详解)

C语言实现汉诺塔(图文详解)

C语言实现汉诺塔(图文详解)

 

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注服务器之家的更多内容!

原文链接:https://blog.csdn.net/qq_42591783/article/details/119515127

标签:

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部