跟着姚桑学算法-递归实现指数型枚举

简介: 基本算法题

基本算法题. 递归实现指数型枚举

从 1∼n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。

输入格式
输入一个整数 n。

输出格式
每行输出一种方案。

同一行内的数必须升序排列,相邻两个数用恰好 1 个空格隔开。

对于没有选任何数的方案,输出空行。

本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。

数据范围
1≤n≤15

输入样例:

3

输出样例:

3
2
2 3
1
1 3
1 2
1 2 3

:four_leaf_clover:题解 --- 状态压缩递归

__状态压缩的特性__:可以枚举所有选与不选的情况;
本题关键要考虑到按照什么顺序递归,具体解决步骤见代码注释栏目。

:memo:代码展示

#include<bits/stdc++.h>
using namespace std;
int n;
// 二进制状态压缩,即用二进制上的位来记录数有没有被用过
// u是当前枚举到的数,state是二进制数记录哪些数被选
void dfs(int u ,int state){
    if( u == n){
        for(int i = 0; i< n; i++)
            //判断第i位是不是1,如果是1就代表被选,输出
            if(state >> i & 1) 
                //第几位就代表输出几,只不过不是从0开始,而是从1开始
                cout << i + 1 << " ";
        cout << endl;
        return;
    }
    // 不用这个数,第u位不动
    dfs(u + 1, state); 
    // 用这个数,把第u位变成1
    // 运算优先级:左移高于位运算|
    dfs(u + 1, state | 1 << u);  


}

int main(){

    cin >> n;
    /*
    回顾dfs参数的含义:
        - u是当前枚举到的数,
        -state是二进制数记录哪些数被选

    则 dfs(0, 0)表示:当前枚举到0,没有数被选

    */ 
    dfs(0, 0);

}

【知识点:状态压缩递归】

正如之前讲过的状态压缩(再回顾一遍),今天再来说一说递归:

状态压缩 问题 :
1.解法需要保存一定的状态数据(表示一种状态的一个数据值),每个状态数据通常情况下是可以通过2进制来表示的。这就要求状态数据的每个单元只有两种状态,比如说棋盘上的格子,放棋子或者不放,或者是硬币的正反两面。这样用0或者1来表示状态数据的每个单元,而整个状态数据就是一个一串0和1组成的二进制数。
2.解法需要将状态数据实现为一个基本数据类型,比如int,long等等,即所谓的状态压缩。状态压缩的目的一方面是缩小了数据存储的空间,另一方面是在状态对比和状态整体处理时能够提高效率。这样就要求状态数据中的单元个数不能太大,比如用int来表示一个状态的时候,状态的单元个数不能超过32(32位的机器)。

递归 问题:
其作为一种解决问题的有效方法,在递归过程中,函数将自身作为子例程调用。
递归的思想是 把一个大型复杂问题层层转化为一个与原问题规模更小的问题,问题被拆解成子问题后,递归调用继续进行,直到子问题无需进一步递归就可以解决的地步为止。

目录
相关文章
|
5月前
|
算法 C++
算法笔记:递归(c++实现)
算法笔记:递归(c++实现)
|
20天前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
14 1
|
5月前
|
存储 算法 程序员
数据结构与算法===递归
数据结构与算法===递归
|
20天前
|
算法 定位技术
数据结构与算法学习九:学习递归。递归的经典实例:打印问题、阶乘问题、递归-迷宫问题、八皇后问题
本文详细介绍了递归的概念、重要规则、形式,并展示了递归在解决打印问题、阶乘问题、迷宫问题和八皇后问题等经典实例中的应用。
29 0
|
3月前
|
算法
【算法】递归、搜索与回溯——汉诺塔
【算法】递归、搜索与回溯——汉诺塔
|
4月前
|
机器学习/深度学习 算法 数据挖掘
算法金 | 欧氏距离算法、余弦相似度、汉明、曼哈顿、切比雪夫、闵可夫斯基、雅卡尔指数、半正矢、Sørensen-Dice
**摘要:** 了解9种距离和相似度算法:欧氏距离、余弦相似度、汉明距离、曼哈顿距离、切比雪夫距离、闵可夫斯基距离、雅卡尔指数、半正矢距离和Sørensen-Dice系数。这些算法在机器学习、文本分析、图像处理和生物学等领域各有应用。例如,欧氏距离用于KNN和K-Means,余弦相似度用于文本相似性,汉明距离在错误检测中,曼哈顿距离在数据挖掘,切比雪夫距离在棋盘游戏,闵可夫斯基距离通过调整参数适应不同场景,雅卡尔指数和Sørensen-Dice系数用于集合相似度。每种算法有其优缺点,如欧氏距离对异常值敏感,余弦相似度忽略数值大小,汉明距离仅适用于等长数据。
106 2
算法金 | 欧氏距离算法、余弦相似度、汉明、曼哈顿、切比雪夫、闵可夫斯基、雅卡尔指数、半正矢、Sørensen-Dice
|
3月前
|
算法
【算法】递归总结:循环与递归的区别?递归与深搜的关系?
【算法】递归总结:循环与递归的区别?递归与深搜的关系?
|
3月前
|
算法
【算法】递归、搜索与回溯——简介
【算法】递归、搜索与回溯——简介
|
4月前
|
算法 Python
python中算法递归错误(Recursion Errors)
【7月更文挑战第18天】
64 1
|
5月前
|
机器学习/深度学习 算法 C语言
详细介绍递归算法在 C 语言中的应用,包括递归的基本概念、特点、实现方法以及实际应用案例
【6月更文挑战第15天】递归算法在C语言中是强大力量的体现,通过函数调用自身解决复杂问题。递归涉及基本概念如自调用、终止条件及栈空间管理。在C中实现递归需定义递归函数,分解问题并设定停止条件。阶乘和斐波那契数列是经典应用示例,展示了递归的优雅与效率。然而,递归可能导致栈溢出,需注意优化。学习递归深化了对“分而治之”策略的理解。**
97 7