1.算法设计与分析__递推算法

约定不等于承诺〃 2023-10-07 03:50 43阅读 0赞

### 递推算法 ###

递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。  
　　递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。  
　  
　　例题1——[数字三角形][Link 1]

【例2】满足F1=F2=1，Fn=Fn-1+Fn-2的数列称为斐波那契数列（Fibonacci），它的前若干项是1，1，2，3，5，8，13，21，34……求此数 列第n项（n>=3）。即：f1=1 （n=1） f2=1 （n=2） fn=fn-1 + fn-2 （n>=3）

程序如下：
    #include<iostream>
    #include<cstdio>
    using namespace std;
    int main()
    {
        int f0=1,f1=1,f2;
        int n;
        cin>>n;
     for (int i=3; i<=n; ++i)
        {
             f2=f0+f1;
             f0=f1;
             f1=f2;
        }
    printf("%d\n",f2);
    return 0;
    }

有关Fibonacci数列，我们先来考虑一个简单的问题：楼梯有n个台阶，上楼可以一步上一阶，也可以一步上两阶。一共有多少种上楼的方法？ 这是一道计数问题。在没有思路时，不妨试着找规律。n=5时，一共有8种方法：5=1+1+1+1+15=2+1+1+15=1+2+1+15=1+1+2+15=1+1+1+25=2+2+15=2+1+25=1+2+2 其中有5种方法第1步走了1阶(背景灰色)，3种方法第1步走了2阶，没有其他可能。假设f(n)为n个台阶的走法总数，把n个台阶的走法分成两类。 第1类：第1步走1阶，剩下还有n-1阶要走，有f(n-1)种方法。 第2类：第1步走2阶，剩下还有n-2阶要走，有f(n-2)种方法。 这样，就得到了递推式：f(n)=f(n-1)+f(n-2),不要忘记边界情况：f(1)=1,f(2)=2。把f(n)的前几项列出：1，2，3，5，8，……。 再例如，把雌雄各一的一对新兔子放入养殖场中。每只雌兔在出生两个月以后，每月产雌雄各一的一对新兔子。试问第n个月后养殖场中共有多少对兔子。  
还是先找找规律。 第1个月：一对新兔子r1。用小写字母表示新兔子。 第2个月：还是一对新兔子，不过已经长大，具备生育能力了，用大写字母R1表示。 第3个月：R1生了一对新兔子r2，一共2对。 第4个月：R1又生一对新兔子r3，一共3对。另外，r2长大了，变成R2 第5个月：R1和R2各生一对，记为r4和r5，共5对。此外，r3长成R3。 第6个月：R1、R2和R3各生一对，记为r6～r8，共8对。此外，r4和r5长大。 …… 把这些数排列起来：1，1，2，3，5，8，……，事实上，可以直接推导出来递推关系f(n)=f(n-1)+f(n-2):第n个月的兔子由两部分组成，一部分是上个月就有的老兔子f(n-1)，一部分是上个月出生的新兔子f(n-2)(第n-1个月时具有生育能力的兔子数就等于第n-2个月兔子总数)。根据加法原理，f(n)=f(n-1)+f(n-2)。

【例3】 有 2χn的一个长方形方格，用一个1*2的骨牌铺满方格。  
![在这里插入图片描述][20200313213048431.png]  
　　编写一个程序，试对给出的任意一个n(n>0), 输出铺法总数。  
【算法分析】  
　（1）面对上述问题，如果思考方法不恰当，要想获得问题的解答是相当困难的。可以用递推方法归纳出问题解的一般规律。  
　（2）当n=1时，只能是一种铺法，铺法总数有示为x1=1。  
　（3）当n=2时：骨牌可以两个并列竖排，也可以并列横排，再无其他方法，如下左图所示，因此，铺法总数表示为x2=2； ![在这里插入图片描述][2020031321310315.png]  
　（4）当n=3时：骨牌可以全部竖排，也可以认为在方格中已经有一个竖排骨牌，则需要在方格中排列两个横排骨牌（无重复方法），若已经在方格中排列两个横排骨牌，则必须在方格中排列一个竖排骨牌。如上右图，再无其他排列方法，因此铺法总数表示为x3=3。  
　　由此可以看出，当n=3时的排列骨牌的方法数是n=1和n=2排列方法数的和。  
（5）推出一般规律：对一般的n，要求xn可以这样来考虑，若第一个骨牌是竖排列放置，剩下有n-1个骨牌需要排列，这时排列方法数为xn-1；若第一个骨牌是横排列，整个方格至少有2个骨牌是横排列（1*2骨牌），因此剩下n-2个骨牌需要排列，这是骨牌排列方法数为xn-2。从第一骨牌排列方法考虑，只有这两种可能，所以有：  
xn=xn-1+xn-2 （n>2）  
x1=1  
x2=2  
xn=xn-1+xn-2就是问题求解的递推公式。任给n都可以从中获得解答。例如n=5，  
x3=x2+x1=3  
x4=x3+x2=5  
x5=x4+x3=8

下面是输入n，输出x1~xn的c++程序：
    #include<iostream>
    using namespace std;
    int main()
    {
      int n,i,j,a[101];
      cout<<"input n:";                     //输入骨牌数
      cin>>n;
      a[1]=1;a[2]=2;
      cout<<"x[1]="<<a[1]<<endl;
      cout<<"x[2]="<<a[2]<<endl;
      for (i=3;i<=n;i++)                //递推过程
       {
         a[i]=a[i-1]+a[i-2];
         cout<<"x["<<i<<"]="<<a[i]<<endl;
    　   }
    } 
      下面是运行程序输入 n=30，输出的结果： 
       input n: 30 
          x[1]=1 
          x[2]=2 
          x[3]=3 
    　　........ 
          x[29]=832040 
          x[30]=1346269
    问题的结果就是有名的斐波那契数。

