递归与递推练习

递归实现指数型枚举递归实现排列型枚举简单斐波那契

题目链接：
递归实现指数型枚举

这道题我们用树状图的方式来分析：
就拿例子来说明 枚举出{1，2，3}的所有子集

首先我们要知道每个位置有两个选择（选或不选）
例如第一个位置我们先看不选：

现在我们从第二层看选的情况：

现在我们再看全部分解后的情况：

我们就形成了这样一道递归树状图。
同时我们需要数组 st[] 记录状态。

代码如下：

#include 
#include 
#include 
#include 

using namespace std;

const int N = 20;
int n;
bool st[N];//用来记录被选择的数

void dfs(int u){
    if(u > n){
        for(int i = 1; i <= n; i++){
            if(st[i])//判断是否被选择
                printf("%d ", i);
        }
        puts("");
        return ;
    }
    //1.选择
    st[u] = true;
    dfs(u + 1);
   // 2.不选
    st[u] = false;
    dfs(u + 1);
}

int main(){
    cin >> n;
    dfs(1);
    return 0;
}

还有一种方法就是用按位的方式进行标记
具体实现就不分析了，如果对按位操作不熟悉的话可与看我的算法零基础：
《算法零基础100讲》(第44讲) 位运算 (位或) 入门
《算法零基础100讲》(第42讲) 位运算 (位与) 入门
《算法零基础100讲》(第49讲) 位运算 (右移)
《算法零基础100讲》(第48讲) 位运算 (左移)

代码如下：

#include 
#include 
#include 
#include 

using namespace std;

int n;

void dfs(int u, int state){
    if(u == n){
        for(int i = 0; i < n; i++){
            if(state >> i & 1)//判断i是否被选
                printf("%d ", i + 1);
        }
        puts("");
        return ;
    }
    //1.不选
    dfs(u + 1, state);
    //2.选
    dfs(u + 1, state | 1 << u);
}

int main(){
    cin >> n;
    dfs(0, 0);
    
    return 0;
}

题目链接：
递归实现排列型枚举

这道题我们还是用树状图的方式来描绘：
对{1，2，3}进行排列组合

同时我们要用数组 used[]和state[]， 其功能分别是记录数字是否被使用过和记录状态

#include 
#include 

using namespace std;

const int N = 10;
int n;
int used[N];  //记录其是否被使用过
int state[N]; //记录状态

void dfs(int u){
    if(u > n){//如果u > n则输出state[]
        for(int i = 1; i <= n; i++){
            printf("%d ", state[i]);
        }
        printf("n");
        return ;
    }
    for(int i = 1 ; i <= n; i++){
        if(!used[i]){//判断i是否被用过
            used[i] = 1;//标记i
            state[u] = i;//记录位置u的数
            dfs(u + 1);
            
            //恢复现场
            used[i] = 0;
            state[u] = 0;
        }
    }
    
}

int main(){
    cin >> n;
    dfs(1);
    return 0;
}

当然我们也可以使用c++里的库函数 next_permutation() 进行排列组合

代码如下：

#include 
#include 
#include 
#include 

using namespace std;

#define Swap(a, b){int tmp = a;a = b; b = tmp;}
const int N = 10;
int n;
int arr[9];
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)arr[i] = i;
    do{
        for(int i = 1; i <= n; i++)printf("%d ", arr[i]);
        printf("n");
    }while(next_permutation(arr + 1, arr + n + 1));
    return 0;
}

题目链接：
简单斐波那契

斐波那契就很简单
就直接上代码了：

#include 
#include 
#include 
#include 

using namespace std;

int main(){
    int n;
    cin >> n;
    int a = 0, b = 1;
    for(int i = 1; i <= n; i++){
        cout << a << ' ';
        int sum = a + b;
        a = b; b = sum;
    }
    return 0;
}