递推递归 | 基础算法

递归

C++中，函数里面可以嵌套调用函数：

cpp

int fun1()
{
    return 1;
}
int fun2()
{
    return fun1()+2;
}
int main()
{
    cout<<fun2()<<endl;
}

也可以在函数里调用自己，但是一定要有结束的情况：

cpp

int fac(int x)
{
    if(x==1) return 1;
    else return x*fac(x-1);
}
int main()
{
    cout<<fac(3)<<endl;
}

如上面这个函数，效果是输出

f a c (3) = 3 * f a c (2) = 3 * 2 * f a c (1) = 3 * 2 * 1

递归问题一般是直接从整体问题去考虑，把整体问题分解成几个同类型的小规模问题。

比如斐波那契数列：

$f_{n} = f_{n - 1} + f_{n - 2}$

可以写成：

cpp

int fib(int n)
{
	if(n<=2) return 1;
    return fib(n-1)+fib(n-2);
}
int main()
{
    int n;cin>>n;
    cout<<fib(n)<<endl;
}

每个函数分为两个分支，所以是时间复杂度是 $O (2^{n})$

我们评测机通常一秒能跑 $5 e 7$ 左右，也就是说，如果 $n = 1 e 6$ ，那么 $O (n l o g n)$ 时间复杂度的方法是极限，如果是 $O (n^{2})$ 的将会超时。

斐波那契有没有快速一点的方法？有的：

f i b (5) = f i b (4) + f i b (3) = (f i b (3) + f i b (2)) + (f i b (2) + f i b (1)) = ((f i b (2) + f i b (1)) + 1) + (1 + 1)

看，虽然分了很多次，但其实实际上访问到的fib(x)中x的值不多，我们可以用数组记录fib(x)的值是多少，下次再访问到直接返回数组的值：

cpp

int f[110];
int fib(int n)
{
    if(f[n]!=0) return f[n];
    if(n<=2) return 1;
    f[n]=fib(n-1)+fib(n-2);
    return f[n];
}

这样的话，每个位置实际上只花了 $O (1)$ 的时间，当重复进入到相同的位置会直接返回答案，一共也就只有 $1 \sim n$ 这么多位置，所以时间复杂度变成 $O (n)$ 。

P1464 Function

对于一个递归函数 $w (a, b, c)$

如果 $a \leq 0$ 或 $b \leq 0$ 或 $c \leq 0$ 就返回值$ 1$。
如果 $a > 20$ 或 $b > 20$ 或 $c > 20$ 就返回 $w (20, 20, 20)$
如果 $a < b$ 并且 $b < c$ 就返回$ w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)$。
其它的情况就返回 $w (a - 1, b, c) + w (a - 1, b - 1, c) + w (a - 1, b, c - 1) - w (a - 1, b - 1, c - 1)$

这是个简单的递归函数，但实现起来可能会有些问题。当 $a, b, c$ 均为 $15$ 时，调用的次数将非常的多。你要想个办法才行。

注意：例如 $w (30, - 1, 0)$ 又满足条件 $1$ 又满足条件 $2$ ，请按照最上面的条件来算，答案为 $1$ 。

直接按题目给出的条件来递归：

cpp

#include<bits/stdc++.h>
using namespace std;
int dp[22][22][22];//记录已经到过的位置的答案
int w(int a,int b,int c)
{
    if(a<=0||b<=0||c<=0) return 1;
    if(a>20||b>20||c>20) return w(20,20,20);
    if(dp[a][b][c]) return dp[a][b][c];
    int ret=0;
    if(a<b&&b<c) ret=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    else ret=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
    dp[a][b][c]=ret;
    return ret;
}
int main()
{
    int a,b,c;cin>>a>>b>>c;
    cout<<w(a,b,c)<<endl;
    return 0;
}

当加入了 dp 数组来记录答案，每个位置只会求解一次，所以时间复杂度是 $O (20 * 20 * 20)$ 。

P1498 南蛮图腾

输出一个大小为 $n$ 的南蛮图腾 $1 \leq n \leq 10$

 /\
/__\
  
   /\
  /__\
 /\  /\
/__\/__\

       /\
      /__\
     /\  /\
    /__\/__\
   /\      /\
  /__\    /__\
 /\  /\  /\  /\
/__\/__\/__\/__\

从上到小分别是大小为 1~3 的。

可以看出大的图腾是由三个小的图腾拼起来的。

每次用一个函数 void draw(int x,int y,int n) 来画一个以 (x,y) 为左上角，大小为 n 的图腾，这个图腾又可以分成三个大小为 n-1 的图腾。

cpp

void draw(int x,int y,int n)//以(x,y)为左上角，大小为n的图腾
{
	if(n==1)
    {
        a[x][y+1]='/';
        a[x][y+2]='\\';//单独一个\是转义符号，比如\n代表换行，如果要输出需要打两个\\
        a[x+1][y]='/';
        a[x+1][y+1]=a[x+1][y+2]='_';
        a[x+1][y+3]='\\';
        return;
    }
    draw(x,y+(1<<(n-1)),n-1);//上面
    draw(x+(1<<(n-1)),y,n-1);//左下
    draw(x+(1<<(n-1)),y+(1<<n),n-1);//右下
}

P1157 组合的输出

排列与组合是常用的数学方法，其中组合就是从 $n$ 个元素中抽出 $r$ 个元素（不分顺序且 $r \leq n \leq 21$ ），我们可以简单地将 $n$ 个元素理解为自然数 $1, 2, \dots, n$ ，从中任取 $r$ 个数。

