概述
递推法是一种根据递推关系进行问题求解的方法，常用来进行序列计算
根据初始条件，按照一定的规律逐项进行计算，直到得到结果
递推法正推和逆推
- 正推
小规模问题的解递推到大规模问题的解 - 逆推
大规模问题的解递推到小规模问题的解
例题
猴子吃桃
题目：猴子每天吃一半多一个的桃子，第十天只有一个桃子，问原来有多少个。
分析：
int peach(int i){
if(i==1)
return 1;
else
return (peach(i-1)+1)*2;
}
斐波那契数列
题目：一对兔子放在围栏中，第二个月起，生一对兔子，新兔子下个月起生一对兔子，一年后有多少对兔子？
\[F_n=\begin{cases} 1 \quad n=1,2\\ F_{n-1}+F_{n-2} \quad n\gt 2 \end{cases} \]int Fib(int n)
{
if(n==1||n==2)
return 1;
else
return Fib(n-1)+Fib(n-2);
}
错排问题
问题：n封信放进n个有地址的信封，全部放错的概率是？
分析：
| 信的数量 | 错排可能 |
|---|---|
| 1 | 0 |
| 2 | 1 |
| n | \((n-1)\times F_{n-1}+F_{n-2}\) |
int epp(int n){
if(n==1) return 0;
if(n==2) return 1;
else return (n-1)*(epp(n-1)+epp(n-2));
}
整数拆分
问题：对于大于2的整数，用2的整数次幂进行拆分，有多少种拆分方式？
分析：
2->(1,1),(2)
3->(1,1,1),(1,2)
4->(1,1,1,1),(1,1,2),(2,2),(4)
5->(1,1,1,1,1),(1,1,1,2),(1,2,2),(4,1)
6->(1,1,1,1,1,1),(1,1,1,1,2),(1,1,2,2),(1,1,4),(2,2,2),(2,4)
分析可知，当n为奇数时，和n-1数量一样；当n为偶数时，为n/2中所有元素翻倍以及n-1所有的元素补充上1；
int div(int n){
if(n==1){
return 1;
}
else if(n%2==0){
return div(n/2)+div(n-1);
}
else{
return div(n-1);
}
}
杨辉三角
问题：杨辉三角是二项式展开的系数的三角形，打印n阶杨辉三角
分析：每行的开头和结束都是1，其余为上一行同一列和前一列的和；
int main()
{
int n;
cin>>n;
int a[n][n];
for(int i=0;i<n;i++)
{
for(int j=0;j<=i;j++)
{
if(j==0||j==i)
a[i][j]=1;
else
a[i][j]=a[i-1][j-1]+a[i-1][j];
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
乘法结合问题
问题：在其前后次序不变的情况下，每次只对两个元素进行乘法，以括号决定乘的先后顺序，有多少种不同的相乘方式？
分析：
括号匹配问题，将左括号看作入栈，右括号看作出栈，题目既有多少出栈顺序。计算catalan数即可
catalan数的通项公式为
\(C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}\)，其中\(\binom{a}{b}\)表示从a个元素中选取b个元素的组合数
递推公式为
\(C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}, n > 0\)
long long catalan(int n) {
// 如果n为0或1，返回1
if (n == 0 || n == 1) {
return 1;
}
// 否则，根据递推方程计算并返回结果
long long result = 0;
for (int k = 0; k < n; k++) {
result += catalan(k) * catalan(n - 1 - k);
}
return result;
}
练习
-
- 问题：6人参加会议，入场是随意把帽子挂在衣架上，走的时候顺手拿一顶，问拿对的概率
- 分析：
- 当5人拿对，只剩下一个帽子，此人拿对的概率是1；
- 当4人拿对，只剩下2个帽子，2人拿对的概率是1/2；
- ......
- 第一人开始拿，此人拿对的概率是1/6
- 通过递归计算
- 实现
double proba(double n){ if(n==1) return 1; return (1/n)*proba(n-1); }
-
- 问题：已知数列递推式：\(a_1=1;a_{2i}=a_i+1,a_{2i+1}=a_i+a_{i+1}\),求第n项已经前n项最大值
- 分析：
- 使用数组实现递推，偶数位为i/2位的值+1，奇数为i/2位的值+i+1位的值；
- 过程中记录最大值，运算结束后输出；
- 实现：
int sl(int n, int &max) { int num[n+1]={0}; num[1] = 1; for (int i = 2; i <= n; i++) { if (i % 2 == 0) { num[i] = num[i/2]+1; } else { num[i] = num[i/2] + num[i/2+1]; } if (num[i] > max) { max = num[i]; } } return num[n]; }
-
- 问题：一只猴子要爬上30级台阶，一步可以跳1级或三级台阶，共有多少种跳法？
- 分析：若猴子当前在第n阶，则上一次可能在n-1阶或n-3阶，也就是说，到达第n阶的跳法f(n)=f(n-1)+f(n-3)
- 实现：
int mk(int n) { if (n==1||n==2)return 1; if (n==3)return 2; return mk(n-1)+mk(n-3); }
-
- 问题：假设核反应堆有α和β两种粒子，每秒钟一个α可以分裂为3个β，一个β可以分裂为1个α和两个β。t=0时只有一个α，t秒的时候有多少α和多少β？
- 分析：建立两个数组，依次计算
- 实现：
void particle(int t,int &alphas,int &betas) { int alpha[t]={0}; int beta[t]={0}; alpha[0]=1; for (int i = 1; i <= t; i++) { beta[i]=alpha[i-1]*3+beta[i-1]*2; alpha[i]=beta[i-1]; } alphas=alpha[t]; betas=beta[t]; }
-
- 问题：设x和y为非负整数，对集合\(\{2^x3^y|x\geqslant0,y\geqslant0\}\),求集合中小于整数n的元素个数，并求元素从小到大的排序的第m项元素
- 分析：找到由1到n遍历，对2和3连续除，若结果为1，则表示该数为2和3的倍数（符合条件）
- 实现：
int main() { int n,m; while(cin>>n>>m) { int a[100001]; int k=0; for(int i=1;i<=n;i++) { int temp=i; while(temp%2==0) temp/=2; while(temp%3==0) temp/=3; if(temp==1) a[++k]=i; } cout<<k<<endl<<a[m]<<endl; } } -
- 题目：\(2\times n\)的长方形，用若干个\(1\times 2\)的骨牌铺满，\(n=3\)时铺满方格共有3种方法，求对于给定的n，有多少种铺法？
- 分析：
- 当\(n=1\)时，只有一种铺法，即\(f(1)=1\)；
- 当\(n=2\)时，有两种铺法，即\(f(2)=2\)。
- 当\(n>2\)时，我们可以考虑最右边一列的情况
- 如果最右边一列是竖着放一个骨牌，则剩下的部分是一个\(2\times (n-1)\)的长方形方格，有\(f(n-1)\)种铺法；
- 如果最右边一列是横着放两个骨牌，则剩下的部分是一个\(2\times (n-2)\)的长方形方格，有\(f(n-2)\)种铺法。
- 因此，我们可以得到递推公式：\(f(n)=f(n-1)+f(n-2)\)
- 实现：
int domino(int n) { if (n==1)return 1; if (n==2)return 2; return domino(n-1)+domino(n-2); }
- 题目：\(2\times n\)的长方形，用若干个\(1\times 2\)的骨牌铺满，\(n=3\)时铺满方格共有3种方法，求对于给定的n，有多少种铺法？