C/C++ 递归指数型枚举

个人主页:仍有未知等待探索_C语言疑难,数据结构,小项目-CSDN博客

专题分栏:算法_仍有未知等待探索的博客-CSDN博客

目录

一、前言

二、递归指数型枚举

1、题目信息

题目描述

输入格式

输出格式

样例

提示

 2、解析

 3、代码


一、前言

之前进行枚举的时候,都是进行暴力枚举的策略,将所用可能性都枚举一遍以获得最优解,但是枚举全部元素的效率如同愚公移山,无法应付数据范围稍大的情形。其算法的主要策略是跳过一些无效状态,降低问题的规模。

二、递归指数型枚举

1、题目信息

题目链接:U127142 指数型枚举 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

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

输入格式

输入一个整数n。

输出格式

每行输出一种方案。

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

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

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

样例

样例输入

```
3
```

样例输出

```
1 2 3
1 2
1 3
1
2 3
2
3
```

提示

1≤n≤15

 2、解析

如下图是整个程序的思路,n=3,代表要求 n = 3 的方案数。首先我们要先选第一个数,用一个数组进行存储这位数到底选还是不选。如果选的话,就接着往下一位数进行继续判断,知道要判断的位数大于n,代表结束。然后开始进行回溯。

下图我只对前一半的运行步骤进行了标号,另一半和这个一样。 

 3、代码

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 20;
int n;//枚举的位数
int st[N];//存储枚举的位数的信息(某位数是否进行了选择)
void bfs(int x){
    //如果x>n的话,说明枚举选择结束,接着就是输出所选的组合
    if(x>n){
        //选n位数,所以循环n次
        for(int i=1;i<=n;i++){
            //如果为1,代表该数选上了,i下标其实就是要存储的数
            if(st[i]==1){
                printf("%d ",i);
            }
        }
        printf("\n");
        return;
    }
    //选x位的数
    st[x]=1;//1代表选上了
    bfs(x+1);//进行接着往下递归
    //其实不写也没事,不过写上的话思路更加的完整
    st[x]=0;//回溯,把存储状态的数组进行恢复
    //不选x位的数
    st[x]=2;//2代表了没选上
    bfs(x+1);//进行接着往下递归
    //其实不写也没事,不过写上的话思路更加的完整
    st[x]=0;//回溯,把存储状态的数组进行恢复
}
int main(){
    cin>>n;
    bfs(1);
    return 0;
}

谢谢大家的支持!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/180356.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

数据结构与算法编程题14

设计一个算法&#xff0c;通过一趟遍历在单链表中确定值最大的结点。 #include <iostream> using namespace std;typedef int Elemtype; #define ERROR 0; #define OK 1;typedef struct LNode {Elemtype data; //结点保存的数据struct LNode* next; //结构体指针…

优思学院|2024年质量管理的大趋势

2023年我们已经顺利度过了整年的大部分时间&#xff0c;2024年质量管理的趋势和问题在全球范围内都已经引起了关注&#xff0c;或者仍然是企业导航的首要任务。 1. 通货膨胀与质量管理 2023年&#xff0c;全球范围内通货膨胀和严峻的经济状况成为企业最关心的问题之一。尽管物…

BootStrap【表格二、基础表单、被支持的控件、表单状态】(二)-全面详解(学习总结---从入门到深化)

目录 表格二 表单_基础表单 表单_被支持的控件 表单_表单状态 表格二 紧缩表格 通过添加 .table-condensed 类可以让表格更加紧凑&#xff0c;单元格中的内补&#xff08;padding&#xff09;均会减半 <table class"table table-condensed table-bordered"…

C#语言高阶开发

目录 数据结构 集合 动态数组ArrayList 习题&#xff1a;声明一个Monster类&#xff0c;有一个Attack方法,用一个ArrayList去封装Monster的对象,装10个&#xff0c;遍历monster的list让他们释放攻击方法 哈希表HashTable 创建一个武器类&#xff0c;有一个属性叫做id,每个…

SeaTunnel及SeaTunnel Web部署指南(小白版)

现在你能搜索到的SeaTunnel的安装。部署基本都有坑&#xff0c;官网的文档也是见到到相当于没有&#xff0c;基本很难找到一个适合新手小白第一次上手就能成功安装部署的版本&#xff0c;于是就有了这个部署指南的分享&#xff0c;小主已经把可能遇到的坑都填过了&#xff0c;希…

android keylayout键值适配

1、通过getevent打印查看当前keyevent数字对应事件和物理码 2、dumpsys input 查看输入事件对应的 KeyLayoutFile: /system/usr/keylayout/Vendor_6080_Product_8060.kl 3、通过物理码修改键值映射&#xff0c;修改/system/usr/keylayout/目录下的文件

redis-cluster集群模式

Redis-cluster集群 1 Redis3.0引入的分布式存储方案 2集群由多个node节点组成,redis数据分布在节点之中,在集群之中分为主节点和从节点3集群模式当中,主从一一对应,数据写入和读取与主从模式一样&#xff0c;主负责写&#xff0c;从只能读4集群模式自带哨兵模式&#xff0c;可…

