算法基础之递推

绝地灬酷狼 2022-09-08 00:19 168阅读 0赞

### 算法基础之递推（C++示例） ###

所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。

从已知条件出发逐步推到问题结果，此种方法叫顺推。

从问题出发逐步推到已知条件，此种方法叫逆推。

无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。

递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。

递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。

递推算法是一种理性思维模式的代表，其根据已有的数据和关系，逐步推导而得到结果。递推算法的

执行过程如下:

(1)根据已知结果和关系，求解中间结果。

(2)判定是否达到要求，如果没有达到，则继续根据已知结果和关系求解中间结果。如果满足要求，则表示寻找到一个正确的答案。

递推与递归的区别

比如阶乘函数：f(n)=n\*f(n-1)

在f(3)的运算过程中,递归的数据流动过程如下:

f(3)\{f(i)=f(i-1)\*i\}-->f(2)-->f(1)-->f(0)\{f(0)=1\}-->f(1)-->f(2)--f(3)\{f(3)=6\}

而递推如下:

f(0)-->f(1)-->f(2)-->f(3)

相对于递归算法,递推算法免除了数据进出栈的过程，递推的效率要高一些,在可能的情况下应尽量使用递推.但是递归作为比较基础的算法,它的作用不能忽视。

**例1、**斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。

13世纪意大利数学家斐波那契的《算盘书》中记载了典型的兔子产仔问题，其大意如下：

如果一对一个月大的兔子以后每一个月都可以生一对小兔子，而一对新生的兔子出生两个月才可以生出小兔子。也就是，1月份出生，3月份开始产仔。那么假定一年内没有产生兔子死亡事件，那么1年之后共有多少对兔子呢？

分析

第一个月：1对兔子；

第二个月：1对兔子；

第三个月：2对兔子；

第四个月：3对兔子；

第五个月：5对兔子；

第六个月：8对兔子；

……

从中可以看出，从第三个月开始，每个月的兔子总对数等于前两个月兔子数的总和。相应的计算公式如下：

第n个月兔子总数Fn=Fn-1+Fn-2。

这里初始第一个月的兔子数F1=1，第二个月的兔子数F2=1。

源码如下：

//请留意递归算法和递推算法对比
    #include<iostream>
    using namespace std;
    
    //递归算法求解
    int Fib(int n){
    	if(n==1 || n==2)
    		return 1;
    	else
    		return (Fib(n-1)+Fib(n-2));
    }
    
    //递推算法求解
    int Fib2(int n){
    	int a=1,b=1,c;
    	for(int i=1;i<=n;i++){
    		if(i<=2)
    			c=1;
    		else{
    			c=a+b;
    			a=b;
    			b=c;
    		}
    	}
    	return c;
    }
    
    int main()
    {
    	int n;
    	cout<<"请输入时间（月数）：";
    	cin>>n;
    	cout<<"经过"<<n<<"个月之后"<<endl;
    	cout<<"兔子的数量为（递归算法）："<<Fib(n)<<"对"<<endl;
    	cout<<"兔子的数量为（递推算法）："<<Fib2(n)<<"对"<<endl;
    	return 0; 
    }

运行之结果如下：

请输入时间（月数）：12  
经过12个月之后  
兔子的数量为（递归算法）：144对  
兔子的数量为（递推算法）：144对

**例2、**猴子吃桃

猴子摘了一堆桃子，第一天吃了总数一半多一个，第二天吃了剩余桃子的一半多一个.......直到第十天，他发现只剩1个桃子，问他开始摘了几个桃子?

分析：

逆推法是根据结果推出已知条件，推算方法与顺推法类似，只是需要将结果作为初始条件向前推算。

根据第10天的桃子个数往前推算（逆推）：

第10天只剩1个桃子；

第九天吃了桃子的一半零一个，假设第9天吃之前的桃子个数为x，则有x-(x/2+1)=1，即x=2×(1+1)。其中第一个1表示第10天的桃子个数。接着往前推算；

假设第八天吃桃子之前有x个，第九天吃桃子前有y个（第九天的桃子个数可以由第10天的桃子个数推算

得到），则有x-(x/2+1)=y，即y=2×(y+1)。依此类推，可以得到第1天的桃子个数。

源码如下：

#include<iostream>
    using namespace std;
     
    int fun(int n)//逆推算法，n代表天数
    {
        int i, number=1;
    	for(i=1;i<=n-1;i++)
    	{
    		number=(number+1)*2;
    	}
    	return number;
    }
     
    int main()
    {
        cout<<"开始摘的桃子："<<fun(10)<<"个"<<endl;
    
        return 0;
    }

运行之结果如下：

开始摘的桃子：1534个

**例3、**从原点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？

【[https://cloud.tencent.com/developer/article/1066810?from=14588][https_cloud.tencent.com_developer_article_1066810_from_14588] 】

解题思路：要解决走N步共有多少种走法，我们在拿到题目的时候最直接的想法就是先画出当N=1、N=2、N=3。。。。。N=n时对应走法的图例，由简单到复杂、由特殊到一般的推理过程，找出规律获得解题的思路。

（1）当N=1时，绘出走法图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA6L2v5Lu25oqA5pyv5a2m5Lmg5byA5Y-R54ix5aW96ICF_size_4_color_FFFFFF_t_70_g_se_x_16][]

