递推
课上练习
知识总结
L2-04.递推-知识总结
递推-知识总结 递推概念 递推是一种解决问题的方式，通常递推解题的形式为使用循环一步一步推出结果。因为递推求解的过程常常可以概括为一个递推公式。只不过有些递推公式是十分简单的，而有些复杂的递推公式里会包含各种条件判断。
常见的使用递推求解的场景有： 数列计算 贪心问题 动态规划问题 目前本节课会把重点集中在数列计算上。
算法评价 时间复杂度：O(n) 空间复杂度：若使用数组则为O(n)
递推示例 等差数列 递推公式：a[n] = a[n - 1] + d
a[0] = 0;
for (int i = 1; i < n; i++) { //注意当使用i - 1作为下标时，循环应该从1开始
a[i] = a[i - 1] + d;
}等比数列 递推公式：a[n] = a[n-1] * q
a[0] = 1;
for (int i = 1; i < n; i++) { //注意当使用i - 1作为下标时，循环应该从1开始
a[i] = a[i - 1] * q;
}斐波那契数列 递推公式：f[n] = f[n-1] + f[n-2]
f[0] = 1;
f[1] = 1;
for (int i = 2; i < n; i++) { //注意当使用i - 2作为下标时，循环应该从2开始
f[i] = f[i - 1] * f[n - 2];
}递推求和 sum(n) = n + (n - 1) + (n - 2) + ... + 3 + 2 + 1 递推公式：s[n] = s[n-1] + n
s[0] = 0;
for (int i = 1; i < n; i++) { //注意当使用i - 1作为下标时，循环应该从1开始
s[i] = s[i - 1] + i;
}递推求阶乘 n! = n × (n - 1) × (n - 2) × ... × 3 × 2 × 1 递推公式：f[n] = f[n-1] * n
f[0] = 0;
for (int i = 1; i < n; i++) { //注意当使用i - 1作为下标时，循环应该从1开始
f[i] = f[i - 1] * i;
}️课后作业
☝️总结作业
总结作业非常重要，请务必认真完成✔️
- 递推的核心思想是什么？
- 斐波那契数列的递推公式是什么？
- 求和的递推公式是什么？
- 求阶乘的递推公式是什么？
✌️编程作业
考试只有一次提交机会，请务必本地检查正确后再提交❇️
👌编程作业标准答案
请在AC后或者思考15分钟没有进展后查看，不可抄代码❇️
L2045题解+参考代码
L2045题解+参考代码 题目链接 平方根：L2045
题解 题目要求我们用一种迭代方法求一个正数 x 的平方根近似值，迭代的次数为 n。迭代公式为： y[i] = (y[i-1] + x / y[i-1]) / 2 初始解为 y[0]=1，我们需要迭代 n 次，然后输出 y[n]的值，并保留三位小数。
算法步骤 读取输入：读取两个整数 x 和 n，分别表示要求平方根的正数和迭代次数。 初始化：设置初始解 y0=1。 迭代计算：使用迭代公式更新 y 的值，共迭代 n 次。 输出结果：输出 y 的近似值，保留三位小数。
示例代码 这里是使用 C++ 实现的示例代码：
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // 读取输入
6 int x, n;
7 cin >> x >> n;
8
9 // 初始化初始解
10 double y = 1.0;
11
12 // 迭代计算
13 for (int i = 0; i < n; ++i) {
14 y = (y + x / y) / 2.0;
15 }
16
17 // 输出结果，保留三位小数
18 cout << fixed << setprecision(3) << y << endl;
19
20 return 0;
21}L2046题解
L2046题解+参考代码 题目链接 上台阶：L2046
题解 使用一个数组f[n]保存上n阶台阶的走法总数。 使用递推推出数组的所有数值。 使用一个while循环读取输入的台阶数，输出该该台阶数的方法数，直到输入为0表示结束。 需要注意的是最终的结果可能会大于int，需要使用long long存储。
算法步骤 递推公式： 设f[n]为上n阶楼梯的走法总数。 上楼时可以一步上1阶、2阶或3阶，因此递推关系为：f(n)=f(n−1)+f(n−2)+f(n−3) 基本情况： f[0] = 1，表示没有台阶时有一种走法（即不动）； f[1] = 1，表示只有一个台阶时有一种走法； f[2] = 2，表示有两个台阶时有两种走法（一步一步或一次两步）。
示例代码 这里是使用 C++ 实现的示例代码：
1#include <bits/stdc++.h>
2using namespace std;
3
4long long f[72];
5
6int main() {
7 f[1] = 1;
8 f[2] = 2;
9 f[3] = 4;
10 for (int i = 4; i <= 71; ++i) {
11 f[i] = f[i - 1] + f[i - 2] + f[i - 3];
12 }
13
14 int n;
15 while (cin >> n && n) {
16 cout << f[n] << endl;
17 }
18
19 return 0;
20}