简单递归
文章目录
Let's be better ourselves together.
种一棵树最好的时间是十年前,其次是现在。
如何用简单递归实现指数型枚举,组合型枚举以及排列行枚举?
思路:我们可以把这一类题目想象成,有n个排列在一起的一列格子,我们需要按一定顺序来填这些格子。

以下为三道HZOJ的题目作为例子。
235. 递归实现指数型枚举
题目描述
从 1−n 这 n 个整数中随机选取任意多个,每种方案里的数从小到大排列,按字典序输出所有可能的选择方案。
输入
输入一个整数 n。(1≤n≤10)
输出
每行一组方案,每组方案中两个数之间用空格分隔。
注意每行最后一个数后没有空格。
样例输入
3样例输出
1
1 2
1 2 3
1 3
2
2 3
3样例输入2
4样例输出2
1
1 2
1 2 3
1 2 3 4
1 2 4
1 3
1 3 4
1 4
2
2 3
2 3 4
2 4
3
3 4
4数据规模与约定
时间限制:1 s
内存限制:256 M
100% 的数据保证 1≤n≤10
思路: 从下标为0的格子开始,依次填数,在第i个位置可以选择的最小数字是x的情况下,实现所有指数型枚举。当i > 0,也就是已经选择了至少一个数,输出一种结果。
#include <iostream>
using namespace std;
int n;
int a[20];
//在第i个位置,最小为x
void f(int x, int i) {
if(i > 0) { //如果已经选择了至少一个数字
for(int j = 0;j < i;j ++) {
if(j > 0) cout<<" ";
cout<<a[j];
}
cout<<endl;
}
for(int k = x;k <= n;k ++)
{
a[i] = k;
f(k + 1, i +1);
}
return ;
}
int main()
{
cin>>n;
f(1, 0);
return 0;
}236. 递归实现组合型枚举
题目描述
从 1−n 这 n 个整数中随机选取 m 个,每种方案里的数从小到大排列,按字典序输出所有可能的选择方案。
输入
输入两个整数 n,m。(1≤m≤n≤10)
输出
每行一组方案,每组方案中两个数之间用空格分隔。
注意每行最后一个数后没有空格。
样例输入
3 2样例输出
1 2
1 3
2 3样例输入2
5 3样例输出2
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5数据规模与约定
时间限制:1 s
内存限制:256 M
100% 的数据保证 1≤m≤n≤10
思路:这道题和上一道题十分类似。从下标为0的格子开始,依次填数,在第i个位置可以选择的最小数字是x的情况下,实现所有组合枚举。不同的是边界条件,上一道题当i > 0时即可输出一种结果,这道题要填满m个格子再输出一种结果,所以边界条件为i >= m。
#include <iostream>
using namespace std;
int n, m;
int a[20];
void f(int x, int i) {
if(i >= m) {
for(int j = 0;j < m;j ++){
if(j) cout<<' ';
cout<<a[j];
}
cout<<endl;
return ;
}
for(int k = x;k <= n;k ++) {
a[i] = k;
f(k + 1, i + 1);
}
}
int main()
{
cin>>n>>m;
f(1, 0);
return 0;
}237. 递归实现排列型枚举
题目描述
从 1−n 这 n 个整数排成一排并打乱次序,按字典序输出所有可能的选择方案。
输入
输入一个整数 n。(1≤n≤8)
输出
每行一组方案,每组方案中两个数之间用空格分隔。
注意每行最后一个数后没有空格。
样例输入
3样例输出
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1数据规模与约定
时间限制:1 s
内存限制:256 M
100% 的数据保证 1≤n≤8
思路:这道题其实就是输出n的全排列。这道题需要注意的是,如何判断当前的枚举的这个数字是否出现过。所以我们需要使用一个bool数组来记录它是否出现过。填数字的时候,先判断是否出现,如果没有出现(!st[k]),则填入数字。边界条件是,当n个格子都填满了, i == n,即完成了一种可能的排列。
#include <iostream>
using namespace std;
int n;
int a[10];
bool st[10];
void f(int i){
if(i == n) {
for(int j = 0;j < n;j ++) {
if(j > 0) cout<<' ';
cout<<a[j];
}
cout<<endl;
return ;
}
for(int k = 1;k <= n;k ++) {
if(!st[k]) {
a[i] = k;
st[k] = true;
f(i + 1);
st[k] = false;
}
}
}
int main()
{
cin>>n;
f(0);
return 0;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论