YbtOJ「基础算法」第1章 递推算法

YbtOJ 大全

【例题1】错排问题

设 $f[n]$ 表示 $n$ 个数时的合法方案数。初始化 $f[1]=0,f[2]=1$。当 $n\ge 3$ 时，我们考虑一个位置 $k$，把 $n$ 放在位置 $k$ 上 $(k\ne n)$，共有 $n-1$ 种方法。接下来分两类讨论。

$1.$ 如果 $k$ 放在了位置 $n$ 上，相当于 $k$ 和 $n$ 自己颠倒，和剩下的 $n-2$ 的数无关，此时的合法方案数是 $f[n-2]$。

$2.$ 如果 $k$ 没有放在位置 $n$ 上，相当于 $n$ 这个数放的位置是合法的，把 $k$ 看成 $n$，位置 $n$ 看成 $k$ 对应的位置 $k1$，$k$ 没有放在 $k1$ 这个位置，就相当于是 $n-1$ 个数的子问题，此时合法的方案数是 $f[n-1]$。

所以递推式 $f[n]=(n-1)\times (f[n-1]+f[n-2])$ $(n\ge 3)$

#include 
#include 
#include 
#include 
#include 
#define re register
#define int long long
#define rep(a,b,c)  for(re int a(b) ; a<=c ; ++a)
#define drep(a,b,c) for(re int a(b) ; a>=c ; --a)
using namespace std;
inline int read(){
   
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
   if(ch == '-') f=-1 ; ch=getchar();}
    while(ch>='0'&&ch<='9'){
   x=(x<<1)+(x<<3)+(ch^48) ; ch=getchar();}
    return x*f;
}
const int M = 100;
int n;
int f[M];
signed main(){
   
    n = read();
    f[1] = 0,f[2] = 1;
    rep(i,3,n) f[i] = (i-1)*(f[i-1]+f[i-2]);
    printf("%lld\n",f[n]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

【例题2】传球游戏

设 $f[i][j]$ 表示球在第 $i$ 个人手中，传了 $j$ 次的方案数，初值 $f[1][0]=1$。

$1.$ 当 $i=1$ 时，$i$ 与 $n$ 和 $2$ 相邻，$f[i][j]=f[n][j-1]+f[2][j-1]$

$2.$ 当 $i=n$ 时，$n$ 与 $n-1$ 和 $1$ 相邻，$f[i][j]=f[1][j-1]+f[n-1][j-1]$

$3.$ 其余情况，$f[i][j]=f[i-1][j-1]+f[i+1][j-1]$

注意要先循环 $j$，因为 $f[i][j]$ 对于 $j$ 的转移只和 $j-1$ 有关，而对于 $i$ 的转移不仅仅只有一种情况。最后的答案就是 $f[1][m]$，要传回第一个人手中。

#include 
#include 
#include 
#include 
#include 
#define re register
#define int long long
#define rep(a,b,c)  for(re int a(b) ; a<=c ; ++a)
#define drep(a,b,c) for(re int a(b) ; a>=c ; --a)
using namespace std;
inline int read(){
   
    int x=0,f=1;
1
2
3
4
5
6
7
8
9
10
11
12