现要求你输出所有组合。

例如 $n = 5, r = 3$ ，所有组合为：

$123, 124, 125, 134, 135, 145, 234, 235, 245, 345$ 。

设一个递归函数：void dfs(int k) 表示当前已经选择了 k 个数字。

在函数里还需要知道哪些数字已经选了，哪些数字还没选。

设置一个全局数组 vis ，如果 vis[i]=1 表示数字 i 已经选了。

cpp

int vis[22],a[22];
void dfs(int k)
{
	if(k==r)//已经选够了
	{
		for(int i=1;i<=r;++i)
        {
            cout<<a[i]<<' ';
        }
        cout<<'\n';
        return;//输出之后就返回
	}
    for(int i=1;i<=n;++i)
    {
        if(vis[i]) continue;//如果这个数字已经被选过了，跳过。
        //这一步选这个数字
        vis[i]=1;
        a[k+1]=i;
        dfs(k+1);
        //当尝试过这种情况之后，要把刚才的影响消除掉，也叫回溯
        //回溯是因为数组是全局数组，不能因为这一次尝试影响其他尝试。
        vis[i]=0;
        a[k+1]=0;
    }
}

递推

对于斐波那契这种数列问题，递归是解析 f[n] 由哪些部分组成，然后向下求解。

而递推是从 f[1] 开始从小到大求到 f[n]。

初始条件有 f[1]=f[2]=1

由小的去推大的：

$f [i] = f [i - 1] + f [i - 2]$

cpp

for(int i=3;i<=n;++i) f[i]=f[i-1]+f[i-2]

递推问题的递推方程一般是在求解 f[i] 的时候，考虑最后一步是怎么操作的，然后把除去最后一步的部分看作一个小规模问题。

台阶问题：

有 $n$ 级台阶，一步可以跨一级或两级，有多少种不同的方法迈到第 $n$ 级台阶？

我们设：f[n] 表示迈到第 $n$ 级台阶，有多少种不同的方法。

考虑最后一步跨了几级台阶：

如果只跨了一级，那么还需要迈 $n - 1$ 级

如果跨了两级，那么还需要迈 $n - 2$ 级

所以：

$f [n] = f [n - 1] + f [n - 2]$

边界： $f [0] = f [1] = 1$

P1990 覆盖墙壁

你有一个长为 $N$ 宽为 $2$ 的墙壁，给你两种砖头：一个长 $2$ 宽 $1$ ，另一个是 L 型覆盖 $3$ 个单元的砖头。如下图：

0  0
0  00

砖头可以旋转，两种砖头可以无限制提供。你的任务是计算用这两种来覆盖 $N \times 2$ 的墙壁的覆盖方法。例如一个 $2 \times 3$ 的墙可以有 $5$ 种覆盖方法，如下：

012 002 011 001 011  
012 112 022 011 001

注意可以使用两种砖头混合起来覆盖，如 $2 \times 4$ 的墙可以这样覆盖：

0112
0012

给定 $N$ ，要求计算 $2 \times N$ 的墙壁的覆盖方法。由于结果很大，所以只要求输出最后 $4$ 位。例如 $2 \times 13$ 的覆盖方法为 $13465$ ，只需输出 $3465$ 即可。如果答案少于 $4$ 位，就直接输出就可以，不用加前导 $0$ ，如 $N = 3$ 时输出 $5$ 。

$1 \leq N \leq 10^{6}$ 。

我们称长 $2$ 宽 $1$ 的砖头为一字型砖头。

从左到右按列覆盖墙壁，当前已经覆盖到了 1~i 列，其中前 i-1 列都完全覆盖了，第 $i$ 列的墙壁有两种情况：

（1）完全覆盖了

（2）覆盖了其中一个位置。

其他情况，都可以变成这两种情况之一。

设 f[i][0]/f[i][1] 表示第 i 列完全覆盖/覆盖了其中一个位置的情况数。

对每个状态，考虑达成当前状态的最后一步用的是什么类型的砖头：

首先是 f[i][0]：

（1）用一字型砖头：

可以竖着放一列，覆盖一列 f[i][0]+=f[i-1][0]。

两个横着的并排，覆盖两列 f[i][0]+=f[i-2][0]。

（2）用 L 型砖头：

如果之前是覆盖了上一列的其中一个位置，加一个 L 可以补全：f[i][0]+=f[i-1][1]。

其次是 f[i][1]：

（1）用一字型砖头：

如果之前覆盖了上一列的其中一个位置，一字型横着放在另一行：f[i][1]+=f[i-1][1]。

（2）用 L 型砖头：

如果之前完全覆盖，可以覆盖一列和一个位置，单独覆盖的位置可以决定在哪一行：f[i][1]+=2*f[i-2][0]

最后的答案是 f[n][0]

cpp

f[0][0]=f[1][0]=1;
for(int i=2;i<=n;++i)
{
    f[i][0]=(f[i-1][0]+f[i-1][1]+f[i-2][0])%10000;
    f[i][1]=(2*f[i-2][0]+f[i-1][1])%10000;
}
cout<<f[n][0]<<endl;

练习题

P1002 [NOIP2002 普及组] 过河卒

P1028 [NOIP2001 普及组] 数的计算

P1010 [NOIP1998 普及组] 幂次方

P3612 [USACO17JAN] Secret Cow Code S

P1928 外星密码

递归 ​

递推 ​

练习题 ​

递归

递推

练习题