Lesson 5 - 递归进阶
2024年11月30日大约 10 分钟
7937 数的个数
问题分析
给定一个自然数 n（1 < n ≤ 100），我们需要按照特定规则计算满足条件的数字的个数。规则如下：
- 不作任何处理，直接考虑
n。 - 在
n的左边加上一个正整数，这个正整数不能超过原数的一半（即加的数的值必须小于等于n/2）。 - 对于加上去的新数，继续按此规则进行处理，直到不能再加正整数为止。
要求输出满足这个条件的所有数的个数。
解题思路
- 我们首先将
n作为一个有效的数字。 - 然后，我们在其左边加上一个正整数，该整数的取值范围是
[1, n//2]。 - 对于每个加上的整数，我们继续进行递归处理，直到该整数的值无法再加上一个有效数。
- 最后输出所有满足条件的数字个数。
解题注意事项
- 使用递归来模拟将数左移并不断加上正整数的过程。
- 需要注意递归的结束条件，即当加上的整数为
1时不再继续递归。 - 初始时我们将
n本身作为一个满足条件的数。
代码实现
#include<bits/stdc++.h>
using namespace std;
int ans = 1; // 初始条件，至少有一个数（n本身）
void f(int x) {
for(int i = 1; i <= x / 2; i++) { // 只能加上不超过x的一半的数
ans++; // 找到一个符合条件的数
f(i); // 对加上的数递归处理
}
}
int main() {
int n;
cin >> n;
f(n); // 从n开始进行处理
cout << ans; // 输出最终结果
return 0;
}8913 数的个数2
问题分析
给定一个正整数 n（n 为奇数，且 0 < n < 100），我们需要按照特定规则计算满足条件的数字的个数。规则如下：
- 不作任何处理，直接考虑
n本身。 - 在
n的左边加上一个奇数，这个奇数不能超过原数的一半（即加的数的值必须小于等于n/2且是奇数）。 - 对于每个加上的奇数，我们继续进行递归处理，直到该奇数无法再加上一个有效数。
要求输出满足这个条件的所有数的个数。
解题思路
- 我们首先将
n作为一个有效的数字。 - 然后，我们在其左边加上一个奇数，该奇数的取值范围是
[1, n//2]且该数必须是奇数。 - 对于每个加上的奇数，我们继续进行递归处理，直到无法再加上符合条件的奇数。
- 最后输出所有满足条件的数字个数。
解题注意事项
- 使用递归来模拟将数左移并不断加上奇数的过程。
- 需要注意递归的结束条件，即当加上的数为
1时不再继续递归。 - 初始时我们将
n本身作为一个满足条件的数。 - 每次递归时只允许加上奇数。
代码实现
#include<bits/stdc++.h>
using namespace std;
int ans = 1; // 初始条件，至少有一个数（n本身）
void f(int x) {
for(int i = 1; i <= x / 2; i += 2) { // 只能加上不超过x/2的奇数
ans++; // 找到一个符合条件的数
f(i); // 对加上的数递归处理
}
}
int main() {
int n;
cin >> n;
f(n); // 从n开始进行处理
cout << ans; // 输出最终结果
return 0;
}7769 黑白棋的移动过程
解题思路
- 初始化棋盘：我们首先根据输入
n初始化一个棋盘，左边是n个白子，右边是n个黑子，剩余位置填充空格。 - 递归交换棋子：在棋盘上进行递归交换，直到我们得到交替排列的状态。
- 输出每一步：每一步交换后，打印当前棋盘状态。
解题步骤
- 初始化棋盘：我们使用一个字符数组
a来表示棋盘，其中前n个元素是白子'o'，后n个元素是黑子'*'，其余位置为空'-'。 - 交换过程：每次递归过程中，我们会交换相邻的棋子，并打印出当前的棋盘状态。
- 递归终止条件：当
m到达某个特定值时，递归过程结束，输出最终的状态。
::: details 代码实现
#include<bits/stdc++.h>
using namespace std;
char a[205]; // 用于存储棋盘的状态
int n;
string s[6] = {"oooo****--", "ooo--***o*", "ooo*o**--*", "o--*o**oo*", "o*o*o*--o*", "--o*o*o*o*"};
void f(int m) {
if (m == 4) {
for (int i = 0; i < 6; i++) {
cout << s[i];
for (int j = 11; j <= 2 * n + 2; j++)
cout << a[j];
cout << endl;
}
return;
}
// 打印当前棋盘的状态
for (int i = 1; i <= 2 * n + 2; i++)
cout << a[i];
cout << endl;
// 交换棋子的过程
swap(a[m], a[m * 2 + 1]);
swap(a[m + 1], a[m * 2 + 2]);
// 打印交换后的棋盘状态
for (int i = 1; i <= 2 * n + 2; i++)
cout << a[i];
cout << endl;
// 继续递归
swap(a[m], a[m * 2 - 1]);
swap(a[m + 1], a[m * 2]);
f(m - 1);
}
int main() {
cin >> n; // 输入棋子的数量
// 初始化棋盘
for (int i = 1; i <= n; i++)
a[i] = 'o'; // 白子
for (int i = n + 1; i <= 2 * n; i++)
a[i] = '*'; // 黑子
a[2 * n + 1] = a[2 * n + 2] = '-'; // 填充空行
f(n); // 调用递归函数进行棋子的交换
return 0;
}:::
1499 汉诺塔
问题分析
汉诺塔问题是一个经典的递归问题，描述了如何将一组按大小排列的盘子从一个柱子移动到另一个柱子，且在移动过程中遵守以下规则：
- 每次只能移动一个盘子。
- 任何时刻，大盘子不能放在小盘子上面。
- 移动的过程中可以使用第三根柱子作为辅助。
目标是将 n 个盘子从柱子 A 移动到柱子 C，使用柱子 B 作为辅助柱子，并且输出每次移动盘子的顺序。
解题思路
汉诺塔问题可以通过递归解决，基本思想是：
- 将
n-1个盘子从起始柱子A移动到辅助柱子B，然后再将第n个盘子从A移动到目标柱子C。 - 最后将
n-1个盘子从辅助柱子B移动到目标柱子C。
递归的结束条件是当只有一个盘子时，直接移动它即可。
解题注意事项
- 递归的核心是将问题分解成两个较小的子问题，分别处理。
- 每次递归移动盘子时，遵循标准的移动规则。
代码实现
#include<bits/stdc++.h>
using namespace std;
void hanoi(char a, char b, char c, int n) {
if (n == 1) {
// 当只有一个盘子时，直接移动
cout << a << '-' << c << endl;
return; // 递归出口
}
// 将n-1个盘子从a移动到b
hanoi(a, c, b, n - 1);
// 将第n个盘子从a移动到c
cout << a << '-' << c << endl;
// 将n-1个盘子从b移动到c
hanoi(b, a, c, n - 1);
}
int main() {
int n;
cin >> n; // 输入盘子的个数
hanoi('A', 'B', 'C', n); // A是起始柱，B是辅助柱，C是目标柱
return 0;
}1675 黑白棋
问题分析
在这个问题中，给定一个整数 n，表示棋盘上的棋子总数为 2n，其中前 n 个棋子是白子（表示为○），后 n 个棋子是黑子（表示为●）。初始状态下，所有的白子都在左边，黑子都在右边。我们需要通过一系列规则将这些棋子移动，最终使得棋盘上的棋子排成黑白相间的形式。
规则：
- 每次移动时，我们必须同时移动相邻的两个棋子（颜色不限）。
- 移动时，棋子不能交换左右位置。
- 每次移动必须跳过若干个棋子，不能直接平移。
- 最终目标是将所有的棋子排列成黑白相间的形式。
解题思路
初始状态： 初始状态下，所有的白子（○）排在左边，黑子（●）排在右边。
目标状态： 目标是让棋盘上的棋子排成交替的黑白相间的形式，例如：
○ ● ○ ● ○ ● ...移动规则： 每次需要同时移动相邻的两个棋子，且通过递归的方式，将小规模的棋子问题逐渐转化为大规模的问题。
递归结构：
- 在递归的每一层，我们先将一对相邻的棋子从当前位置移动到目标位置，再交换相邻的两个棋子，直到问题规模缩小到最基本的情况。
递归终止条件： 当
m == 4时，输出已知的移动步骤。
代码实现
#include<bits/stdc++.h>
using namespace std;
void f(int m) {
if(m == 4) { // 递归的出口
cout << "4,5-->9,10" << endl;
cout << "8,9-->4,5" << endl;
cout << "2,3-->8,9" << endl;
cout << "7,8-->2,3" << endl;
cout << "1,2-->7,8" << endl;
return ;
}
// 打印当前的移动
cout << m << ',' << m+1 << "-->" << m*2+1 << ',' << m*2+2 << endl;
cout << m*2-1 << ',' << m*2 << "-->" << m << ',' << m+1 << endl;
// 递归处理问题规模缩小后的情况
f(m - 1);
}
int main() {
int n;
cin >> n;
f(n); // 从初始状态开始递归处理
return 0;
}1977 分解因数
问题分析
题目要求我们把一个给定的正整数
例如，对于数字 20，我们可以进行如下分解：
因此，20有4种不同的分解。
解题思路
- 递归分解：通过递归来逐步分解数字
- 边界条件：如果当前因子
- 累加结果：每次找到一个合法的分解，就将结果计数增加。
解题步骤
- 递归分解函数
f(int x, int y)，其中 - 通过递归，确保分解的因子按照递增顺序排列。
- 处理多组数据，每组数据输出一个结果。
提示
需要特别注意的是递归的终止条件以及如何保证因子按照递增顺序排列。
代码实现
#include<bits/stdc++.h>
using namespace std;
int ans; // 用来记录分解的种数
// f(x, y)：从x开始分解y
void f(int x, int y){
// 从x开始分解y，确保因子不大于y/x
for(int i = x; i <= y; i++){
if(y % i == 0 && i <= y / i){ // 如果i能整除y并且符合递增条件
ans++; // 记录一种新的分解方式
f(i, y / i); // 递归分解y / i
}
}
}
int main(){
int t; // t组数据
cin >> t;
while(t--){
int a; // 当前输入的数字
cin >> a;
ans = 1; // 初始化答案为1，表示a本身就是一种分解
f(2, a); // 从2开始分解a
cout << ans << endl; // 输出结果
}
return 0;
}9406 汉诺塔步数
参考程序
#include<bits/stdc++.h>
using namespace std;
int ans;
void hanoi(char a,char b,char c,int n){
if(n==1){
ans++;
cout<<ans<<':'<<a<<'-'<<c<<endl;
return ;
}
hanoi(a,c,b,n-1);
ans++;
cout<<ans<<':'<<a<<'-'<<c<<endl;
hanoi(b,a,c,n-1);
}
int main(){
int n;
cin>>n;
hanoi('A','B','C',n);
return 0;
}