算法讲解之递归算法

递归算法

概述

​ 前面已经介绍了关于递归调用这样一种操作,而递归程序设计是C++语言程序设计中的一种重要的方法,它使许多复杂的问题变得简单,容易解决了。

递归特点是:函数或过程调用它自己本身。其中直接调用自己称为直接递归,而将A调用B,B以调用A的递归叫做间接递归。

例题讲解

【例1】 给定n(n>=1),用递归的方法计算1+2+3+4+…+(n-1)+n。

【算法分析】

本题可以用递归方法求解,其原因在于它符合递归的三个条件:

(1)本题是累加问题:当前和=前一次和+当前项,而前一次和的计算方法与其相同,只是数据不同s(n)=s(n-1)+n;

(2)给定n,所以是有限次的递归调用;

(3)结束条件是当n=1,则s=1。

实现代码

#include<iostream>

using namespace std;

int fac(int);                    //递归函数

int main()

{

  int t;

  cin>>t;                    //输入t的值

  cout<<"s="<<fac(t)<<endl;    //计算1到t的累加和,输出结果

}

int fac(int n)

{

  if (n==1) return 1;

  return(fac(n-1)+n);           //调用下一层递归

} 

​ 运行程序,当T=5时,输出结果:S=15,其递归调用执行过程是:(设T=3)

image-20201130171227587

​ 递归调用过程,实质上是不断调用过程或函数的过程,由于递归调用一次,所有子程序的变量(局部变量、变参等)、地址在计算机内部都有用特殊的管理方法——栈(先进后出)来管理,一旦递归调用结束,计算机便开始根据栈中存储的地址返回各子程序变量的值,并进行相应操作。

【例2】 设有N个数已经按从大到小的顺序排列,现在输入X,判断它是否在这N个数中,如果存在则输出:“YES” 否则输出“NO”。

【算法分析】

​ 该问题属于数据的查找问题,数据查找有多种方法,通常方法是:顺序查找和二分查找,当N个数排好序时,用二分查找方法速度大大加快。二分查找算法:

(1) 设有N个数,存放在A数组中,待查找数为X,用L指向数据的高端,用R指向数据的低端,MID指向中间:

(2) 若X=A[MID] 输出 “YES”;

(3)若X<A[MID]则到数据后半段查找:R不变,L=MID+1,计算新的MID值,并进行新的一段查找;

(4) 若X>A[MID]则到数据前半段查找:L不变,R=MID-1,计算新的MID值,并进行新的一段查找;

(5)若L>R都没有查找到,则输出“NO”。

该算法符合递归程序设计的基本规律,可以用递归方法设计。

实现代码:

       #include<iostream>
  #include<cstdlib>
  using namespace std;
  int a[11];
  void search(int,int,int);
  int main()                                             //主程序
  {
    int k,x,L=1,R=10;
    cout<<"输入10个从大到小顺序的数:"<<endl;
    for (k=1;k<=10;k++)
    cin>>a[k];
    cin>>x;
    search(x,L,R); 
    system("pause");                       
  }
  void search(int x,int top,int bot)       //二分查找递归过程
  {
    int mid; 
    if (top<=bot)
      {
        mid=(top+bot)/2;                           //求中间数的位置
             if (x==a[mid]) cout<<"YES"<<endl;                 //找到就输出
        else 
         if (x<a[mid]) search(x,mid+1,bot);    //判断在前半段还是后半段查找
        else search(x,top,mid-1);
      }  
    else cout<<"NO"<<endl;
  }

        

【例3】Hanoi汉诺塔问题

​ 有N个圆盘,依半径大小(半径都不同),自下而上套在A柱上,每次只允许移动最上面一个盘子到另外的柱子上去(除A柱外,还有B柱和C柱,开始时这两个柱子上无盘子),但绝不允许发生柱子上出现大盘子在上,小盘子在下的情况,现要求设计将A柱子上N个盘子搬移到C柱去的方法。

【算法分析】

本题是典型的递归程序设计题。

(1)当N=1 时,只有一个盘子,只需要移动一次:A—>C;

(2)当N=2时,则需要移动三次:

​ A—— 1 ——> B, A —— 2 ——> C, B —— 1——> C.

(3)如果N=3,则具体移动步骤为:

image-20201130171347181

image-20201130171403936

image-20201130171417273

假设把第3步,第4步,第7步抽出来就相当于N=2的情况(把上面2片捆在一起,视为一片):

image-20201130171457631

​ 所以可按“N=2”的移动步骤设计:

​ ①如果N=0,则退出,即结束程序;否则继续往下执行;

​ ②用C柱作为协助过渡,将A柱上的(N-1)片移到B柱上,调用过程mov(n-1, a,b,c);

​ ③将A柱上剩下的一片直接移到C柱上;

​ ④用A柱作为协助过渡,将B柱上的(N-1)移到C柱上,调用过程mov (n-1,b,c,a)。

