刻意练习-递归解决汉诺塔问题_汉诺塔5层完整步骤程序设计-CSDN博客

本文链接：https://blog.csdn.net/renyongjian1994/article/details/118247013

本文介绍了递归的基本概念及如何运用递归来解决汉诺塔问题。通过详细解析汉诺塔问题的解决步骤，展示了递归算法的设计思路，并提供了完整的C语言实现代码。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

一、递归和汉诺塔

递归是要先找到解决问题的步骤，从第1步做什么，第2步做什么，一直推断到N-1步做什么，第N步做什么。
然后把注意力放在第N-1步和第N步之间。并且假设N-1步已经解决OK了。

比如求和1-100.如果使用递归来完成。

int sum(int max_num)
{
    //如果这个数值是0，就直接返回0.
    if(max_num == 0)
    {
        return 0;
    }
    //假设之前的求和已经OK了。我用当前值加上之前的和就行。
    return max_num+sum(max_num-1);
}

int main()
{
    int sum_result = sum(100);
    return 0;
}

推理好步骤之后，需要确认停止的条件。如果没有停止的条件，就是无限自我调用，最终会用尽栈区资源。
汉诺塔的解决步骤，正好满足这个。
- 比如有两个盘子的情况。
- 然后这样移动
- 这里其实可以看出，当要移动较大的盘子2的时候，需要先把头顶上的较小的盘子1移动给第三者。
- 然后看看解决有三个盘子的情况。因为已经实现了两个盘子的移动，我们直接快进，把两个盘子的移动打包。
- 是同样的道理，要先把最大的盘子3头顶上的所有盘子移动给第三者。 然后把3放到B，最后把剩下的盘子从第三者移动到B。
- 因为移动两个盘子的操作已经在第一步中完成了，所以这里直接而假设两个盘子已经移动完成了。 也就是完成了N-1步了。把已经完成的内容看成一个整体。

二、抽象汉诺塔解决过程中的元素

抽象盘子

//用数字，比如，总共10个盘子，那就从1-10编号。

抽象棍子
```
//使用 A B C。三个字符
```

抽象移动某一个盘子

//传进去一个盘子的号，然后把它从 from 位置移动到 to 位置。
int move(int panzi_hao,char from,char  to);

抽象移动N个盘子

//把n 个盘子从from 移动到 to
int hn_solve(int panzi_shuliang,char from,char to);

三、实现

根据分析，我们要先把最底下盘子头顶上的盘子都先移动给第三者。所以要先计算出第三者。

//计算第三者的名字，比如 从A 移动到B，那么第三者就是C。从A移动到C，第三者就是B。
char get_tmp(char from,char to)
{
	return ('A'+'B'+'C' - from - to);
}

然后先把上面的n-1个盘子移动到第三者上。

char tmp = get_tmp(from,to);
//先把头顶上的东西都移动到第三者上。
hn_solve(hn_cnt-1,from,tmp);

然后假设头顶的盘子已经都移动完了，把最底下的盘子移动到目标to上。

//然后把最底下的那个大盘子移动到目标上。cnt就是编号最大的那个盘子。
move(hn_cnt,from,to);

最后把第三者头顶上的那么多盘子移动到目标

//然后把刚刚头顶上的东西从第三者移动到目标上
hn_solve(hn_cnt-1,tmp,to);

而具体怎么移动9个盘子，它会先移动前面的8个盘子，怎么移动8个？会自己调用自己先移动前面的7个盘子，直到没有盘子可以移动。
```
//停止条件，如果没有要移动的盘子了，直接返回。
if(hn_cnt == 0)
{
    return 0;
}
```

四、整理

完整代码

#include<stdio.h>

//把 hn_num 号盘子 从 from 位置 移动到 to 位置。
int move(int hn_num,char from,char to)
{
	printf("move %d from %c to %c\n",hn_num,from,to);
	return 0;
}

//计算第三者的名字，比如 从A 移动到B，那么第三者就是C。从A移动到C，第三者就是B。
char get_tmp(char from,char to)
{
	return ('A'+'B'+'C' - from - to);
}

//表示把hn_cnt个盘子从 from 的位置 移动到 to 位置。
int hn_solve(int hn_cnt,char from,char to)
{
    //停止条件，如果没有要移动的盘子了，直接返回。
	if(hn_cnt == 0)
	{
		return 0;
	}
    //获取第三者的名字
	char tmp = get_tmp(from,to);
    //先把头顶上的东西都移动到第三者上。
	hn_solve(hn_cnt-1,from,tmp);
    //然后把最底下的那个大盘子移动到目标上。
	move(hn_cnt,from,to);
    //然后把刚刚头顶上的东西从第三者移动到目标上
	hn_solve(hn_cnt-1,tmp,to);
    
	return 0;
}

int main()
{
    //把 10 个盘子 从 A 移动到 B.
	hn_solve(10,'A','B');
	return 0;
}

五、方法记忆

整理一下思路的关键。
先找到重复操作的最小单元，关注N和N-1之间的关系，假设N-1已经完成，最后加上终止条件。
递归解决问题的关键在于一个假设---------->假设 N-1已经被用同样的方法解决了。比如先序遍历一个二叉树。直接访问根节点，先假设左边的子树都被遍历了。然后假设右边的子树都被遍历了。
像数学归纳法。