【例4】昆虫繁殖  
【问题描述】  
科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，问过Z个月以后，共有成虫多少对？0=<X<=20,1<=Y<=20,X=<Z<=50  
【输入格式】  
x,y,z的数值  
【输出格式】  
过Z个月以后，共有成虫对数  
【输入样例】  
1 2 8  
【输出样例】  
37

【参考程序】
    #include<iostream>
    using namespace std;
    int main()
    {
      long long a[101]={0},b[101]={0},i,j,x,y,z;
      cin>>x>>y>>z;
      for(i=1;i<=x;i++){a[i]=1;b[i]=0;}
      for(i=x+1;i<=z+1;i++)            //因为要统计到第z个月后，所以要for到z+1
      {
        b[i]=y*a[i-x];
        a[i]=a[i-1]+b[i-2];                 
      }  
      cout<<a[z+1]<<endl;
      return 0;
    }

【例5】位数问题  
【问题描述】  
在所有的N位数中，有多少个数中有偶数个数字3？由于结果可能很大，你只需要输出这个答案对12345取余的值。  
【输入格式】  
读入一个数N  
【输出格式】  
输出有多少个数中有偶数个数字3。  
【输入样例】  
2  
【输出样例】  
73  
【数据规模】  
1<=N<=1000  
【样例说明】  
在所有的2位数字，包含0个3的数有72个，包含2个3的数有1个，共73个

【算法分析】  
方法一：排列组合(但需要运用动态规划)。  
可以列出公式,在n个格子中放x个3(其中x为偶数,包括0).。  
c(n,x)\*9(n-x)-c(n-1,x)\*9(n-x-1) 含义为在n个格子中取x个3,且不考虑第一位的特殊情况为c(n,x)\*9^(n-x)。  
而第一位为0的情况,为c(n-1,x)\*9^(n-x-1),两者减下,就为答案。  
方法二：递推  
考虑这种题目,一般来说都是从第i-1位推导第i位,且当前位是取偶数还是取奇数的。  
恍然大悟.可以用f\[i\]\[0\]表示前i位取偶数个3有几种情况,f\[i\]\[1\]表示前i位取奇数个3有几种情况。  
则状态转移方程可以表示为:  
　　　f\[i\]\[0\]=f\[i-1\]\[0\]\*9+f\[i-1\]\[1\];f\[i\]\[1\]=f\[i-1\]\[0\]+f\[i-1\]\[1\]\*9;  
边界条件:f\[1\]\[1\]=1;f\[1\]\[0\]=9;

【参考程序】
    #include<iostream>
    using namespace std;
    int main()
    {
      int f[1001][2],n,i,x;
      cin>>n;
      f[1][1]=1;f[1][0]=9;                        
      for(i=2;i<=n;i++) 
       {   
          x=f[1][0];
          if(i==n)x--;
          f[i][0]=(f[i-1][0]*x+f[i-1][1])%12345;
          f[i][1]=(f[i-1][1]*x+f[i-1][0])%12345;   
       }
       cout<<f[n][0]; 
       return 0;
    }

【例6】过河卒（Noip2002）  
【问题描述】  
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点，如图3-1中的C点和P1，……，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE1NzE5NjEz_size_16_color_FFFFFF_t_70]  
【算法分析】  
　　跳马是一道老得不能再老的题目，我想每位编程初学者都学过，可能是在学回溯或搜索等算法的时候，很多书上也有类似的题目，一些比赛中也出现过这一问题的变形（如NOIP1997初中组的第三题）。有些同学一看到这条题目就去搜索，即使你编程调试全通过了，运行时你也会发现：当n,m=15就会超时。  
　　其实，本题稍加分析就能发现，要到达棋盘上的一个点，只能从左边过来（我们称之为左点）或是从上面过来（我们称之为上点），所以根据加法原理，到达某一点的路径数目，就等于到达其相邻的上点和左点的路径数目之和，因此我们可以使用逐列（或逐行）递推的方法来求出从起点到终点的路径数目。障碍点（马的控制点）也完全适用，只要将到达该点的路径数目设置为0即可。  
　　用F\[i\]\[j\]表示到达点(i,j)的路径数目，g\[i\]\[j\]表示点(i, j)有无障碍，g\[i\]\[j\]=0表示无障碍，g\[i\]\[j\]=1表示有障碍。  
　　则，递推关系式如下：  
　　　 F\[i\]\[j\] = F\[i-1\]\[j\] + F\[i\]\[j-1\] //i>0且j>0且g\[i\]\[j\]= 0  
　　　递推边界有4个：  
　　　　F\[i\]\[j\] = 0 //g\[i\]\[j\] = 1  
　　　　F\[i\]\[0\] = F\[i-1\]\[0\] //i > 0且g\[i\]\[0\] = 0  
　　　　F\[0\]\[j\] = F\[0\]\[j-1\] //j > 0且g\[0\]\[j\] = 0  
　　　　F\[0\]\[0\] = 1  
　　考虑到最大情况下：n=20,m=20，路径条数可能会超过231-1,所以要用高精度。

[Link 1]: https://blog.csdn.net/qq_15719613/article/details/104780435
[20200313213048431.png]: https://img-blog.csdnimg.cn/20200313213048431.png
[2020031321310315.png]: https://img-blog.csdnimg.cn/2020031321310315.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE1NzE5NjEz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200313213212627.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE1NzE5NjEz,size_16,color_FFFFFF,t_70