实现代码:

     #include<iostream>
   using namespace std;
   int k=0,n;
   void mov(int n,char a,char c,char b) 
                                                     //用b柱作为协助过渡,将a柱上的(n)移到c柱上
   {
    if (n==0) return;            //如果n=0,则退出,即结束程序
    mov(n-1,a,b,c );            //用c柱作为协助过渡,将a柱上的(n-1)片移到b柱上
    k++;
    cout <<k<<" :from "<<a <<"-->"<<c<<endl;
    mov(n-1,b,c,a );             //用a柱作为协助过渡,将b柱上的(n-1)移到c柱上
   }
int  main()                                        
   {
    cout<<"n=";
    cin>>n;
    mov(n,'a','c','b'); 
   }



​ 程序定义了把n片从A柱移到C柱的过程mov (n,a,c,b),这个过程把移动分为以下三步来进行:

​ ①先调用过程mov (n-1, a, b, c),把(n-1)片从A柱移到B柱, C柱作为过渡柱;

​ ②直接执行 writeln(a, ’–>’, c),把A柱上剩下的一片直接移到C柱上,;

​ ③调用mov (n-1,b,c,a),把B柱上的(n-1)片从B移到C柱上,A柱是过渡柱。

​ 对于B柱上的(n-1)片如何移到C柱,仍然调用上述的三步。只是把(n-1)当成了n,每调用一次,要移到目标柱上的片数N就减少了一片,直至减少到n=0时就退出,不再调用。exit是退出指令,执行该指令能在循环或递归调用过程中一下子全部退出来。

​ mov过程中出现了自己调用自己的情况,在Pascal中称为递归调用,这是Pascal语言的一个特色。对于没有递归调用功能的程序设计语言,则需要将递归过程重新设计为非递归过程的程序。

【例4】用递归的方法求斐波那契数列中的第N个数

image-20201130171609789

实现代码:

  #include<iostream>
  using namespace std;
  int a[11];
  int fib(int);
  int main()
  {
     int m;
          cin>>m;                              
     cout<<"fib("<<m<<")="<<fib(m);          
  }
  
int fib(int n)
  {
     if (n==0) return 0;                         //满足边界条件,递归返回
     if (n==1) return 1;                         //满足边界条件,递归返回
     return (fib(n-1)+fib(n-2));             //递归公式,进一步递归
  }
//输入 15
//输出 fib(15)=610


【例5】集合的划分

【问题描述】

设S是一个具有n个元素的集合,S={a1,a2,……,an},现将S划分成k个满足下列条件的子集合S1,S2,……,Sk ,且满足:

image-20201130171727222

