数据结构中递推法_数据结构中递归的递推式 - CSDN
精华内容
参与话题
  • 在所有的递推关系,Fibonacci数列应该是最为大家所熟悉的。在最基础的程序设计语言Logo语言,就有很多这类的题目。而在较为复杂的Basic、Pascal、C语言,Fibonacci数列类的题目因为解法相对容易一些,逐渐退出...

    五种典型的递推关系

    1.Fibonacci数列

    所有的递推关系中,Fibonacci数列应该是最为大家所熟悉的。在最基础的程序设计语言Logo语言中,就有很多这类的题目。而在较为复杂的Basic、Pascal、C语言中,Fibonacci数列类的题目因为解法相对容易一些,逐渐退出了竞赛的舞台。可是这不等于说Fibonacci数列没有研究价值,恰恰相反,一些此类的题目还是能给我们一定的启发的。
    Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。
    问题的提出:有雌雄一对兔子,假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子?
      :设满x个月共有兔子Fx对,其中当月新生的兔子数目为Nx对。第x-1个月留下的兔子数目设为Fx-1对。则:
    Fx=Nx+ Fx-1
       Nx=Fx-2 (即第x-2个月的所有兔子到第x个月都有繁殖能力)
       ∴ Fx=Fx-1+Fx-2 边界条件:F0=0,F1=1
    由上面的递推关系可依次得到:
       F2=F1+F0=1,F3=F2+F1=2,F4=F3+F2=3,F5=F4+F3=5,……。
    Fabonacci数列常出现在比较简单的组合计数问题中,例如以前的竞赛中出现的“骨牌覆盖”问题。在优选法中,Fibonacci数列的用处也得到了较好的体现。

    2.Hanoi塔问题

    问题的提出:Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时,这n个圆盘由大到小依次套在a柱上,如图3-11所示。
    要求把a柱上n个圆盘按下述规则移到c柱上:
    这里写图片描述
      (1)一次只能移一个圆盘;
      (2)圆盘只能在三个柱上存放;
      (3)在移动过程中,不允许大盘压小盘。
      问将这n个盘子从a柱移动到c柱上,总计需要移动多少个盘次?
      
    :设hn为n个盘子从a柱移到c柱所需移动的盘次。显然,当n=1时,只需把a 柱上的盘子直接移动到c柱就可以了,故h1=1。当n=2时,先将a柱上面的小盘子移动到b柱上去;然后将大盘子从a柱移到c 柱;最后,将b柱上的小盘子移到c柱上,共记3个盘次,故h2=3。以此类推,当a柱上有n(n2)个盘子时,总是先借助c柱把上面的n-1个盘子移动到b柱上,然后把a柱最下面的盘子移动到c柱上;再借助a柱把b柱上的n-1个盘子移动到c柱上;总共移动hn-1+1+hn-1个盘次。
       ∴hn=2hn-1+1 边界条件:h1=1

    3.平面分割问题

    问题的提出:设有n条封闭曲线画在平面上,而任何两条封闭曲线恰好相交于两点,且任何三条封闭曲线不相交于同一点,问这些封闭曲线把平面分割成的区域个数。
    :设an为n条封闭曲线把平面分割成的区域个数。 由图3-13可以看出:a2-a1=2;a3-a2=4;a4-a3=6。
    这里写图片描述
    这些式子中可以看出an-an-1=2(n-1)。当然,上面的式子只是我们通过观察4幅图后得出的结论,它的正确性尚不能保证。下面不妨让我们来试着证明一下。当平面上已有n-1条曲线将平面分割成an-1个区域后,第n-1条曲线每与曲线相交一次,就会增加一个区域,因为平面上已有了n-1条封闭曲线,且第n条曲线与已有的每一条闭曲线恰好相交于两点,且不会与任两条曲线交于同一点,故平面上一共增加2(n-1)个区域,加上已有的an-1个区域,一共有an-1+2(n-1)个区域。所以本题的递推关系是an=an-1+2(n-1),边界条件是a1=1。
    平面分割问题是竞赛中经常触及到的一类问题,由于其灵活多变,常常感到棘手,下面的例8是另一种平面分割问题,有兴趣的读者不妨自己先试着求一下其中的递推关系。

    4.Catalan数

    Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的,它经常出现在组合计数问题中。
    问题的提出:在一个凸n边形中,通过不相交于n边形内部的对角线,把n边形拆分成若干三角形,不同的拆分数目用hn表示,hn即为Catalan数。例如五边形有如下五种拆分方案(图3-14),故h5=5。求对于一个任意的凸n边形相应的hn。

    这里写图片描述

    这里写图片描述

    Catalan数是比较复杂的递推关系,尤其在竞赛的时候,选手很难在较短的时间里建立起正确的递推关系。当然,Catalan数类的问题也可以用搜索的方法来完成,但是,搜索的方法与利用递推关系的方法比较起来,不仅效率低,编程复杂度也陡然提高。

    第二类Stirling数

    五类典型的递推关系中,第二类Stirling是最不为大家所熟悉的。也正因为如此,我们有必要先解释一下什么是第二类Strling数。
    **【定义2】**n个有区别的球放到m个相同的盒子中,要求无一空盒,其不同的方案数用S(n,m)表示,称为第二类Stirling数。
    下面就让我们根据定义来推导带两个参数的递推关系——第二类Stirling数。
    :设有n个不同的球,分别用b1,b2,……bn表示。从中取出一个球bn,bn的放法有以下两种:
       ①bn独自占一个盒子;那么剩下的球只能放在m-1个盒子中,方案数为S2(n-1,m-1);
       ②bn与别的球共占一个盒子;那么可以事先将b1,b2,……bn-1这n-1个球放入m个盒子中,然后再将球bn可以放入其中一个盒子中,方案数为mS2(n-1,m)。
    综合以上两种情况,可以得出第二类Stirling数定理:
        【定理】S2(n,m)=mS2(n-1,m)+S2(n-1,m-1) (n>1,m1)
    边界条件可以由定义2推导出:
        S2(n,0)=0;S2(n,1)=1;S2(n,n)=1;S2(n,k)=0(k>n)
    第二类Stirling数在竞赛中较少出现,但在竞赛中也有一些题目与其类似,甚至更为复杂。读者不妨自己来试着建立其中的递推关系。

    小结:通过上面对五种典型的递推关系建立过程的探讨,可知对待递推类的题目,要具体情况具体分析,通过找到某状态与其前面状态的联系,建立相应的递推关系。


    一步一步算法篇

    展开全文
  • 1.递推算法的思想: 利用已知的条件不断推导未知的信息。 2.递推算法的分类: (1).

    1.递推算法的思想:

    	利用已知的条件不断推导未知的信息。
    

    2.递推算法的分类:

    (1).顺推法
    (2).逆推法
    

    3.逆推算法的应用:

    《斐波那契数列》

    • 问题:斐波那契数列又叫兔子数
      月数:1 2 3 4 5 6 7 8…
      对数:1 1 2 3 5 8 13 21…
    • (1).解决核心思想:
      将数字转化成一个公式模型

    • (2).递推公式模型:
      F(1=F(2)=1F(1)=F(2)=1

      F(n)=F(n1)+F(n2)F(n)=F(n-1)+F(n-2)


    4.代码示例:

    首先头文件分别定义stdio.h引用库函数
    其次#define NUM 13

    int main()
    {
    int i;
    int F[NUM] = { 1,1 };//保存兔子的初始数据
    for (i = 2; i <NUM; i++)
    {
    	F[i] = F[i - 1]+F[i - 2];
    }
    for (i = 0; i < NUM; i++)
    	printf("第%d月兔子总数:%d\n", i, F[i]);
    return 0;
    }
    

    5.执行程序图:

    执行效果图

    展开全文
  • 递推算法: 通过已知条件,利用特定关系得到中间结论,然后得到最后结果。 1.顺推: 从已知条件出发,逐步推导出要解决问题的方法。 例如斐波拉契数列。 2. 逆推 根据结果推导出已知条件 */ /...
    /*
    递推算法:
        通过已知条件,利用特定关系得到中间结论,然后得到最后结果。
        1.顺推法:
            从已知条件出发,逐步推导出要解决问题的方法。
            例如斐波拉契数列。
        2. 逆推法
            根据结果推导出已知条件   
    */ 
    
    // 斐波拉契数列的递推实现
    
    # include <stdio.h>
    
    int main(void)
    {
        int Fn, f1, f2;
        // 初始值
        f1 = 1;
        f2 = 1;
        int cnt;
        printf("请输入您想求解的数列元素位数:");
        scanf("%d", &cnt);
        if (1 == cnt)
            Fn = f1;
        else if (2 == cnt)
            Fn = f2;
        else
        {
            int i;
            for (i = 3; i <= cnt; ++i)
            {
                Fn = f1 + f2;
                f1 = f2;
                f2 = Fn;
            }
        } 
        printf("斐波拉契数列中第%d为%d!\n", cnt, Fn);
        
        
        return 0;
    } 
    /*
    迭代算法:
        迭代算法又称为辗转法,是一种不断用旧的变量值递推得到
        新的变量值的过程。
    迭代法与递推法相同之处在于都是使用循环语句实现。不同之处
    在于,迭代法使用的是 while 循环,而递推法使用的是 for 循
    环。迭代法在迭代结束后得到一个解或一组解,递推法的循环控
    制变量改变一次就得到一个解,循环结束得到一系列的解。迭代
    法的迭代次数事前是未知的,而递推法的递推次数事前是已知的
    
    迭代法分为精确迭代和未知迭代。
    精确迭代:
        通过迭代可以得到一个精确的解。例如:求最大公约数,进
        制转换,质因数的分解 ,谷角猜想。
    近似迭代:
        通过迭代得到近似的解。例如:二分法,求定积分。 
    */ 
    
    // 利用精确迭代法求最大公约数和最小公倍数
    
    # include <stdio.h>
    
    int main(void)
    {
        int i, j;
        printf("请输入两个正整数:");
        scanf("%d %d", &i, &j);
        int r;  //  表示余数
        int f1, f2;
        if (i < j)
        {
            f1 = j;
            f2 = i;
        } 
        else
        {
            f1 = i;
            f2 = j;
        }
        while (0 != (f1 % f2))
        {
            r = f1 % f2;
            f1 = f2;
            f2 = r;
        }
        printf("最大公约数为 %d\n最小公倍数为 %d\n", r, i*j/r);
        
        return 0;
    } 

     

    转载于:https://www.cnblogs.com/lnlin/p/6776899.html

    展开全文
  • 下面通过一些典型实例及其扩展来讨论递推法的应用。 【例2】骨牌铺方格 在2×n的一个长方形方格,用一种2×1的骨牌铺满方格。输入n(n<=40),输出铺放方案的总数。 例如n=3时,为2×3方格,骨牌的铺放...

          下面通过一些典型实例及其扩展来讨论递推法的应用。

    【例2】骨牌铺方格

          在2×n的一个长方形方格中,用一种2×1的骨牌铺满方格。输入n(n<=40),输出铺放方案的总数。

          例如n=3时,为2×3方格,骨牌的铺放方案有三种,如下图1所示。

     

    图1  2×3方格的骨牌铺放方案

          (1)编程思路。

          设f[i]为铺满2*n方格的方案数,则有    f[i]=f[i-1]+f[i-2]。

          其中,f[i-1]为铺满2*(n-1)方格的方案数(既然前面的2*(n-1)的方格已经铺满,那么最后一个只能是竖着放)。f[i-2]为铺满2*(n-2)方格的方案数(如果前面的2*(n-2)的方格已经铺满,那么最后的只能是横着放两块,否则会重复)。

          初始情况为:f[1]=1,f[2]=2。

          (2)源程序。

    #include <iostream>

    using namespace std;

    int main()

    {

        int i,n,f[41];

        cin>>n;

        f[1]=1;f[2]=2; 

        for(i=3;i<=n;i++)

         f[i]=f[i-1]+f[i-2];      // 按递推关系实施递推 

        cout<<f[n]<<endl;

        return 0;

    }

           (3)问题扩展。

          有一个大小是2×n的长方形方格,现用2种规格的骨牌铺满,骨牌规格分别是 2×1和2×2。输入n(n<=30),输出铺放方案的总数。

          (4)扩展问题编程思路。

          铺方格的骨牌规格多了一种,递推公式做相应变化。

          设f[i]为铺满2*n方格的方案数,则有   f[i]=f[i-1]+2*f[i-2]。

          其中,f[i-1]为铺满2*(n-1)方格的方案数(既然前面的2*(n-1)的方格已经铺满,那么最后一个只能是竖着放)。f[i-2]为铺满2*(n-2)方格的方案数(如果前面的2*(n-2)的方格已经铺满,那么最后的2*2方格或者横着放两块2*1的骨牌,或者放1块2*2的骨牌)。

          初始情况为:f[1]=1,f[2]=3。

           (5)扩展问题的源程序。

    #include <iostream>

    using namespace std;

    int main()

    {

        int i,n,f[31];

        cin>>n;

        f[1]=1;f[2]=3; 

        for(i=3;i<=n;i++)

         f[i]=f[i-1]+2*f[i-2];      // 按递推关系实施递推 

        cout<<f[n]<<endl;

        return 0;

    }

    【例3】上台阶

          设有一个共有n级的台阶,某人上台阶一步可上1级,也可上2级。编写一个程序,输入台阶的级数n(n<=40),输出某人从底层上到台阶顶层的走法的种数。

          (1)编程思路。

          先考虑最简单的情况。如果只有1级台阶,那显然只有一种上法。如果有2级台阶,那就有两种上的方法了:一种是分两次上,每次上1级;另外一种就是一次上2级。

          再来讨论一般情况。设把n级台阶时的上法看成是n的函数,记为f(n)。

          当n>2时,第一次上的时候就有两种不同的选择:一是第一次只上1级,此时上法数目等于后面剩下的n-1级台阶的上法数目,即为f(n-1);另外一种选择是第一次上2级,此时上法数目等于后面剩下的n-2级台阶的上法数目,即为f(n-2)。因此n级台阶时的不同上法的总数f(n)=f(n-1)+(f-2)。

          由此推导出递推公式 f(n)=f(n-1)+(f-2)  (n>2)

          初始情况:f(1)=1; f(2)=2。

          (2)源程序。

    #include <iostream>

    using namespace std;

    int main()

    {

        int k,n,f[41];

        cout<<"请输入台阶总数n:";

        cin>>n;

        f[1]=1;f[2]=2; 

        for(k=3;k<=n;k++)

         f[k]=f[k-1]+f[k-2];      // 按递推关系实施递推 

        cout<<"上法总数为 "<<f[n]<<endl;

        return 0;

    }

          (3)扩展1。

          设一个台阶有n级,一步有m种跨法,一步跨多少级均从键盘输入(输入的级数从小到大)。求从底层上到台阶顶层的走法的种数。

          (4)扩展1的编程思路。

          例如,设有10级台阶,输入的m依次为2、4、7。递推式可写成

           f(n)=f(n-2)+f(n-4)+f(n-7)  (n>=8)。但由于事先不知输入的是2、4、7,所以递推初始情况f(1)~f(7)无法直接赋初值,也就无法用一个这个单纯的递推式直接递推。必须先采用某种方法根据输入的m个一步上的台阶数将初始条件求取出来。

          实际上,可以将上台阶的递推分成多级递推,这样初始条件可在分级递推中求取。

    当第1次输入2时,f(1)=0,f(2)=1。(初始条件)

    当第2次输入4时,第1级递推:

    f(3)=f(3-2)=0,  f(4)=f(4-2)+1=2。(因为4本身即为一个一步到位的上法)

    当第3次输入7时,第2级递推:

    f(5)=f(5-2)+f(5-4)=0,f(6)=f(6-2)+f(6-4)=3,f(7)=f(7-2)+f(7-4)+1=1。

    为求第10级台阶上法,采用三级递推:

    f(8)=f(8-2)+f(8-4)+f(8-7)=5,f(9)=f(9-2)+f(9-4)+f(9-7)=2,

    f(10)=f(10-2)+f(10-4)+f(10-7)=8。

    下面探讨一般情况。

          设上n级台阶的不同上法为f(n),从键盘输入一步跨多少级的m个整数分别为x(1)、x(2)、…、x(m),输入时约定1<=x(1) <x(2) <…<x(m)。

    当1<=n<x(1) 时,f(n)=0;      f(x(1))=1。(初始条件)

    当x(1)<n<x(2) 时,第1级递推:f(n)=f(n−x(1));

      f(x(2))=f(n-x(1))+1 (存在x2这个一步到位的上法)。

    当x(2)<n<x(3) 时,第2级递推:f(n)=f(n−x(1))+f(n−x(2));

      f(x(3))=f(n-x(1))+ f(n−x(2)) +1 (存在x3这个一步到位的上法)。

    ……

    当x(m-1)<n<x(m),有第m-1级递推:f(n)=f(n−x(1))+f(n−x(2))+…+f(n−x(m-1));

    f(x(m))=f(n−x(1))+f(n−x(2))+…+f(n-x(m-1))+1。

    当x(m)<n时,第m级递推: f(n)=f(n−x(1))+f(n−x(2))+…+f(n−x(m))

    为了便于统一处理,不妨附设一个x(m+1),使得x(m+1)=max(x(m),n)+1。

    这样第m级递推统一描述为:

           当x(m)<n<x(m+1) 时,第m级递推: f(n)=f(n−x(1))+f(n−x(2))+…+f(n−x(m))

              f(x(m+1))= f(n−x(1))+f(n−x(2))+…+f(n−x(m))+1。

          (5)扩展1的源程序。

    #include <iostream>

    using namespace std;

    int main()

    {

           int i,j,k,m,n,t,x[10],f[51];

        cout<<"请输入总台阶数:";

        cin>>n;

        cout<<"一次有几种跳法:";

        cin>>m;

        cout<<"请从小到大输入一步跳几级。"<<endl;

        for(i=1; i<=m; i++)    

            cin>>x[i];

        for(i=1;i<x[1];i++)   f[i]=0;  

        f[x[1]]=1;

        x[m+1]=(x[m]>n?x[m]:n)+1;

           for(k=1;k<=m;k++)

            for(t=x[k]+1;t<=x[k+1];t++)

                  {

                         f[t]=0;

                for(j=1;j<=k;j++)             // 按公式累加实现分级递推 

                   f[t]=f[t]+f[t-x[j]];

                if(t==x[k+1])             

                   f[t]=f[t]+1;

                  }

           cout<<"共有不同的跳法种数为 "<<f[n]<<endl;

           return 0;

    }

          (6)扩展2。

          例3中的递推式实际上就是斐波那契数列的递推式。这个数列的增长很快,46项以后就会超过整型数据的表数范围。现设台阶有1000级,按一步可上1级,也可上2级的上法,不同的上法种数是一个209位的整数,如何正确求得这个种数。

        (7)扩展2的编程思路。

          由于要求的数据超过了整数表示的范围,需要进行高精度计算。

          如何表示和存放大数呢?一个简单的方法就是:用数组存放和表示大数。一个数组元素,存放大数中的一位。

          我们日常书写一个大整数,左侧为其高位,右侧为其低位,在计算中往往会因进位(carry)或借位(borrow)导致高位增长或减少,因此可以定义一个整型数组(int bignum[maxlen])从低位向高位实现大整数的存储,数组的每个元素存储大整数中的一位。

          显然,在C++中,int类型(4个字节/32位计算机)数组元素存储十进制的一位数字非常浪费空间,并且运算量也非常大,因此可将存储优化为万进制,即数组的每个元素存储大整数数字的四位。(为什么选择万进制,而不选择更大的进制呢?这是因为万进制中的最大值9999相乘时得到的值是99980001,不会超过4个字节的存储范围,而十万进制中的最大值99999相乘时得到的值是9999800001,超过4个字节的存储范围而溢出,从而导致程序计算错误。)

          在编写程序代码过程中作如下定义:

    const int base=10000;

    const int maxlen=50+1;

    int bignum[maxlen];

          说明:base表示进制为万进制,maxlen表示大整数的长度,1个元素能存储4个十进制位,50个元素就存储200个十进制位,而加1表示下标为0的元素另有它用,程序用作存储当前大整数的位数。

          下面讨论大整数的加法运算的实现。

          可以采用小学中曾学习的竖式加法。两个大整数98240567043826400046和3079472005483080794进行加法运算,如图2所示。

     

    图2  加法的计算过程

          从图2中可以得知,做加法运算是从低位向高位进行,如果有进位,下一位进行相加时要加上进位,如果最高位已计算完还有进位,就要增加存储结果的位数,保存起进位来。关于进位的处理,一般定义单独变量carry进行存储。

          (8)扩展2的源程序。

    #include <iostream>

    using namespace std;

    const int base=10000;

    const int maxlen=60+1;

    void addition(int *bignum1, int *bignum2, int *bignum_ans);

    void printbignum(int *bignum);

    int main()

    {

        int k,n,f[1001][maxlen];

        cout<<"请输入台阶总数n:";

        cin>>n;

        f[1][0]=1;  f[1][1]=1;

           f[2][0]=1;  f[2][1]=2;

        for(k=3;k<=n;k++)

          addition(f[k-1],f[k-2],f[k]);      // 按递推关系实施递推 

        cout<<"上法总数为 ";

           printbignum(f[n]);

        return 0;

    }

    void addition(int *bignum1, int *bignum2, int *bignum_ans)

    {

           int carry=0;

        memset(bignum_ans,0,sizeof(int)*maxlen);

           bignum_ans[0]=bignum1[0]>bignum2[0]?bignum1[0]:bignum2[0];

           for(int pos=1; pos<=bignum_ans[0]; pos++){

                  carry+=bignum1[pos]+bignum2[pos];

                  bignum_ans[pos]=carry%base;

                  carry/=base;

           }

           if(carry)

                  bignum_ans[++bignum_ans[0]]=carry;

    }

    void printbignum(int *bignum)

    {

           int *p=*bignum+bignum;

           cout<<*p--;

           cout.fill('0');        // 定义填充字符'0'

           while(p>bignum){ cout.width(4); cout<<*p--; }

           cout<<endl;

    }

          如果要求2000级台阶的不同上法种数(是一个418位的整数),上面的程序如何修改?如果求5000级甚至10000级的台阶呢?请读者自己动手做一做。在修改过程中,定义的二维数组造成栈溢出怎么办?

          (9)扩展3——第39级台阶。

          小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题:

           如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也就是说一共要走偶数步。那么,上完39级台阶,有多少种不同的上法呢?

           (10)扩展3的编程思路。

           由于在上台阶的过程中需要考虑不同的迈脚情况,因此需要定义二维数组c[40][2],数组元素c[i][0]表示上到第i级台阶时最后一步是左脚的方法数,c[i][1] 表示上到第i级台阶时最后一步是右脚的方法数。

    由于每一步能上一级或两级台阶,因此可得递推式:

    c[i][0] = c[i-1][1]+c[i-2][1] (因为最后一步为左脚,倒数第二步肯定为右脚)

    c[i][1] = c[i-1][0]+c[i-2][0] (因为最后一步为右脚,倒数第二步肯定为左脚)

    初始情况为:

    c[1][0]=1,第一步左脚直接迈一级台阶。

    c[1][1]=0,因为先迈左脚,右脚不可能落在第1级台阶。

    c[2][0]=1,第一步左脚直接迈两级台阶。

    c[2][1]=1,左右脚各迈一级台阶,右脚正好落在第2级台阶。

    (11)扩展3的源程序。

    #include<iostream>

    using namespace std;

    int main()

    {

        int i;

        int c[40][2];

        c[1][1] = 0;   c[1][0]=1;

        c[2][1] = 1;   c[2][0]=1;

        for(i = 3; i <= 39; ++i)

           {

            c[i][0] = c[i - 1][1] + c[i - 2][1];

            c[i][1] = c[i - 1][0] + c[i - 2][0];

        }

        cout<<c[39][1]<<endl;

        return 0;

    }

         

           例2和例3采用的都是顺推,下面看一个采用倒推求解的实例。

          【例4】猴子吃桃

          有一个猴子第一天摘下若干个桃子,当即吃了一半,还不过瘾,又多吃了一个。第二天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩下的一半后又多吃一个。到第10天早上想再吃时,见只剩下一个桃子了。

    求第一天共摘了多少个桃子?

    (1)编程思路。

    设x[n]表示第n天吃桃子前的桃子数,则有x[10]=1。

    由于, x[i]=x[i-1]-x[i-1]/2-1,

    因此,递推关系式为: x[i-1]=2*(x[i]+1)。倒推求得x[1]就是猴子所摘的桃子数。

    (2)源程序。

    #include <iostream>

    using namespace std;

    int  main()

    {

        int a[11],i;

           a[10]=1;

           for (i=9;i>=1;i--)

                  a[i]=2*(a[i+1]+1);

           cout<<a[1]<<endl;

        return  0;

    }

          (3)问题扩展。

          有一猴子第一天摘下若干个桃子,当即吃了一半,还不过瘾,又多吃了m个。第二天早上又将剩下的桃子吃掉一半,又多吃了m个。以后每天早上都吃了前一天剩下的一半后又多吃m个。到第n天早上想再吃时,见只剩下d个桃子了。

          求第一天共摘了多少个桃子(m,n,d均由键盘输入,且1<=n,m,d<=20)?

          (4)扩展问题的源程序。

    #include <iostream>

    using namespace std;

    int  main()

    {

        int i,m,n,d;

        cin>>n>>m>>d;

           int *a;

           a=new int [n+1];

           a[n]=d;

           for (i=n-1;i>=1;i--)

                  a[i]=2*(a[i+1]+m);

           cout<<a[1]<<endl;

        return  0;

    }

     【例5】过河卒

          如图3,在棋盘的A点有一个过河卒,需要走到目标B点。卒行走规则:可以向下、或者向右。同时在棋盘上的任一点有一个对方的马(如图4-4的C点),该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如,图4-4中C点上的马可以控制9个点(图中的P1,P2,…,P8 和C)。卒不能通过对方马的控制点。

           棋盘用坐标表示,A点(0,0)、B点(n,m)(n,m为不超过50的整数,并由键盘输入),同样马的位置坐标通过键盘输入,并约定C<>A,同时C<>B。

           编写程序,计算出卒从A点能够到达B点的路径的条数。

           例如,输入6  6  3  2,输出为17。

     

    图3  棋盘上的过河卒和对方的控制马

    (1)编程思路。

          在棋盘的A点(0,0)的过河卒要到达棋盘上的任意一点,只能从左边和上边两个方向过来。因此,要到达某一点的路径数,等于和它相邻的左、上两个点的路径数和:

            F[i][j] = F[i-1][j] + F[i][j-1]。

          可以使用逐列(或逐行)递推的方法来求出从起始顶点到终点的路径数目,即使有障碍(将马的控制点称为障碍),这一递推方法也完全适用,只要将到达该点的路径数目设置为0即可,用F[i][j]表示到达点(i,j)的路径数目,g[i][j]表示点(i,j)有无障碍,递推方程如下:

    F[0][0] = 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[i][j] = F[i-1][j] + F[i][j-1]   (i > 0,j > 0,g[x, y] = 0) // 递推式

    (2)源程序。

    #include <iostream>

    using namespace std;

    int main() 

        int i,j,x,y,n,m,forbidden[51][51]; 

        int ans[51][51]; 

        int dx[8]={-2,-1,1,2,2,1,-1,-2};

           int dy[8]={1,2,2,1,-1,-2,-2,-1};

        cin>>n>>m>>x>>y; 

        for (i=0;i<=n;i++)

                  for (j=0;j<=m;j++)

            {

                         forbidden[i][j]=0;

                ans[i][j]=0;

                  }

        ans[0][0]=1; 

        forbidden[x][y]=1;

           for (i=0;i<8; i++)

            if (x+dx[i]>=0 && x+dx[i]<=n && y+dy[i]>=0 && y+dy[i]<=m)

                     forbidden[x+dx[i]][y+dy[i]]=1;

           for (i=1; i<=n; i++) 

            if (forbidden[i][0]==0) 

                ans[i][0]=1; 

            else break; 

        for (i=1; i<=m; i++) 

            if (forbidden[0][i]==0) 

                ans[0][i]=1; 

            else break; 

        for (i=1; i<=n; i++) 

            for (j=1; j<=m; j++) 

                if (forbidden[i][j]==0) 

                    ans[i][j]=ans[i-1][j]+ans[i][j-1]; 

        cout<<ans[n][m]<<endl;

        return 0; 

    【例6】学生队列。

    There are many students in PHT School. One day, the headmaster whose name is PigHeader wanted all students stand in a line. He prescribed that girl can not be in single. In other words, either no girl in the queue or more than one girl stands side by side.

    The case n=4 (n is the number of children) is like FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM Here F stands for a girl and M stands for a boy. The total number of queue satisfied the headmaster’s needs is 7.

    Can you make a program to find the total number of queue with n children?

          (1)编程思路。

          设满足要求的n个学生的队列数为F(n)表示。

          简单枚举n较小的情况为:F(0)=1 (没有人也是合法的,这个可以特殊处理,就像0的阶乘定义为1一样); 

            F(1)=1(一个男生M);F(2)=2;(两个男生MM或两个女生FF);F(3)=4(MMM、MFF、FFM或FFF)。

          当人数n大于3时,n个学生排队可以看成是由n-1个学生排好队后再加一个学生。按最后加的学生的性别分两种情况:

          1)当加的最后一个学生是男孩M时候,前面n-1个随便排出来,只要符合要求就可以,即方案数为F(n-1)。

          2)当加的最后一个学生是女孩F时候,第n-1个学生肯定是女孩F,这时候又有两种情况:

          ① 前面n-2个学生按满足要求的方法排好队,后面加两个女生一定也满足要求,此时方案数为F(n-2)。

          ② 前面n-2个人不是满足要求的队列,加上两个女生也有可能是合法的。当第n-2个学生是女孩而第n-3个学生是男孩时,后面加上两个女孩可能合法。此时前n-4个学生的队列必须满足要求,即方案数为F(n-4)。

          综上所述:总数F(n)= F(n-1)+ F(n-2)+ F(n-4)。

          (2)源程序。

    #include <iostream>

    using namespace std;

    int main()

    {

        int i,n,f[31];

        f[0]=1; f[1]=1; f[2]=2; f[3]=4; 

        for(i=4;i<=30;i++)

           f[i]=f[i-1]+f[i-2]+f[i-4];      // 按递推关系实施递推 

        while (cin>>n && n!=-1)

           {

                  cout<<f[n]<<endl;

           }

        return 0;

    }

    【例7】栈

          栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。

          栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一个元素进栈)。

          栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。晶晶宁宁同学在复习栈的基本概念时,想到了一个书上没有讲过的问题,而她自己无法给出答案,所以需要你的帮忙。

          晶晶考虑的是这样一个问题:一个操作数序列,从1,2,一直到n(图4-5所示为1到3的情况),栈A的深度大于n。

    现在可以进行两种操作,

    1)将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的push操作)。

    2)将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的pop操作)。

          使用这两种操作,由一个操作数序列就可以得到一系列的输出序列。设栈的原始状态如图4所示,由123生成序列231的过程如图5所示。

     

    图4  栈的原始状态

     

    图5  采用栈生成序列231的过程

          请编写程序,对输入的n,计算并输出由操作数序列1,2,…,n经过栈操作可能得到的输出序列的总数。

          (1)编程思路。

           先模拟入栈、出栈操作,看看能否找出规律,设f(n)表示n个数通过栈操作后的排列总数,当n很小时,很容易模拟出f(1)=1,f(2)=2,f(3)=5。通过观察,看不出它们之间的递推关系,再分析n=4的情况,假设入栈前的排列为“4123”,按第一个数“4”在出栈后的位置进行分情况讨论:

          1)若“4”最先输出,刚好与n=3相同,总数为f(3)。

          2)若“4”第二个输出,则在“4”的前只能是“1”,“23”在“4”的后面,这时可以分别看作是n=1和n=2时的两种情况,排列数分别为f(1)和f(2),所以此时的总数为f(1)*f(2)。

          3)若“4”第三个输出,则“4”的前面二个数为“12”,后面一个数为“3”,组成的排列总数为f(2)*f(1)。

          4)若“4”第四个输出,与情况(1)相同,总数为f(3)。

         所以有:f(4)=f(3)+f(1)*f(2)+f(2)*f(1)+f(3)。

          若设0个数通过栈后的排列总数为:f(0)=1;

          上式可变为:f(4)=f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0)。

    再进一步推导,不难推出递推式:

    f(n)=f(0)*f(n-1)+f(1)*f(n-2)+…+f(n-1)*f(0);

    即f(n)=      (n>=1)

    初始值:f(0)=1;

    有了以上递推式,就很容易用递推法写出程序。

    (2)源程序。

    #include <iostream>

    using namespace std;

    int  main()

    {

        int a[19]={0},n,i,j;

           cin>>n;

           a[0]=1;

           for (i=1;i<=n;i++)

                  for (j=0;j<=i-1;j++)

                         a[i]=a[i]+a[j]*a[i-j-1];

           cout<<a[n]<<endl;

        return  0;

    }

          (3)用公式直接求解。

          实际上,一个栈的入栈序列为1,2,3,…,n,其不同的出栈序列的种数是一个卡特兰数。

          卡特兰数是组合数学中一个常出现在各种计数问题中出现的数列。该数列如下:

    C0=1,C1=1,C2=2,C3=5,C4=14,C5=42,C6=132,C7=429,C8=1430,

    C9=4862,C10=16796,C11=58786,C12=208012,……。

    卡塔兰数的一般项公式为:

     

            Cn的另一个表达形式为:

     

     

    下面简要描述一下这个公式的推导情况。

          对于1~n中的每一个数来说,必须入栈一次、出栈一次。设入栈为状态“1”,出栈为状态“0”。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1~n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b),因此输出序列的总数目等于由左至右扫描由n个1和n个0组成的2n位二进制数,1的累计数不小于0的累计数的方案种数。

          在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求(由左至右扫描,0的累计数大于1的累计数)的方案数即为所求。

          不符合要求的数的特征是由左至右扫描时,必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数,此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如果把后面这2(n-m)-1位上的0和1互换,使之成为n-m个0和n-m-1个1,结果得1个由n+1个0和n-1个1组成的2n位数,即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。反过来,任何一个由n+1个0和n-1个1组成的2n位二进制数,由于0的个数多2个,2n为偶数,故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换,使之成为由n个0和n个1组成的2n位数,即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。因而不合要求的2n位数与n+1个0,n-1个1组成的排列一一对应。 即不符合要求的方案数为c(2n,n+1)。

           由此得出,输出序列的总数目= c(2n,n)-c(2n,n+1)=c(2n,n)/(n+1)。

          (4)采用公式直接求解的源程序。

    #include <iostream>

    using namespace std;

    int combin(int n,int m)   // 求组合数C(n,m)

    {

           int p=1,i,t;

        t=n;

           for (i=1;i<=m;i++)

           {

            p=p*t/i;

                  t--;

           }

           return p;

    }

    int main() 

        int n; 

        cin>>n; 

        cout<<combin(2*n,n)/(n+1)<<endl;

        return 0; 

     

    【例8】整数划分问题

          正整数s(简称为和数)的划分(又称拆分)是把s分成为若干个正整数(简称为零数或部分)之和,划分式中允许零数重复,且不记零数的次序。

          试求s=12共有多少个不同的划分式?展示出所有这些划分式。

    (1)编程思路。

    整数划分问题可采用多种方法解决,下面我们采用递推的法来完成。

    为了建立递推关系,先对和数k较小时的划分式作观察归纳:

    k=2:1+1;2    2种划分式

    k=3:1+1+1;1+2;3      3种划分式

    k=4:1+1+1+1;1+1+2;1+3;2+2;4     5种划分式

    k=5:1+1+1+1+1;1+1+1+2;1+1+3;1+2+2;1+4;2+3;5    7种划分式

          由以上各划分看到,除和数本身k=k这一特殊划分式外,其它每一个划分式至少为两项之和。约定在所有划分式中零数作非降序排列,探索和数k的划分式与和数k−1的划分式存在以下递推关系:

          1)在所有和数k−1的划分式前加零数1都是和数k的划分式。

          2)和数k−1的划分式的前两个零数作比较,如果第1个零数x1小于第2个零数x2,则把第1个零数加1后成为和数k的划分式。

    定义一个三维数组a,a[k][j][i]表示为和数k的第j个划分式的第i个数。

    递推的初始条件为:a[2][1][1]=1; a[2][1][2]=1; a[2][2][1]=2。

    根据递推关系,实施递推:

    1)实施在k−1所有划分式前加1操作。

    a[k][j][1]=1;

    for (t=2;t<=k;t++)         

            a[k][j][t]=a[k−1][j][t−1];          //  k−1的第t−1项变为k的第t项

    2)若k−1划分式第1项小于第2项,第1项加1,变为k的第i个划分式

           if(a[k-1][j][1]<a[k-1][j][2])  // 若k-1划分式第1项小于第2项 

             { i++;                     // 第1项加1为k的第i个划分式的第1项 

              a[k][i][1]=a[k-1][j][1]+1;    

              for(t=2;t<=k-1;t++)

                 a[k][i][t]=a[k-1][j][t];

              }

    (2)源程序及运行结果。

    #include <iostream>

    #include <iomanip>

    using namespace std;

    int main()

    {

           int s,i,j,k,t,cnt;

        static int a[21][800][21]={0};

        cout<<"input s(s<=20):";

           cin>>s;

        a[2][1][1]=1; a[2][1][2]=1; a[2][2][1]=2;

        cnt=2;

        for(k=3;k<=s;k++)

        {

                  for(j=1;j<=cnt;j++)

            {

                         a[k][j][1]=1;          

                for(t=2;t<=k;t++)    // 实施在k-1所有划分式前加1操作 

                   a[k][j][t]=a[k-1][j][t-1];    

            }

            for(i=cnt,j=1;j<=cnt;j++)

               if(a[k-1][j][1]<a[k-1][j][2])  // 若k-1划分式第1项小于第2项 

                     {

                            i++;              // 第1项加1为k的第i个划分式的第1项 

                   a[k][i][1]=a[k-1][j][1]+1;    

                   for(t=2;t<=k-1;t++)

                      a[k][i][t]=a[k-1][j][t];

               }

            i++;   a[k][i][1]=k;    // k的最后一个划分式为:k=k 

            cnt=i;

           }

        for(j=1;j<=cnt;j++)        // 输出s的所有划分式 

        {

                  cout<<setw(4)<<j<<": "<<s<<"="<<a[s][j][1];

            i=2;

            while (a[s][j][i]>0)

            {

                         cout<<"+"<<a[s][j][i];

                         i++;

                  }

            cout<<endl;

           }

        return 0;

    }

          (3)整数划分的优化。

          上面递推算法的时间复杂度与空间复杂度为O(n2u),其中u为n划分式的个数。由于u随n增加非常快,难以估算其数量级,因此算法的时间复杂度与空间复杂度是很高的。

          下面我们对整数划分进行集智。

          分析上面使用三维数组a[k][j][i]完成的递推过程。当由k−1的划分式推出k的划分式时,k−1以前的数组单元已完全闲置。因此,可以考虑把三维数组a[k][j][i]改进为二维数组a[j][i]。进行和数为k的递推前,数组元素a[j][i]表示和数是k−1的已有划分式。根据递推关系推出和数为k的划分式:

           1)把a[j][i]依次存储到a[j][i+1],加上第一项a[j][1]=1;这样完成在k−1的所有划分式前加1的操作,转化为k的划分式。

    for(t=i;t>=1;t−−)

           a[j][t+1]=a[j][t];

    a[j][1]=1;

           2)对已转化的cnt个划分式逐个检验,若其第2个数小于第3个数(相当于k−1时的第1个数小于第2个数),则把第2个数加1,去除第一个数后,作为k时增加的一个划分式,为第t个(t从cnt开始,每增加一个划分式,t增1)划分式。

    for(t=u,j=1;j<=u;j++)

      if(a(j,2)<a(j,3))     // 若k−1划分式第1项小于第2项 

        {t++;

         a(t,1)=a(j,2)+1;  // 第1项加1 作为k的第t个划分式的第1项

         i=3;

         while(a(j,i)>0)

            {a(t,i−1)=a(j,i);i++;}

         }   

          (4)优化后的源程序。

    #include <iostream>

    #include <iomanip>

    using namespace std;

    int main()

    {

           int s,i,j,k,t,cnt;

        static int a[1600][25]={0};

        cout<<"input s(s<=24):";

        cin>>s;

        a[1][1]=1;a[1][2]=1;a[2][1]=2;

           cnt=2;

        for(k=3;k<=s;k++)

        {

                  for(j=1;j<=cnt;j++)

            {

                         i=k-1;          

                for(t=i;t>=1;t--)         // 实施在k-1所有划分式前加1操作 

                  a[j][t+1]=a[j][t];

                a[j][1]=1;

                  }

            for(t=cnt,j=1;j<=cnt;j++)

              if(a[j][2]<a[j][3])   // 若k-1划分式第1项小于第2项 

                    {

                           t++;

                  a[t][1]=a[j][2]+1;   // 第1项加1 

                  i=3;

                  while(a[j][i]>0)

                  {

                                  a[t][i-1]=a[j][i];

                                  i++;

                           }

                    }

            t++;  a[t][1]=k;             // 最后一个划分式为:k=k 

            cnt=t;

           }

        for(j=1;j<=cnt;j++)        // 输出s的所有划分式 

        {

                  cout<<setw(4)<<j<<": "<<s<<"="<<a[j][1];

            i=2;

            while (a[j][i]>0)

            {

                         cout<<"+"<<a[j][i];

                         i++;

                  }

            cout<<endl;

           }

        return 0;

    }

          改进的递推程序把原有的三维数组优化为二维数组,降低了算法的空间复杂度,拓展了算法的求解范围。

          但是,由于划分式的数量cnt随和数s增加得相当迅速。例如,和数为24时有1575种划分。因此尽管改进为二维数组,求解的和数s也不可能太大。

    转载于:https://www.cnblogs.com/cs-whut/p/11022612.html

    展开全文
  • #include<stdio.h> #define M 10007 int main() { int a1,a2; a1=a2=1; int temp; long n; long i; scanf("%ld",&n); for(i=1;i<n;i++) { temp=a2; a2=(a1+a2)%M;... print...
  • 递推方程的求解

    千次阅读 2014-06-25 00:14:31
    在计算算法分析的过程,难免会遇到复杂度的递推方程,求解递推方程是获得复杂度关于输入规模n的函数的必然途径。  目前,主要存在的求解递推方程的方法如下: 迭代: 直接迭代;换元迭代;差消...
  • 数据结构面试题

    千次阅读 多人点赞 2018-01-22 10:21:19
    数据结构面试题 1.数据结构与算法常见笔试题    第一章 数据结构与算法 一.算法的基本概念 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 1.算法的基本特征:可行...
  • 数据结构与算法常见笔试题

    万次阅读 多人点赞 2017-09-10 22:25:46
    1.数据结构与算法常见笔试题   第一章 数据结构与算法 一.算法的基本概念 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 1.算法的基本特征:可行性,确定性,有穷性,拥有足够的情报。 2....
  • 一、数据结构知识点总结整理 3 2.数据结构的定义: 4 3.数据结构的知识: 9 二、数据结构的实现 16 1、二叉树三种遍历的非递归算法 16 1.先序遍非递归算法 16 2.中序遍历非递归算法 17 3.后序遍历非递归算法 18 4....
  • 数据结构之递归

    千次阅读 2018-04-20 17:08:17
    本篇是数据结构与算法的第5篇,从这篇种我们将深入了解递归算法,这可能是一篇分水岭的博文,因为只有在理解递归的基础上,我们才可能更轻松地学习树的数据结构,实际上数据结构系列书籍递归并没有讲得特别通俗...
  • 【面试笔试】数据结构与算法

    千次阅读 2016-05-05 17:27:01
    2.算法的基本要素:算法数据的运算和操作、算法的控制结构。 3.算法设计的基本方法:列举、归纳递推、递归、减半递推技术、回溯。 4.算法设计的要求:正确性、可读性、健壮性、效率与低存储量需求二....
  • 题目描述: 斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N >...
  • 【超详细】数据结构总结及思维导图(王道考研)

    万次阅读 多人点赞 2020-08-09 23:40:20
    数据结构 第一章:数据结构的 基本概念 定义 在任何问题,数据元素都不是孤立存在的,而是在它们之间存在着某种关系,这种数据元素相互之间的关系称为结构(Structure)。数据结构是相互之间存在一种或多种特定...
  • 数据结构 数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。...根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型:线性结...
  • 数据结构与算法有哪些

    千次阅读 2017-05-29 16:00:47
    数据结构与算法 1、 算法的基本特征:可行性、确定性、有穷性、拥有足够的情报  2、 算法的基本运算和操作:算术运算、逻辑运算、关系运算、数据传输 3、 算法的基本控制结构:顺序结构、选择结构、循环(重复)...
  • 常用数据结构、算法、设计模式

    千次阅读 2019-08-08 16:37:31
    数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合数据元素之间的关系组成 。 常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示: 二,常用的设计模式: 设计模式...
  • 数据结构是算法实现的基础,算法总是要依赖于某种数据结构来实现的。往往是在发展一种算法的时候,构建了适合于这样的算法的数据结构。一种数据结构假设脱离了算法,也就没有存在的价值了。 算法的作用----解决不论...
  • 数据结构 第一章:数据结构的基本概念 定义 在任何问题,数据元素都不是孤立存在的,而是在它们之间存在着某种关系,这种数据元素相互之间的关系称为结构(Structure)。数据结构是相互之间存在一种或多种特定...
1 2 3 4 5 ... 20
收藏数 11,042
精华内容 4,416
关键字:

数据结构中递推法