共有3种不同的走法，也就是黑色线条的数量，即f(1)=3

（2）当N=2时，绘出走法图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA6L2v5Lu25oqA5pyv5a2m5Lmg5byA5Y-R54ix5aW96ICF_size_7_color_FFFFFF_t_70_g_se_x_16][]

共有7种不同的走法，也就是绿色线条的数量，即f(2)=7

（3）当N=3时，绘出走法图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA6L2v5Lu25oqA5pyv5a2m5Lmg5byA5Y-R54ix5aW96ICF_size_14_color_FFFFFF_t_70_g_se_x_16][]

共有17种不同的走法，也就是红色线条的数量，即f(3)=17

由此看出，对于任何一个起点，最多可以走出3种走法，但最少必须走出2种走法。那么我们要求出f(n)，实际上转换为如果我们能够得到上一步即f（n-1）有多少个终点是有3种走法的，有多少个点有2种走法的，那么问题就解决了。

a.上一步，即f（n-1）有多少个终点是有3种走法的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA6L2v5Lu25oqA5pyv5a2m5Lmg5byA5Y-R54ix5aW96ICF_size_15_color_FFFFFF_t_70_g_se_x_16][]

对于N=3时，f(n-1)=f(2), 有3个点A、B、C可以走出3种不同走法的，这3个点是怎么得到的呢？它的存在与N值有没有必然的联系？如果我们能找到它与N之间的关系，问题也就解决了。有了这样的思路以后，我们不难找到这样的规律：如果f（n-2）存在，即上上步存在，那么从上上步出发的线路里面必然会有一条向上走的线路，而这条向上走的线路在到达f（n-1）之后，  向f（n）出发时也必然有左、上、右这三种走法，那么我们就得出了这样的结论：当f（n-2）存在时，f（n-2）的值实际上就等价于f（n-1）有多少个终点是有3种走法。

b.f（n-1）有多少个终点是有2种走法的

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA6L2v5Lu25oqA5pyv5a2m5Lmg5byA5Y-R54ix5aW96ICF_size_15_color_FFFFFF_t_70_g_se_x_16 1][]

对于N=3时，有4个点D、E、F、G可以走出2种不同走法的，这4个点又是怎么得到的呢？它与N值有什么联系呢？ 实际上我们在解决了上一个问题的时候，这个问题就变得相当容易了， f（n-1）减掉刚才有3种走法的点，剩下的点不就是只有2种走法了吗？即f（n-1）-f（n-2）。

c. 得出f（n）的一般关系式

f(n)=3\*f(n-2)+2\*(f(n-1)-f(n-2) ) (n>=3)

化简：

f(n)=2\*f(n-1)+f(n-2) (n>=3)

任何递推题，都会有临界条件。当N=1时，f(n)=3;,当N=2时，f(n)=7,这些都可以看成是临界条件。只有当N>=3时，即上上步存在的情况下，就可以得出f(n)的一般通式：f(n)=2\*f(n-1)+f(n-2)

源码如下：

#include <stdio.h>   
    #include <windows.h>    
    int main()    
    {    
       int n;    
       int i;    
       int fn_1,fn_2;    
       printf("please input n=");    
       scanf("%d",&n); //输入任意n值    
       int fn=0;    
       if(n==1)    
         fn=3; //初始化当n=1和n=2时的临界条件    
       else if(n==2)    
         fn=7;    
       else{    
         fn_1=7;    
         fn_2=3;    
         for(i=3;i<=n;i++)    
         {    
            fn=2*fn_1+fn_2; //当n>=3时fn的通式    
            fn_2=fn_1;//更新fn_1和fn_2的值    
            fn_1=fn;    
         }    
       }    
       printf("一共有%d种走法！\n",fn);  //输出结果    
       return 0;    
    }

运行之结果如下：

please input n=5  
一共有99种走法！

[https_cloud.tencent.com_developer_article_1066810_from_14588]: https://cloud.tencent.com/developer/article/1066810?from=14588
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA6L2v5Lu25oqA5pyv5a2m5Lmg5byA5Y-R54ix5aW96ICF_size_4_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/4a6f162604fd4e96be26934a051915ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA6L2v5Lu25oqA5pyv5a2m5Lmg5byA5Y-R54ix5aW96ICF_size_7_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/dad92730ad7149909c7a16465cf7bb8b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA6L2v5Lu25oqA5pyv5a2m5Lmg5byA5Y-R54ix5aW96ICF_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/90651ddb669f40b5a9d914a2da3924e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA6L2v5Lu25oqA5pyv5a2m5Lmg5byA5Y-R54ix5aW96ICF_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/8a42efeffac04bc6b7c9a46629068be8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA6L2v5Lu25oqA5pyv5a2m5Lmg5byA5Y-R54ix5aW96ICF_size_15_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/6049fc53c93d486aaedf5f7503e8152f.png