C语言实现汉诺塔【图文讲解】
本期介绍🍖
主要介绍:汉诺塔是什么,汉诺塔的规律,如何用C语言来实现汉诺塔👀。
目录
什么是汉诺塔
汉诺塔(Tower of Hanoi),又称河内塔。源自印度古老传说的一个游戏,大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
若每次移动需要1s的时间,那么请问婆罗门需要多久才能把这64片黄金圆盘从一根石柱上移动到另一个石柱上?
若只有1个圆盘时,需要移动1次;若有2个圆盘时,需要移动3次;若有3个圆盘时,需要移动7次……不难看出,汉诺塔步数的数学规律为2的n次方减1(n为柱子上的圆盘个数)。所以若有64个圆盘那将会移动2^64-1次(即:18,446,744,073,709,551,615次),若每次移动需要1s时间,则需要将近5849亿年的时间才能够做到。可见大梵天有多恨婆罗门,这绝对是在坑人啊!!!
如何用C语言实现汉诺塔
现有三个柱子A、B、C,其中有n个圆盘在A柱上,最终要实现把这n个圆盘从A柱借助B柱移动到C柱上。实现实现思路:先将n-1个圆盘从A柱移动到B柱上,然后将A柱上最后一个圆盘移动到C柱上,最后再把B柱上的n-1个圆盘移动到C柱上。如下图所示:
当n=1时:
1.将A柱上最后一个圆盘移动到C柱上(A →C)
当n=2时:
1.将1个圆盘从A柱移动到B柱上,重复n=1时的步骤,只不过是将那1个圆盘(从A借助于B移动到C)改为(从A借助于C移动到B)
2.将A柱上最后一个圆盘移动到C柱上(A →C)
3.将B柱上的1个圆盘移动到C柱上。重复n=1时的步骤,只不过是将那个圆盘(从A借助于B移动到C)改为(从B借助于A移动到C)
当n=3时:
1.将2个圆盘从A柱移动到B柱上。重复n=2时的步骤,只不过是将那2个圆盘(从A借助于B移动到C)改为(从A借助于C移动到B)
2.将A柱上最后一个圆盘移动到C柱上(A →C)
3.将B柱上的2个圆盘移动到C柱上。重复n=2时的步骤,只不过是将那2个圆盘(从A借助于B移动到C)改为(从B借助于A移动到C)
当n=4时:
1.将3个圆盘从A柱移动到B柱上。重复n=3时的步骤,只不过是将那3个圆盘(从A借助于B移动到C)改为(从A借助于C移动到B)
2.将A柱上最后一个圆盘移动到C柱上(A →C)
3.将B柱上的3个圆盘移动到C柱上。重复n=3时的步骤,只不过是将那3个圆盘(从A借助于B移动到C)改为(从B借助于A移动到C)
以此类推,当汉诺塔上的圆盘数为n个时该如何移动,只需要按照上面的规律一直往上递归,最终是可以达到目的的。程序如下:
#include<stdio.h>
void move(char A, char C, int n)
{
printf("把第%d个圆盘从%c--->%c
", n, A, C);
}
void HanoiTower(char A, char B, char C, int n)
{
if (n == 1)
{
move(A, C, n);
}
else
{
//将n-1个圆盘从A柱借助于C柱移动到B柱上
HanoiTower(A, C, B, n - 1);
//将A柱子最后一个圆盘移动到C柱上
move(A, C, n);
//将n-1个圆盘从B柱借助于A柱移动到C柱上
HanoiTower(B, A, C, n - 1);
}
}
int main()
{
int n = 0;
printf("输入A柱子上的圆盘个数:");
scanf("%d", &n);
//将n个圆盘从A柱借助于B柱移动到C柱上
HanoiTower('A', 'B', 'C', n);
return 0;
}
若想知道一共移动了多少次圆盘,只需要在move()函数中加一个全局变量来统计个数就行。
这份博客👍如果对你有帮助,给博主一个免费的点赞以示鼓励欢迎各位🔎点赞👍评论收藏⭐️,谢谢!!!
如果有什么疑问或不同的见解,欢迎评论区留言欧👀。
相关文章
- 突破 100 种,微软翻译新增对 12 种语言/方言支持,包括藏语、维吾尔语...
- 破解Windows 11的TPM及4GB内存限制 U盘神器Rufus 3.16 Beta2发布
- Google Chrome正在清理使用率低下的标签页堆叠功能
- Rufus现可让用户为不满足系统需求的PC创建Windows 11安装介质
- 如何在 Linux 上安装Samba
- 微软重申Windows 11硬件要求严格是为了安全性:多数5年内的电脑都支持
- 升级了 Windows 11 正式版,有坑吗?
- 玩转Vim自带的文件浏览器Netrw,看这个就够了
- 微软承认!Windows 11系统存在问题
- 微软亲自演示黑客入侵,告诉你 Windows 11 的 TPM 2.0 有多重要
- Windows 10电脑卡顿,一定要设置这五项!老电脑也能提速十倍
- Windows操作系统10定时关机教程
- 升级Windows 11遭遇蓝屏死机?可能是你用了中文
- 从Windows 10升级到Windows 11的快捷方法
- 基于 KDE 的优秀的 Linux 发行版
- 广大应用程序开发者正努力支持Windows 11的新右键上下文菜单
- 微软为Windows 11 Linux子系统带来了一些新特性
- 谷歌 Chrome Canary 浏览器安卓版正在测试全新页面缩放:还支持记忆功能
- Goroutine 存在的意义是什么?
- Linux 终端初始化 console_init 及 tty 驱动框架