视频剪辑有妙招:批量置入封面,轻松提升视频效果

随着社交媒体的兴起&#xff0c;视频已经成为分享和交流的重要方式。无论是专业的内容创作者还是普通的社交媒体用户&#xff0c;都要在视频剪辑上下一番功夫&#xff0c;才能让视频更具吸引力。而一个吸引的封面往往能在一瞬间抓住眼球&#xff0c;提高点击率。还在因如何选择…

基于Mapmost Alpha工具快速搭建3D场景可视化大屏

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…

h5如何使用navigateBack回退到微信小程序页面并携带参数

前言 在h5中使用navigateBack回退到微信小程序页面很常见&#xff0c;但是有一种交互需要在回退之后的页面可以得到通知&#xff0c;拿到标识之后&#xff0c;进行某些操作&#xff0c;这样的话&#xff0c;由于微信官方并没有直接提供这样的api&#xff0c;就需要我们开动脑筋…

【计算思维】蓝桥杯STEMA 科技素养考试真题及解析 6

1、明明买了一个扫地机器人&#xff0c;可以通过以下指令控制机器人运动: F:向前走 10 个单位长度 L:原地左转 90 度 R:原地右转 90 度 机器人初始方向向右&#xff0c;需要按顺序执行以下那条指令&#xff0c;才能打扫完下图中的道路 A、F-L-F-R-F-F-R-F-L-F B、F-R-F-L-F-F…

如何搭建Zblog网站并通过内网穿透将个人博客发布到公网

文章目录 1. 前言2. Z-blog网站搭建2.1 XAMPP环境设置2.2 Z-blog安装2.3 Z-blog网页测试2.4 Cpolar安装和注册 3. 本地网页发布3.1. Cpolar云端设置3.2 Cpolar本地设置 4. 公网访问测试5. 结语 1. 前言 想要成为一个合格的技术宅或程序员&#xff0c;自己搭建网站制作网页是绕…

virtualList 封装使用 虚拟列表 列表优化

虚拟列表 列表优化 virtualList 组件封装 virtualList 组件封装 本虚拟列表 要求一次性加载完所有数据 不适合分页 新建一个select.vue 组件页面 <template><div> <el-select transfer"true" :popper-append-to-body"true"popper-class…

redis-cluster集群(目的:高可用)

1、特点 集群由多个node节点组成&#xff0c;redis数据分布在这些节点中&#xff0c;在集群中分为主节点和从节点&#xff0c;一个主对应一个从&#xff0c;所有组的主从形成一个集群&#xff0c;每组的数据是独立的&#xff0c;并且集群自带哨兵模式 2、工作原理 集群模式中…

Android系统调试工具大全:解密adb、dumpsys、procrank等神器

Android系统调试工具大全&#xff1a;解密adb、dumpsys、procrank等神器 引言 Android开发中&#xff0c;调试是一个非常重要的环节&#xff0c;本文将介绍一些常用的Android系统调试工具&#xff0c;包括adb、logcat、procrank、dumpsys、dmesg、top、free、df、trace、pm、…

如何使用Google My Business来提升您的内容和SEO?

如果您的企业有实体店&#xff0c;那么使用Google My Business&#xff08;GMB&#xff09;来改善您的本地SEO并增强您的在线形象至关重要。Google My Business &#xff08;GMB&#xff09; 是 Google 提供的补充工具&#xff0c;使企业能够控制其在 Google 搜索和地图上的数字…

【数字化转型方法论读书笔记】-数据中台角色解读

一千个读者&#xff0c;就有一千个哈姆雷特。同样&#xff0c;数据中台对于企业内部不同角色的价值也不同&#xff0c;下面分别从董事长、CEO、 CTO/CIO、IT 架构师、数据分析师这 5 个角色的视角详细解读数据中台。 1、董事长视角下的数据中台 在数字经济时代&#xff0c;企业…

【从入门到起飞】JavaSE—多线程(3)(生命周期,线程安全问题,同步方法)

&#x1f38a;专栏【JavaSE】 &#x1f354;喜欢的诗句&#xff1a;路漫漫其修远兮&#xff0c;吾将上下而求索。 &#x1f386;音乐分享【如愿】 &#x1f384;欢迎并且感谢大家指出小吉的问题&#x1f970; 文章目录 &#x1f354;生命周期&#x1f384;线程的安全问题&#…

每日一题 1410. HTML 实体解析器(中等,模拟)

模拟&#xff0c;没什么好说的 class Solution:def entityParser(self, text: str) -> str:entityMap {&quot;: ",&apos;: "",>: >,<: <,&frasl;: /,&amp;: &,}i 0n len(text)res []while i < n:isEntity Falseif …

Java—学生信息管理系统(简单、详细)

文章目录 一、主界面展示二、学生类三、系统功能方法3.1 main()方法3.2 添加学生信息3.3 删除学生信息3.4 修改学生信息3.5 查看所有学生信息 四、完整代码4.1 Student .Java4.2 StudentManger.Java 前言&#xff1a;本案例在实现时使用了Java语言中的ArrayList集合来储存数据。…