汉诺塔？爬楼梯?斐波那契?知道递归就够了

你的名字 2023-09-24 23:00 38阅读 0赞

*有远大志向而脚踏实地，有障碍失败而不言放弃，这样坚持下去，不会成功也会获益无穷——方海权*

### 文章目录 ###

*  导读
 *  递归
 *   *  递推
     *  回归
 *  问题一般形式
 *  爬楼梯问题：
 *  汉诺塔问题

# 导读 #

**我们在利用编程解决实际问题时总会遇到这样一种问题，即分解后的子问题与原问题类似，能用原来的方法解决问题，且最终的子问题是已知解或易于解，通常我们可以使用一种特殊的解决问题的方法——递归**

# 递归 #

其基本思想是：**将要解决的问题分解成比原问题规模小的子问题，当解决这个子问题时，又可以用到原问题的解决方法，按照这个原则逐步递推，最终将原问题转换成较小且已知的解的子问题。  
递归一般分为两个阶段：**

## 递推 ##

将**原问题不断地转化成子问题**， 逐渐从未知向己知推进， 最终到达已知解的问题，即递推阶段结束。

## 回归 ##

从**已知解的问题**出发，按照递推的逆过程，逐一求值回归， 最后到达递归的开始处，即结束回归阶段，获得问题的解。

# 问题一般形式 #

诺可将求解问题逐步转化成与原问题类似的子问题，且最终子问题有明确的解，则可采用递归函数，实现问题的求解。  
*注：由于在递归函数中存在着调用自身的过程，因此要控制反复进入自身的函数体调用，必须在函数体中设置终止条件，当条件成立时，终止调用自身，并使控制逐步返回到主调函数。*

# 爬楼梯问题： #

**假设你正在爬楼梯。需要 n 阶你才能到达楼顶。  
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。  
解释：有两种⽅法可以爬到楼顶。  
输⼊：n = 2  
输出：2  
第⼀种：1 阶 + 1 阶  
第⼆种： 2 阶**  
题解：这是一道非常经典的例题，通过分析我们不难发现一个这样的规律，当我们第一步只爬一个台阶剩下的n-1个台阶有它的爬法个数，当我们第一步爬两个台阶剩下的n-2个台阶就有它的爬法。以此类推最终我们就可以得到这样一个函数关系式：  
![在这里插入图片描述][a464a94b6760453e9d7f51b27fc8a663.png]  
这明显符合我们递归问题，因此我们可以写出代码：

#include<stdio.h>
    int Class(int n) {
        
    	int i = 0;
    	if (n == 1)
    		return 1;
    	if (n == 2)
    		return 2;
    	return Class(n - 1) + Class(n - 2);
    }
    int main()
    {
        
    	int n = 0;
    	scanf("%d", &n);
    	printf("%d", Class(n));
    }

在我们运算过程中我们会发现总有那么几个数我们需要重复计算，大大的增加了我们的运算量，这里我们可以创造一张记忆表去记录我们已有的n：

#include<stdio.h>
    int a[100] = {
         0 };//创造记忆体
    int b = 0;
    int Class(int n)
    {
        
    	int i = 0;
    	if (n == 1)
    		return 1;
    	if (n == 2)
    		return 2;
    	while (i <= b)
    	{
        
    		if (n == a[i])
    			return a[i];
    	}//判断楼梯阶数是否在记忆体中保留过
    	int c =	Class(n - 1) + Class(n - 2);
    	a[b] = c;
    	return c;
    }
    int main()
    {
        
    	int n;
    	scanf("%d", &n);
    	printf("需要爬%d", Class(n));
    }```
    当然这道题我们同样也可以使用一般循环的解法：
    
    ```c
    #include<stdio.h>
    int Class(int n)
    {
        
    	if (n == 1)
    		return 1;
    	if (n == 2)
    		return 2;
    	int c = 0;
    	int i = 0;
    	int pre = 2;
    	int prepor = 1;
    	for (i = 3;i <= n;i++)
    	{
        
    		c = pre + prepor;
    		prepor = pre;
    		pre = c;
    	}
    	return c;
    }
    int main()
    {
        
    	int n = 0;
    	scanf("%d", &n);
    	printf("需要爬%d", Class(n));
    }

# 汉诺塔问题 #

**古代有一个梵塔，塔内有3个座A、B、C,开始时A座上有64个盘子，盘子大小不等，大的在下，小的在上，有一个老和尚想把这64个盘子从A座移到C座，但每次只允许移动一个盘，且移动过程中在3个座上都始终保持大盘在下、小盘在上的状态。在移动过程中可以利用B座，要求编写程序并打印出移动的步骤。**  
题解：将n个盘子从A座移到C座可以分解为以下三个步骤:

1.  将A座上n-1个盘子借助C座先移到B座上。
2.  将A座上剩下的一个盘子移到C座上。
3.  将n-1个盘子从B座借助A座移到C座上。  
    如果想将A座上3个盘子移到C座上，可以分解为以下三个步骤:
4.  将A座上2个盘子借助C座移到B座上
5.  将A座上1个盘子移到C座上;
6.  将B座上2个盘子借助A座移到C座上。  
    其中第(2)步可以直接实现。第(1)步又可用递归方法分解为:
7.  将A座上1个盘子从A座移到C座
8.  将A座上1个盘子从A座移到B座
9.  将C座上1个盘子从C座移到B座
10. 将B座上1个盘子从B座移到A座上
11. 将B座上1个盘子从B座移到C座上
12. 将A座上1个盘子从A座移到C座上。  
    综合以上情况，可得到移动3个盘子的步骤为:  
    A→C, A→B，C→B，A→C，B→A，B→C，A→C  
    ![在这里插入图片描述][f48c908d779b4fc3b9a000465fe8fa0b.gif_pic_center]  
    代码如下：

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

运行结果如下：  
![在这里插入图片描述][4ab9d1374fae4572ae6852e0adebdbe2.png]

最后的话 ：如果大家觉得这篇文章对你们有帮助的话希望你们能够点点关注，你们的关注是我继续写下去的动力，谢谢大家。  
![在这里插入图片描述][142449b56d794acb82a8748c64177aba.gif_pic_center]

（文章中图片与部分内容来源与网络，如有侵权请联系删除）

[a464a94b6760453e9d7f51b27fc8a663.png]: https://img-blog.csdnimg.cn/a464a94b6760453e9d7f51b27fc8a663.png
[f48c908d779b4fc3b9a000465fe8fa0b.gif_pic_center]: https://img-blog.csdnimg.cn/f48c908d779b4fc3b9a000465fe8fa0b.gif#pic_center
[4ab9d1374fae4572ae6852e0adebdbe2.png]: https://img-blog.csdnimg.cn/4ab9d1374fae4572ae6852e0adebdbe2.png
[142449b56d794acb82a8748c64177aba.gif_pic_center]: https://img-blog.csdnimg.cn/142449b56d794acb82a8748c64177aba.gif#pic_center