【算法设计与分析】第二章递推算法

﹏ヽ暗。殇╰゛Y 2023-07-13 03:13 1阅读 0赞

## 递推 ##

一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。

eg：【例1】数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70]  
　 1、 一步可沿左斜线向下或右斜线向下走；  
　 2、 三角形行数小于等于100；  
3、 三角形中的数字为0，1，…，99；  
测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：

5
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5

【算法分析】  
　　此题解法有多种，从递推的思想出发，设想，当从顶层沿某条路径走到第i层向第i+1层前进时，我们的选择一定是沿其下两条可行路径中最大数字的方向前进，为此，我们可以采用倒推的手法，设a\[i\]\[j\]存放从i,j 出发到达n层的最大值，则a\[i\]\[j\]=max\{a\[i\]\[j\]+a\[i+1\]\[j\]，a\[i\]\[j\]+a\[i+1\]\[j+1\]\}，a\[1\]\[1\] 即为所求的数字总和的最大值。

【代码】

#include<bits/stdc++.h>
    using namespace std;
    
    int n;
    int a[1000][1000];
    
    int main()
    { 
        cin>>n;
        for(int i=1;i<=n;i++)
        { 
            for(int j=1;j<=i;j++)
            { 
                cin>>a[i][j];
            }
        }
        for(int i=n-1;i>=1;i--)
        { 
            for(int j=1;j<=i;j++)
            { 
                a[i][j]=max(a[i+1][j],a[i+1][j+1]);
            }
        }
        cout<<a[1][1]<<endl;
        return 0;
    }

## 序列求和的方法 ##

**等差数列：**  
 S n = n ∗ ( a 1 + a n ) / 2 S\_n=n\*(a\_1+a\_n)/2 Sn=n∗(a1\+an)/2  
**等比数列：**  
 S n = a 1 ∗ ( 1 − q n ) / ( 1 − q ) ; ( q ! = 1 ) S\_n=a\_1\*(1-q\_n)/(1-q);(q!=1) Sn=a1∗(1−qn)/(1−q);(q!=1)  
 S n = n ∗ a 1 ; ( q = = 1 ) S\_n=n\*a\_1;(q==1) Sn=n∗a1;(q==1)

**调和级数:**  
 ∑ k = 1 n ( 1 / k ) = l n n + O ( 1 ) \\sum\_\{k=1\}^\{n\} (1/k)=lnn+O(1) ∑k=1n(1/k)=lnn\+O(1)

## 递推方程 ##

设序列 a 0 a\_0 a0, a 1 a\_1 a1,…, a n a\_n an,…简记为 a n \{a\_n\} an，一个把 a n a\_n an与某些个 a i a\_i ai联系起来的等式叫做冠以 a n \{a\_n\} an的递推方程。  
**求解**：  
给定关于序列 a n \{a\_n\} an的递推方程和若干初值，计算 a n a\_n an

eg:Fibonacci数列： 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …  
初值： f 0 = 1 f\_0=1 f0=1 ,  f 1 = 1 f\_1=1 f1=1  
递推方程：  f n = f n − 1 + f n − 2 f\_n=f\_\{n-1\}+f\_\{n-2\} fn=fn−1\+fn−2

## 迭代法求解递推方程 ##

**迭代法**

*  不断用递推方程的右部替换左部
 *  每次替换，随着 n 的降低在和式中多出一项
 *  直到出现初值停止迭代
 *  将初值代入并对和式求和
 *  可用数学归纳法验证解的正确性

**换元迭代**

*  将对 n 的递推式换成对其他变元k的递推式
 *  对 k 直接迭代
 *  将解 (关于 k 的函数) 转换成关于n 的函数

## 差消法化简高阶递推方程 ##

根据已知，写出递推方程，并且写出递推方程的下一项，，讲两个递推方程做差，然后化简即可。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200309201520760.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA==,size_16,color_FFFFFF,t_70