从零开始学算法-Day3

//2020.4.22 第三天，学习的动力下降了
这也太难了吧。。。

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

题目描述：从1∼n这 n (n≤16)个整数中随机选取任意多个，输出所有可能的选择方案。

链接：https://ac.nowcoder.com/acm/contest/998/A
来源：牛客网

求解之路：

题目咋一看，不会。。。仔细一看，真的不会啊。。太难了
没办法啊，还是得学。
道理怎么办呢？那就得去看别人的代码了。。。

#include<iostream>
using namespace std;
int n;
void dfs(int u,int state)
{  //u用于记录递归次数 
//state用于记录状态 
    if(u==n)
    {
        for(int i=0;i<n;i++)
        if(state>>i&1)
        cout<<i+1<<" ";
        cout<<endl;
    return;
    }

    dfs(u+1,state);//表示不将第u位置1
    dfs(u+1,state|1<<u);//将第u位置1
    /* 最终将置成
    3->100
    2->010
    2 3->110
    1->001
    1 3->101
    1 2->011
    1 2 3->111
    */

}
int main(){
    cin>>n;
    dfs(0,0);//本题有明显的顺序，可以用dfs搜索
    //应该有两个变量一个用于记录递归的次数，以便
    //在边界的条件时能及时停下来
    //另一个用于记录不同的状态
    return 0; 
}

今天真的不行了，看不明白啊，太晚了，明天再捋捋。。

//2020.4.23 今天继续来搞

画了个流程图，一下子就把代码理解了。

<< 的优先级比| 高，运算的时候会先进行<<运算。

这道题用非递归就也能解出来了

#include <iostream>
using namespace std;

int main (){
    int n;
    cin >> n;
    for(int sta = 0; sta < (1 << n);sta++){
        for(int i = 0;i < n; i ++)
            if(sta >> i & 1)
                cout << i+1 << " ";
        cout << endl;
    }
    return  0;
} 

　总结：

真的很难，真的需要慢慢学！！！
递归代码来源：https://blog.csdn.net/qq_42635159/article/details/97116622