则称S1,S2,……,Sk是集合S的一个划分。它相当于把S集合中的n个元素a1 ,a2,……,an 放入k个(0<k≤n<30=无标号的盒子中,使得没有一个盒子为空。请你确定n个元素a1 ,a2 ,……,an 放入k个无标号盒子中去的划分数S(n,k)。

【输入样例】setsub.in

​ 23 7

【输出样例】setsub.out

4382641999117305

【算法分析】

先举个例子,设S={1,2,3,4},k=3,不难得出S有6种不同的划分方案,即划分数S(4,3)=6,具体方案为:

{1,2}∪{3}∪{4} {1,3}∪{2}∪{4} {1,4}∪{2}∪{3}

{2,3}∪{1}∪{4} {2,4}∪{1}∪{3} {3,4}∪{1}∪{2}

考虑一般情况,对于任意的含有n个元素a1 ,a2,……,an的集合S,放入k个无标号的盒子中去,划分数为S(n,k),我们很难凭直觉和经验计算划分数和枚举划分的所有方案,必须归纳出问题的本质。其实对于任一个元素an,则必然出现以下两种情况:

​ 1、{an}是k个子集中的一个,于是我们只要把a1,a2,……,an-1 划分为k-1子集,便解决了本题,这种情况下的划分数共有S(n-1,k-1)个;

​ 2、{an}不是k个子集中的一个,则an必与其它的元素构成一个子集。则问题相当于先把a1,a2,……,an-1 划分成k个子集,这种情况下划分数共有S(n-1,k)个;然后再把元素an加入到k个子集中的任一个中去,共有k种加入方式,这样对于an的每一种加入方式,都可以使集合划分为k个子集,因此根据乘法原理,划分数共有k * S(n-1,k)个。

综合上述两种情况,应用加法原理,得出n个元素的集合{a1,a2,……,an}划分为k个子集的划分数为以下递归公式:S(n,k)=S(n-1,k-1) + k * S(n-1,k) (n>k,k>0)。

下面,我们来确定S(n,k)的边界条件,首先不能把n个元素不放进任何一个集合中去,即k=0时,S(n,k)=0;也不可能在不允许空盒的情况下把n个元素放进多于n的k个集合中去,即k>n时,S(n,k)=0;再者,把n个元素放进一个集合或把n个元素放进n个集合,方案数显然都是1,即k=1或k=n时,S(n,k)=1。

因此,我们可以得出划分数S(n,k)的递归关系式为:

S(n,k)=S(n-1,k-1) + k * S(n-1,k) (n>k,k>0)

S(n,k)=0 (n<k)或(k=0)

S(n,k)=1 (k=1)或(k=n)

实现代码

    #include<iostream>
 using namespace std;
 
 int s(int n, int k)                           //数据还有可能越界,请用高精度计算
 {
     if ((n < k) || (k == 0)) return 0;              //满足边界条件,退出
     if ((k == 1) || (k == n)) return 1;
     return s(n-1,k-1) + k * s(n-1,k);            //调用下一层递归
 }
 
 int main()
 {
     int n,k;
     cin >> n >> k;
     cout << s(n,k);
     return 0;
 }

【例6】数的计数(Noip2001)

【问题描述】

我们要求找出具有下列性质数的个数(包括输入的自然数n)。先输入一个自然数n(n≤1000),然后对此自然数按照如下方法进行处理:

不作任何处理;

在它的左边加上一个自然数,但该自然数不能超过原数的一半;

加上数后,继续按此规则进行处理,直到不能再加自然数为止。

输入:自然数n(n≤1000)

输出:满足条件的数

【输入样例】

​ 6 满足条件的数为 6 (此部分不必输出)

​ 16

​ 26

​ 126

​ 36

​ 136

【输出样例】

​ 6

【方法一】

用递归,f(n)=1+f(1)+f(2)+…+f(div/2),当n较大时会超时,时间应该为指数级。

实现代码:

#include<iostream>
using namespace std;
int ans;
void dfs(int m)                           //统计m所扩展出的数据个数
{
    int i;
    ans++;                                  //每出现一个原数,累加器加1;
    for (i = 1; i <= m/2; i++)         //左边添加不超过原数一半的自然数,作为新原数
      dfs(i); 
}
int main()
{
    int n;
    cin >> n;
    dfs(n);
    cout << ans;
    return 0;
} 

【方法二】:用记忆化搜索,实际上是对方法一的改进。设h[i]表示自然数i满足题意三个条件的数的个数。如果用递归求解,会重复来求一些子问题。例如在求h[4]时,需要再求h[1]和h[2]的值。现在我们用h数组记录在记忆求解过程中得出的所有子问题的解,当遇到重叠子问题时,直接使用前面记忆的结果。

实现代码:

#include<iostream>
using namespace std;
int h[1001];
void dfs(int m)
{
    int i;
    if (h[m] != -1) return;         //说明前面已经求得h[m]的值,直接引用即可,不需要再递归
    h[m] = 1;                           //将h[m]置为1,表示m本身为一种情况
    for (i = 1; i <= m/2; i++)
    {
        dfs(i);
        h[m] += h[i];
    }   
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
      h[i] = -1;                         //h数组初始化为-1
    dfs(n);                              //由顶到下记忆化递归求解
    cout << h[n];   
    return 0;
}

【方法三】

​ 用递推,用h(n)表示自然数n所能扩展的数据个数,则h(1)=1, h(2)=2, h(3)=2, h(4)=4, h(5)=4, h(6)=6, h(7)=6, h(8)=10, h(9)=10.分析以上数据,可得递推公式:h(i)=1+h(1)+h(2)+…+h(i/2)。此算法的时间度为O(n*n)。

设h[i]-i按照规则扩展出的自然数个数(1≤i≤n)。下表列出了h[i]值及其方案:

image-20201130172217205

实现代码:

#include<iostream>
using namespace std;
int h[10001];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)   //按照递增顺序计算扩展出的自然数的个数
    {
        h[i] = 1;                        //扩展出的自然数包括i本身
        for (int j = 1; j <= i/2; j++)         
                                 //i左边分别加上1…自然数 按规则扩展出的自然数
          h[i] += h[j]; 
    }
    cout << h[n];
    return 0;
}

【方法四】

是对方法三的改进,我们定义数组s,s(x)=h(1)+h(2)+…+h(x),h(x)=s(x)-s(x-1),此算法的时间复杂度可降到O(n)

实现代码:

#include<iostream>
using namespace std;
int h[1001],s[1001];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        h[i] = 1 + s[i/2];
        s[i] = s[i-1] + h[i];                  //s是h的前缀累加和
    }
    cout << h[n];
    return 0;
}

【方法五】

还是用递推,只要作仔细分析,其实我们还可以得到以下的递推公式:

(1)当i为奇数时,h(i)=h(i-1);

(2)当i为偶数时,h(i)=h(i-1)+h(i/2).

#include<iostream>
using namespace std;
int h[1001];
int main()
{
    int n;
    cin >> n;
    h[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        h[i] = h[i-1];
        if (i % 2 == 0) h[i] = h[i-1] + h[i/2];
    }
    cout << h[n];
    return 0;
}
Default image
LIU
代码是躯体,思想是灵魂

Leave a Reply