Day2 蓝桥杯省赛冲刺精炼刷题 —— 递归与递推

一、3.汉诺塔 - 蓝桥云课

算法代码： 

#include <iostream>
using namespace std;int cnt = 0;  // 计数器
int m;         // 用于存储第 m 步// 递归解决汉诺塔问题
void hanoi(string A, string B, string C, int n) {if (n == 1) {cnt++;if (cnt == m) {  // 如果找到了第 m 步cout << "#" << n << ": " << A << "->" << C << endl;}} else {hanoi(A, C, B, n - 1);  // 第一步cnt++;if (cnt == m) {  // 如果找到了第 m 步cout << "#" << n << ": " << A << "->" << C << endl;  // 第二步}hanoi(B, A, C, n - 1);  // 第三步}
}int main() {int n;  // 盘子的数量cin >> n >> m;  // 读取盘子数量和目标步骤hanoi("A", "B", "C", n);  // 递归调用汉诺塔函数cout << cnt << endl;  // 输出递归的总步数return 0;
}

        这段代码实现了汉诺塔问题的求解，具体功能是找出将N个盘子从A杆移动到C杆的过程中，第M步的具体移动操作，并输出最少移动步数。以下是代码的详细解释：

代码功能

1. 输入处理：读取两个整数N（盘子数量）和M（目标步数）。

2. 递归求解：通过递归函数hano模拟汉诺塔的移动过程，并在过程中检查是否到达第M步。

3. 输出结果：如果找到第M步，输出该步的具体操作；最后输出最少移动步数。

参数传递的意义

函数hano的参数为string A, string B, string C, int n，其中：

• A：起始杆，初始为"A"。

• B：辅助杆，初始为"B"。

• C：目标杆，初始为"C"。

• n：当前需要移动的盘子数量。

        这些参数的设计是为了在递归过程中动态跟踪盘子的移动路径。每次递归调用时，起始杆、辅助杆和目标杆的角色会发生变化，从而确保盘子能够正确移动。

递归逻辑

1. 基本情况（n == 1）：直接将最上面的盘子从起始杆A移动到目标杆C，并增加步数cnt。如果当前步数是M，则输出该步的操作。

2. 递归情况：

   • 将上方的n-1个盘子从A移动到B（借助C作为辅助杆）。

   • 将第n个盘子从A移动到C，并增加步数cnt。如果当前步数是M，则输出该步的操作。

   • 将n-1个盘子从B移动到C（借助A作为辅助杆）。

示例分析

以输入3 2为例：

1. 第一次递归调用hano("A", "C", "B", 2)，将前两个盘子从A移动到B。

   • 在移动过程中，第2步是将编号为2的盘子从A移动到B，因此输出#2: A->B。

2. 最少移动步数为2^3 - 1 = 7，故最终输出7。

总结

        通过递归和参数动态调整，代码高效地模拟了汉诺塔的移动过程，并在过程中捕获目标步数的操作。最少移动步数为2^N - 1，这是汉诺塔问题的经典解。

---

二、1.全排列的价值 - 蓝桥云课 

算法代码：

#include <iostream>using namespace std;
const int N = 1e6+10;
int f[N];
const int MOD = 998244353;int main() {int n;cin >> n;f[1] = 0;int p = 1; // 代表阶乘for (int i = 1; i < n; ++i) {p = 1ll * p * i % MOD;f[i + 1] = 1ll * i * (i + 1) / 2 % MOD * p % MOD + 1ll * f[i] * (i + 1) % MOD;f[i + 1] %= MOD; }cout << f[n] << '\n';return 0;
}

解析： 

---

三、1.奇妙变换 - 蓝桥云课 

算法代码：

#include <iostream>
using namespace std;const int MOD = 998244353;int f(int x) {if (x > 10) {return (1LL * 2 * x * f(x - 6)) % MOD;} else {return x * (x - 1) % MOD;}
}int main() {int n;cin >> n;cout << f(n) << endl;return 0;
}

 解析：

 动态规划（优化）

使用动态规划避免递归：

#include <iostream>
#include <vector>
using namespace std;const int MOD = 998244353;int main() {int n;cin >> n;if (n <= 10) {cout << n * (n - 1) % MOD << endl;return 0;}vector<int> dp(n + 1);for (int i = 1; i <= 10; ++i) {dp[i] = i * (i - 1) % MOD;}for (int i = 11; i <= n; ++i) {dp[i] = 1LL * 2 * i * dp[i - 6] % MOD;}cout << dp[n] << endl;return 0;
}

空间优化动态规划

进一步优化空间，只保存最近的 6 个值：

#include <iostream>
#include <vector>
using namespace std;const int MOD = 998244353;int main() {int n;cin >> n;if (n <= 10) {cout << n * (n - 1) % MOD << endl;return 0;}vector<int> dp(6); // dp[0] to dp[5] represent f(i-5) to f(i)for (int i = 1; i <= 10; ++i) {dp[i % 6] = i * (i - 1) % MOD;}for (int i = 11; i <= n; ++i) {dp[i % 6] = 1LL * 2 * i * dp[(i - 6) % 6] % MOD;}cout << dp[n % 6] << endl;return 0;
}

验证

对于 n=15:

1. f(9)=9×8=72

2. f(15)=2×15×72=2160

输出为 2160，与样例一致。

复杂度分析

• 时间复杂度：O(n)，只需一次遍历从 1 到 n。

• 空间复杂度：O(1)，仅使用常数空间（6 个元素的数组）。

最终代码

#include <iostream>
#include <vector>
using namespace std;const int MOD = 998244353;int main() {int n;cin >> n;if (n <= 10) {cout << n * (n - 1) % MOD << endl;return 0;}vector<int> dp(6); // dp[i % 6] = f(i)for (int i = 1; i <= 10; ++i) {dp[i % 6] = i * (i - 1) % MOD;}for (int i = 11; i <= n; ++i) {dp[i % 6] = 1LL * 2 * i * dp[(i - 6) % 6] % MOD;}cout << dp[n % 6] << endl;return 0;
}

注意事项

1. 模运算：每次乘法后都要取模，防止溢出。

2. 初始条件：f(1) 到 f(10) 直接计算。

3. 空间优化：使用模 6 的数组来保存最近的 6 个值，避免存储整个 dp 数组。

---

四、1.高塔登顶方案 - 蓝桥云课

算法代码： 

#include <iostream>
#include <vector>
using namespace std;const int MOD = 1e9 + 7;/*** 正向递推的动态规划解法（未优化）* @param n 目标台阶数* @param m 最小跳跃步数* @param k 最大跳跃步数* @return 到达第n阶的方式数*/
int sol1(int n, int m, int k) {vector<int> f(n + 1, 0); // 动态规划数组f[1] = 1;for (int i = 1; i <= n; ++i) {// 更新i能到达的所有位置for (int j = i + m; j <= min(i + k, n); ++j) {f[j] = (f[j] + f[i]) % MOD;}}return f[n];
}/*** 反向递推的动态规划解法（未优化）* @param n 目标台阶数* @param m 最小跳跃步数* @param k 最大跳跃步数* @return 到达第n阶的方式数*/
int sol2(int n, int m, int k) {vector<int> f(n + 1, 0);f[1] = 1;for (int i = 2; i <= n; ++i) {// 统计所有能到达i的位置贡献int start = max(i - k, 1);int end = i - m;for (int j = start; j <= end; ++j) {f[i] = (f[i] + f[j]) % MOD;}}return f[n];
}/*** 使用前缀和优化的动态规划解法* @param n 目标台阶数* @param m 最小跳跃步数* @param k 最大跳跃步数* @return 到达第n阶的方式数*/
int sol_fast(int n, int m, int k) {vector<int> f(n + 1, 0); // 动态规划数组vector<int> sum(n + 1, 0); // 前缀和数组f[1] = 1;sum[1] = 1;for (int i = 2; i <= n; ++i) {int c1 = i - m; // 贡献区间右端点int c2 = max(i - k, 1); // 贡献区间左端点if (c1 >= c2) {// 通过前缀和快速计算区间和f[i] = ((sum[c1] - sum[c2 - 1]) + MOD) % MOD;}sum[i] = (sum[i - 1] + f[i]) % MOD; // 维护前缀和}return f[n];
}int main() {int n, m, k;scanf("%d%d%d", &n, &m, &k);printf("%d\n", sol_fast(n, m, k));return 0;
}

 解析：

---

五、1.数正方形 - 蓝桥云课

算法代码：

#include <iostream>  // 引入输入输出流库
#include <vector>    // 引入向量容器库（虽然代码中未使用，但保留）
#include <queue>     // 引入队列库（虽然代码中未使用，但保留）using namespace std; // 使用标准命名空间const int MOD = 1e9 + 7; // 定义模数常量，用于取模运算// 第一种计算方法：直接计算每个边长的贡献
int get_ans(int n) {n --; // 将点阵的边长转换为格子数量（n×n的点阵有(n-1)×(n-1)个格子）int ans = 0; // 初始化答案为0for (int i = 1; i <= n; ++i) { // 遍历所有可能的正方形边长i// 计算边长为i的正方形的贡献：// 1. i是当前正方形的边长// 2. (n - i + 1) * (n - i + 1)是边长为i的正方形可以放置的位置数量// 3. 1ll用于将乘法提升为长整型以避免溢出ans += 1ll * i * (n - i + 1) % MOD * (n - i + 1) % MOD; ans %= MOD; // 每次加法后取模，防止溢出}return ans; // 返回最终结果
}// 第二种计算方法：利用平方和优化计算
int get_ans1(int n) {n --; // 同样将点阵的边长转换为格子数量int ans = 1; // 初始化答案为1（对应i=1的情况）int f2 = 1;  // 初始化平方和为1（1² = 1）for (int i = 2; i <= n; ++i) { // 从i=2开始遍历f2 += 1ll * i * i % MOD; // 累加i²到平方和中f2 %= MOD; // 每次加法后取模ans = (ans + f2) % MOD; // 将当前平方和累加到答案中}return ans; // 返回最终结果
}int main() {int n; // 定义变量n，表示点阵的边长cin >> n; // 从标准输入读取ncout << get_ans1(n) << endl; // 调用get_ans1函数并输出结果return 0; // 程序正常结束
}