专栏首页光城(guangcity)算法系列之二进制位+回溯递归

算法系列之二进制位+回溯递归

1.算法系列之二进制位+回溯递归

题目:从 1~n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。输入:n 输出:多种方案 同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。

数据范围
1≤n≤15
输入样例:
3
输出样例:
3
2
2 3
1
1 3
1 2
1 2 3

数据范围15,2^15次方是可以的,也就是递归算法。

2.递归+回溯

我们直接递归的过程中记录下选择的数即可。

#include <iostream>
#include <vector>
using namespace std;

int n;

void dfs(int u, vector<int>& temp) {
    if (u == n) {
        for(int i=0;i<temp.size();i++) {
            cout << temp[i]+1 << " ";
        }
        cout << endl;
        return;
    }
    dfs(u+1, temp); // 不选
    temp.push_back(u);  // add
    dfs(u+1, temp); // 选择
    temp.pop_back(); // recover
}
int main() {
    cin >> n;
    vector<int> temp;
    dfs(0,temp);   
    return 0;
}

3.递归+二进制位

针对每一个数,都有选与不选两种可能:假设n = 5 那么我们可以用二进制位表示每一位选择还是没有选择。

0 1 2 3 4

// 例如:选择数字4 5(分别对应第3、4位)
0 0 0 1 1 表示的数字就是11000
然后到了递归出口时,把这个数字从低位向高位遍历,&1判断是否是1,是1,那么该位是被选择了,也就是这个数字(该位+1)被选择了。
// 再比如:选择数字1
1 0 0 0 0 表示的数字就是1,出口的时候直接从低位遍历,此时就是index=0所代表的数字1。

具体实现如下:

#include <iostream>
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) {
                cout << i+1 << ' ';
            }
        }
        cout << endl;
        return;
    }
    dfs(u+1, state); // 不选
    //  <<与>>优先级大于|,&
    dfs(u+1, state | (1 << u)); // 选择
}
int main() {
    cin >> n;
    dfs(0,0);   
    return 0;
}

3.非递归+二进制位

在递归实现中,我们是通过往下递归,直到找到出口,此时我们得到了一个状态,也就是二进制的数据串,例如:1010,然后从第0位开始到第n-1开始拿去该二进制数中是1所代表哪个数。

那对于非递归,我们可以知道所有的状态或者说二进制数总共有2^n种可能,可以直接遍历该2^n种可能性,再去从低位到高位,判断哪一位是1,进而确定具体选择的数字是多少。

int n;
cin >> n;

for (int state = 0; state < 1<<n; state++) {
    for (int i=0;i<n;i++) {
        // 右移拿到第i位的数,判断是否——是1
        if (state>>i&1) cout << i+1 << " ";
    }
    cout << endl;
}

本文分享自微信公众号 - 光城(guangcity),作者:lightcity

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 如何提高编程能力?(中)

    函数方程: y - f2 = (f2 - f1) / (x2 - x1)(x - x2) 化简得: x=(f2x1-f1x2)/(f2-f1)

    公众号guangcity
  • Hive SQL开窗函数实战

    开窗函数是数据的一种查询统计语法糖,多是用于离线统计,这同时也是大数据技术栈的应用场景。今天学习Hive SQL的开窗(窗口)函数,对比与MySQL,在MySQ...

    公众号guangcity
  • 天眼连接你我

    最近读者想让我多发点爬虫文章,实在是时间原因,让各位就等了,我一口气,继续研究字体反爬策略,本文是基于天眼进行初探,后文待续。

    公众号guangcity
  • C++ 传递动态内存

    这部分内容在引用作为函数的参数这个blog中有一些涉及,为了讨论引用传递顺带了参数传递与指针传递,在这里从动态内存传递的角度梳理一下,先看这样一个题目: 下...

    chaibubble
  • HDU 2566 统计硬币

    统计硬币 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

    Angel_Kitty
  • ZeroBrane Studio 简易适配 Lua 5.4

    Lua 5.4 已经到 rc4 版本了,相信不少朋友都已经有所尝试,最简单的测试方法应该就是手动编译一个 lua.exe,然后直接命令行执行脚本:

    用户2615200
  • 算法提高 金陵十三钗

    金陵十三钗   本题难度:难   本题占分比例:5% 问题描述   在电影《金陵十三钗》中有十二个秦淮河的女人要自我牺牲代替十二个女学生去赴日本...

    AI那点小事
  • 小程序本地相册选择图片或相机拍照底部弹框功能

    今天一位粉丝问了一个问题,关于小程序本地相册选择图片或相机拍照底部弹框功能,小程序根据文档来写,为什么没有底部弹框,点击按钮就直接打开了手机相册了。看了一下不是...

    王小婷
  • LiteOS内核教程05 | 互斥锁(共享资源保护)

    在多任务环境下,往往存在多个任务竞争同一共享资源的应用场景,互斥锁可被用于对共享资源的保护从而实现独占式访问。互斥锁(mutex)又称互斥型信号量,是一种特殊的...

    Mculover666
  • 小程序调用拍照功能

    今天一位粉丝问了一个问题,关于小程序本地相册选择图片或相机拍照底部弹框功能,小程序根据文档来写,为什么没有底部弹框,点击按钮就直接打开了手机相册了。看了一下不是...

    王小婷

扫码关注云+社区

领取腾讯云代金券