简单递归

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;
}

评论

暂无评论