C语言 - 汉诺塔详解(超详细)

C语言 – 汉诺塔详解(超详细)

全栈程序员-站长 • 2026年3月19日下午11:30 • 未分类 • 阅读 2

文章目录

一、前言
二、玩游戏
三、汉诺塔打印步数
四、汉诺塔打印步骤

一、前言

一、汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

在这里插入图片描述
A B C

二、玩游戏

三、汉诺塔打印步数

目的：不使用递归计算1个n层的汉诺塔从A柱到C柱的所有步数
原理：如下
平台：Visual studio 2017 && windows
*/

塔数	步数	规律
1	1	2^1 – 1
2	3	2^2 – 1
3	7	2^3 – 1
4	15	2^ 4 – 1
5	31	2^5 – 1
…	…	2^n – 1

实现代码：

#define _CRT_SECURE_NO_WARNINGS #include 
     #include 
     int main() { 
    int num = 0; scanf("%d", &num);//塔数 printf("完成%d层的汉诺塔需要%d步\n", num, (int)pow(2,num) - 1); return 0; }

目的：使用递归计算1个n层的汉诺塔从A柱到C柱的所有步数
原理：
1.将n-1个碟子从A杆经C杆移动到B杆
2.将A杆上的第n个碟子移动到C杆
3.将n-1个碟子从B杆经A杆移动到C杆

所以: f (n -1 ) + 1 + f (n – 1); -> 2 * f (n – 1) +1; 这个式子叫做递推式
平台：Visual studio 2017 && windows
*/

实现代码：

#define _CRT_SECURE_NO_WARNINGS #include 
     int Hanio_twice(int num) { 
    if(1 == num) return 1; else return 2 * Hanio_twice(num - 1) + 1; } int main() { 
    int num = 0; scanf("%d", &num);//塔数 int ret = Hanio_twice(num); printf("完成%d层的汉诺塔需要%d步\n", num, ret); return 0; }

步数	规律
1	2 ^ 1 – 1
3	2 ^ 2 – 1
7	2 ^ 3 – 1
…	…
64	2 ^ 64 – 1

四、汉诺塔打印步骤

目的：使用递归打印1个n层的汉诺塔从A柱到C柱的所有步骤
原理：封装1个函数Hanio(num, ‘A’, ‘B’, ‘C’)。
其中num是塔数；A、B、C，3个字符为抽象成的3个柱子。
如果只有1层那么输出A；
否则就有2种情况，其1是将n-1个碟子从A经C到B。其2是将n-1个碟子从B经A到C
平台：Visual studio 2017 && windows
*/

塔数	步骤
1	A->C
2	A->B、A->C、B->C
3	A->C、A->B、C->B、A->C、B->A、B->C、A->C
4	A->B，A->C，B->C，A->B，C->A，C->B，A->B，A->C，B->C，B->A，C->A，B->C，A->B，A->C，B->C
…	…
偶	A->B
奇	A->C

实现代码：

#define _CRT_SECURE_NO_WARNINGS #include 
     void Hanio_Step(int n, char A, char B, char C) { 
    if (1 == n) printf("%c->%c\n", A, C); else { 
    Hanio_Step(n-1, A, C, B); printf("%c->%c", A, C); Hanio_Step(n-1, B, A, C); } } int main() { 
    int n = 0; scanf("%d", &n); Hanio_Step(n, 'A', 'B', 'C'); return 0; }

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/202703.html原文链接：https://javaforall.net

C语言 – 汉诺塔详解(超详细)

文章目录

一、前言

二、玩游戏

三、汉诺塔打印步数

四、汉诺塔打印步骤

关于作者

全栈程序员-站长

发表回复

C语言 – 汉诺塔详解(超详细)

文章目录

一、前言

二、玩游戏

三、汉诺塔打印步数

四、汉诺塔打印步骤

关于作者

全栈程序员-站长

相关推荐

Void – 开源 Cursor 替代品，让 AI 帮你创建文件、写代码[Win／macOS]

代理服务器和反向代理服务器详解

RC有源滤波器之带通滤波器（四）

oracle 的dba users表,oracle DBA 常用表和视图

windows启动mongo服务_启动windows

即梦AI海外版（Dreamina ai）推出新模型Seedream3.0，英文排版效果惊艳！

发表回复