递推总结
来自重庆宏帆八中初2022级1班的一名学生
被某郭茂老师被迫强行自愿写总结!!!
什么是递推？
f(n) = 2f(n - 1) + 2
-
递推算法是一种
简单的算法,即通过已知条件,利用特定关系得出中间推论,直至得到结果的算法.递推算法分为顺推和逆推两种. -
递推不同于递归,相对于递归算法,递推算法免除了数据进出栈的过程,也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值.
简单的顺推
所谓顺推法是从已知条件出发,逐步推算出要解决的问题的方法叫顺推.
简单的逆推
所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件,即顺推法的逆过程,称为逆推.
五种典型的递推关系
Fibonacci数列
在所有的递推关系中,Fibonacci数列是最常见的.
看着代码,好像没啥问题,但你要仔细一想就会发现问题,第i月的卵的数量不是这样的,因为有些之前的卵已经长成虫,而我们再次算上了这些变成虫的卵,所以就多算了,而上面的代码就犯了这个错误,正确代码应该减去已经长成虫的卵.
代码如下
#include <cstdio>
int main() {
long long f[55],g[55]; // f[i]表示第i月成虫数量,g[i]表示第i月新产下的卵
g[0] = 0;
f[0] = 0;
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
for (int i = 1;i <= x; i++) {
f[i] = 1;
g[i] = 0; //初始化
}
g[x + 1] = y;
f[x + 1] = 1;
for (int i = x + 2; i <= z + 1; i ++) {
//f[i] = f[i - x - 1] + f[i - x - 2] * y + g[i - x - 2];
f[i] = f[i - 1] + g[i - 2];
g[i] = g[i - x] + (f[i - x] - f[i - x - 1]) * y;
}
printf("%lld",f[z + 1]);
return 0;
}
Hanoi塔问题
分析
设h(n)为第n个盘子从a柱移到c柱所需移动的盘次.显然,当n = 1时,只需把a柱上的盘子直接移动到c柱就可以哦,故h(1) = 1.当n = 2时,先将a柱上面的小盘子移动到b柱上面去;然后将大盘子从a柱移到c柱:最后,将b柱上的小盘子移到c柱上,共三个盘次,故h(2) = 3.以此类推,当a柱上有n个盘子,总是先借助c柱把上面的n - 1个盘子移动到b柱,然后再把a柱最下面的盘子移动到c柱上;再借助a柱把b柱上的n - 1个盘子移动到c柱上;总共移动h(n - 1) + 1 + h(n - 1)个盘次.所以可得到h(n) = 2h(n - 1) + 1,边界条件:h(1) = 1.
代码如下
#include <cstdio>
long long h[65];
int main() {
int n;
scanf("%d",&n);
h[1] = 1;
for (int i = 2;i <= n; i++) {
h[i] = 2 * h[i - 1] + 1;
}
printf("%lld",h[n]);
return 0;
}
当然你也可以用递归的方法做,通过推理可以推出h(n) = 2 ^ n - 1.
代码如下
#include <cstdio>
#include <cmath>
int main() {
long long n;
scanf("%lld",&n);
long long sum;
sum = pow(2 , n) - 1;
printf("%lld",sum);
return 0;
}
平面分割问题
分析
当平面上已有n - 1条曲线将平面分割成a(n - 1)个区域后,第n条曲线每与曲线相交一次,就会增加一个区域,因为平面上已经有了n - 1条封闭曲线,且第n条曲线与已有的每一条封闭曲线恰好交于两点,且不会与任两条曲线交于同一点,故平面上增加 2(n - 1) 个区域,加上已有的 a(n - 1) 个区域,一共有a(n - 1) + 2(n - 1) 个区域.所以本题的递推关系是 a(n) = a(n - 1) + 2 (n - 1),边界条件是a(1) = 1.
代码如下
#include <cstdio>
int a[46346];
int main() {
int n;
a[1] = 2;
scanf("%d",&n);
for (int i = 2;i <= n; i++) {
a[i] = a[i - 1] + 2 * (i - 1);
}
printf("%d",a[n]);
return 0;
}
当然你还是可以用递归的方法来做.可以推出公式 a(n) = n * (n - 1) + 2.
代码如下
#include <cstdio>
int main() {
int n;
scanf("%d",&n);
printf("%d",n * n - n + 2);
return 0;
}
Catalan数
分析
令一个k值,k从2开始到n - 1结束,剩下的是 n - k + 1 边形,令f(n)为n边形的划分方式,那么 f(n) = f(k) * f(n - k + 1) (k从2开始,到n - 1结束)想一下为什么要用乘法
代码如下
#include <cstdio>
long long sum;
long long f[42];
int main() {
int n;
scanf("%d",&n);
f[1] = 1;
f[2] = 1;
if (n == 1 || n == 2) {
printf("0");
return 0;
}
for (int i = 1;i <= n; i++) {
for (int k = 2 ; k <= i - 1; k++) {
f[i] += f[k] * f[i - k + 1];
}
}
printf("%lld",f[n]);
return 0;
}
第二类stirling数
分析
记f(n, m)为n个球,m个盒子的方法总数.从中取出一个球k有以下情况.当k独占一个盒子,方案数为f(n - 1,m- 1);当k与其他球共享一个盒子,方案数:m * f(n-1,m).那么一共有 f(n - 1,m - 1) + m * f(n - 1,m) 种方法.即 f(n) = f(n - 1,m - 1) + m * f(n - 1,m) 种方法.
代码如下
#include <cstdio>
long long a[25][25];
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (i == j) {
a[i][j] = 1;
} else {
a[i][j] = a[i - 1][j - 1] + j * a[i - 1][j];
}
}
}
printf("%lld", a[n][m]);
return 0;
}
