一递推概述
递推是一种通过已知条件和重复计算来解决问题的算法思想。它利用计算机高速运算的特征，通过循环结构从初始条件出发逐步推导出问题的解。
递推算法的重点是通过分析，找到相邻项之间的关系，即“递推关系式”(简称“递推式”)，然后循环迭代递推式，得到最终结果。
二递推的实现步骤
1、确定问题的已知条件;
2、找出问题的递推式;
3、选择合适的循环结构实现递推;
4、处理边界条件和特殊情况;
5、输出结果。
- # include <bits/stdc++.h>
- using namespace std;
- // 声明函数 factorial 用于计算整数n的阶乘，返回整数
- int factorial(int n) {
- // 特殊情况处理(思考：省略这里的判断是否影响结果？)
- if (n == 1 || n == 0) return 1;
- // 声明计算结果 ret
- int ret = 1;
- for (int i = 1; i <= n; i++) {
- // 将 i 乘到 ret 中，得到 i！
- ret *= i;
- }
- return ret;
- }
- int main() {
- // 声明阶乘数n，并输入n的值
- int n;
- cin >> n;
- // 调用函数计算阶乘，并输出结果
- cout << factorial(n) << endl;
- return 0;
- }
三斐波那契数列
-
第0项：f(0) = 0；
-
第1项：f(1) = 1；
-
从第2项开始，每一项都等于前两项之和：f(n) = f(n-1) + f(n-2)。
- # include <bits/stdc++.h>
- using namespace std;
- // 声明函数 fibonacci 用于计算第n项的值，返回整数
- int fibonacci(int n) {
- // 特殊情况处理
- if (n < 2) return n;
- // a、b、c 为相邻的3个数
- int a = 0, b = 1, c;
- // 从第2项计算到第n项
- for (int i = 2; i <= n; i++) {
- // 将前两项的和存入第三项
- c = a + b;
- // 更新前两项的值（依次后移）
- a = b;
- b = c;
- }
- return c;
- }
- int main() {
- // 声明项数n，并输入n的值
- int n;
- cin >> n;
- // 调用函数计算斐波那契数列的第n项，并输出结果
- cout << fibonacci(n) << endl;
- return 0;
- }
四
上楼梯问题
类似斐波那契数列的问题有很多，上楼梯问题就是其中之一。
- # include <bits/stdc++.h>
- using namespace std;
- // 声明函数 fib 计算爬上第 n 个台阶的不同走法
- int fib(int n) {
- // 特殊情况处理
- if (n < 3) return n;
- // a、b、c 为相邻三个台阶的不同走法
- int a, b, c;
- a = 1; // 第一个台阶的走法是 1 种
- b = 2; // 第二个台阶的走法是 2 种
- // 使用 for 循环，从第 3 项计算到第 n 项
- for (int i = 3; i <= n; i++) {
- c = a + b; // 计算第三个台阶的走法
- a = b; // 更新第一个台阶的走法
- b = c; // 更新第二个台阶的走法
- }
- return c; // 返回第三个台阶的走法
- }
- int main() {
- // n 为楼梯的台阶数量
- int n;
- // 输入台阶数量 n
- cin >> n;
- // 调用函数 fib 计算爬到第 n 个台阶的不同走法，并输出结果
- cout << fib(n) << endl;
- return 0;
- }
五
错位排序问题
错位排序问题（简称“错排问题”）是指排列中没有任何元素出现在其原始位置上的排列方式。
-
任取一封信，装错的情况：n-1。 -
在剩余的信中，再任取一封信，装错的情况有两种： 1、与上一封信位置互换，接下来就变成了n-2封信的错排问题； 2、不与上一封信位置互换，接下来就成了n-1封信的错排问题。
-
总结递推式：f(n) = (n-1) * [f(n-1) + f(n-2)]。 -
根据递推式，至少确认前两项，才能计算后续项： 1、当只有一封信和一个信封的时候，装错的情况为0，即：f(1) = 0； 2、当有两封信和两个信封的时候，装错的情况为1，即：f(2) = 1。
- # include <bits/stdc++.h>
- using namespace std;
- // 声明函数 misplaced_sort 计算n封信的错排情况
- int misplaced_sort(int n) {
- // 特殊情况处理
- if (n < 3) return n - 1;
- // a、b、c 为相邻的三项
- int a = 0, b = 1, c;
- // 从第3项计算到第n项
- for (int i = 3; i <= n; i++) {
- // 根据递推式计算第三项
- c = (i - 1) * (a + b);
- // 更新前两项的值（依次后移）
- a = b;
- b = c;
- }
- return c;
- }
- int main() {
- // 声明项数n，并输入n的值
- int n;
- cin >> n;
- // 调用错排函数计算n封信的错排情况，并输出结果
- cout << misplaced_sort(n) << endl;
- return 0;
- }
六
倒推问题
倒推是指从后往前反向递推。前面都是从前往后，正向递推。仅仅是递推方向的不同，递推方法相同。
- # include <bits/stdc++.h>
- using namespace std;
- // 声明一维数组存每个施工小队面临的工程数量
- int a[11];
- int n; // n 为施工小队的数量
- int main() {
- cin >> n; // 输入工程队数量：n
- a[n] = n; // 初始化第 n 工程队面临的任务数量
- // 使用 for 循环从 n~1 倒序迭代
- for (int i = n; i > 1; i--) {
- // 根据递推式倒推计算前一项的值
- a[i-1] = 2 * a[i] + 2 * (i - 1);
- }
- // 第 1 工程队面临的任务数量就是工程总量
- cout << a[1] << endl;
- return 0;
- }
