牛客——递归实现指数型枚举(枚举,dfs)

news/2024/2/28 6:51:09

链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
 

题目描述

从 1∼n1\sim n1∼n这 n (n≤16)(n \leq 16)(n≤16) 个整数中随机选取任意多个,输出所有可能的选择方案。

输入描述:

一个整数n。

输出描述:

每行一种方案。同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。对于没有选任何数的方案,输出空行。本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;for(int i=0;i<(1<<n);i++){for(int j=0;j<=n;j++){if(i>>j&1){cout<<j+1<<' ';}}cout<<endl;}return 0;
}

这个题就是枚举,可以结合二进制的特点来看。

每一个数的存在与否就看成0和1,那么就有2的n次方种。

接着就是要找二进制数中为1的输出j+1就可以。

另外还可以用dfs来做。

#include<bits/stdc++.h>
using namespace std;
int n;
bool st[100]={false};
void dfs(int u){if(u>n){for(int i=1;i<=n;i++)if(st[i])cout<<i<<" ";cout<<endl;return;}st[u]=true;dfs(u+1);//选择当前分支st[u]=false;dfs(u+1);//不选当前分支}int main(){cin>>n;dfs(1);return 0;
}

另外,还有一个拓展:

题目描述

把 1∼n这 n(n<10)个整数排成一行后随机打乱顺序,输出所有可能的次序。
输入描述:
一个整数n。
输出描述:
按照从小到大的顺序输出所有方案,每行1个。 首先,同一行相邻两个数用一个空格隔开。其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面。

示例1

输入
3
输出
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

void dfs(int u){if(u==n+1){                 //递归边界,已经处理完排列的1~n位for(int i=1;i<=n;i++)cout<<P[i]<<" ";   //输出当前排列cout<<endl;return ;}for(int i=1;i<=n;i++){    //枚举1~n,试图将x填入P[u]中,if(st[i]==false){     //如果不在P[0]~P[u-1]中,P[u]=i;           //将P的第u位为i,即将i加入到当前排列st[i]=true;       //记i已经在u号位dfs(u+1);       //处理排列载=在第u+1号位st[i]=false;       //已经处理完P[u]为i的子问题,还原}}
}

 


http://www.ppmy.cn/news/1350421.html

相关文章

[NSSCTF]-Web:[SWPUCTF 2021 新生赛]easyrce解析

先看网页 代码审计&#xff1a; error_reporting(0); &#xff1a;关闭报错&#xff0c;代码的错误将不会显示 highlight_file(__FILE__); &#xff1a;将当前文件的源代码显示出来 eval($_GET[url]); &#xff1a;将url的值作为php代码执行 解题&#xff1a; 题目既然允许…

【ES】--ES集成热更新自定义词库(字典)

目录 一、问题描述二、具体实施1、Tomcat实现远程扩展字典2、验证生效3、ES配置远程扩展字典4、为何不重启ES能实现热更新 一、问题描述 问题现象: 前面完成了自定义分词器词库集成到ES中。在实际项目中词库是时刻在变更的&#xff0c;但又不希望重启ES&#xff0c;对此我们应…

【51单片机】DS18B20(江科大)

一、DS18B20温度传感器 1.DS18B20介绍 DS18B20是一种常见的数字温度传感器,其控制命令和数据都是以数字信号的方式输入输出,相比较于模拟温度传感器,具有功能强大、硬件简单、易扩展、抗干扰性强等特点 测温范围 :- 55℃到125℃ 通信接口:1-Wire(单总线) 其它特征:可形成…

Linux第47步_安装支持linux的第三方库和mkimage工具

安装支持linux的第三方库和mkimage工具&#xff0c;做好移植前的准备工作。 编译linux内核之前&#xff0c;需要先在 ubuntu上安装“lzop库”和“libssl-dev库”&#xff0c;否则内核编译会失败。 mkimage工具会在zImage镜像文件的前面添加0x40个字节的头部信息,就可以得到uI…

精品springboot疫苗发布和接种预约系统

《[含文档PPT源码等]精品基于springboot疫苗发布和接种预约系统[包运行成功]》该项目含有源码、文档、PPT、配套开发软件、软件安装教程、项目发布教程、包运行成功&#xff01; 软件开发环境及开发工具&#xff1a; Java——涉及技术&#xff1a; 前端使用技术&#xff1a;…

【正在更新】从零开始认识语音识别:DNN-HMM混合系统语音识别(ASR)原理

摘要 | Abstract TO-BE-FILLED 1.前言 | Introduction 近期想深入了解语音识别(ASR)中隐马尔可夫模型(HMM)和深度神经网络-隐马尔可夫(DNN-HMM)混合模型&#xff0c;但是尽管网络上有许多关于DNN-HMM的介绍&#xff0c;如李宏毅教授的《深度学习人类语言处理》[1]&#xff0c;…

Kotlin手记(一):基础大杂烩

Kotlin简介 2011年7月&#xff0c;JetBrains推出Kotlin项目&#xff0c;这是一个面向JVM的新语言 2012年2月&#xff0c;JetBrains以Apache 2许可证开源此项目。 2016年2月15日&#xff0c;Kotlin v1.0发布&#xff0c;这被认为是第一个官方稳定版本。 在Google I/O 2017中&am…

CSP-动态规划-最长公共子序列(LCS)

一、动态规划 动态规划&#xff08;Dynamic Programming&#xff0c;简称DP&#xff09;主要用于求解可以被分解为相似子问题的复杂问题&#xff0c;特别是在优化问题上表现出色&#xff0c;如最短路径、最大子数组和、编辑距离等。动态规划的核心思想是将原问题分解为较小的子…

【蓝桥杯选拔赛真题34】C++最大值 第十三届蓝桥杯青少年创意编程大赛C++编程选拔赛真题解析

目录 C/C最大值 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 七、推荐资料 C/C最大值 第十三届蓝桥杯青少年创意编程大赛C选拔赛真题 一、题目要求 1、编程实现&#xff08;C&#xff09; 给定一个…

【GameFramework框架内置模块】1、全局配置(Config)

推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享简书地址 大家好&#xff0c;我是佛系工程师☆恬静的小魔龙☆&#xff0c;不定时更新Unity开发技巧&#xff0c;觉得有用记得一键三连哦。 一、前言 【GameFramework框架】系列教程目录&#xff1a; https://blog.csdn.net/q7…

第9讲用户信息修改实现

用户信息修改实现 后端修改用户昵称&#xff1a; /*** 更新用户昵称* param wxUserInfo* param token* return*/ RequestMapping("/updateNickName") public R updateNickName(RequestBody WxUserInfo wxUserInfo,RequestHeader String token){if(StringUtil.isNot…

vue3学习——集成sass

安装 pnpm i sass sass-loader -D在vite.config.ts文件配置: export default defineConfig({css: {preprocessorOptions: {scss: {javascriptEnabled: true,additionalData: import "./src/styles/variable.scss";,},},},} }创建三个文件 src/styles/index.scss //…

openkylin(Debian系)安装nginx及安装前需要的准备

前言 现在很多linux系统都可以使用高级包管理工具安装软件了&#xff0c;但是在像是 openkylin这些新系统中&#xff0c;好多软件包虽然有&#xff0c;但是因为其依赖的包还没有做好&#xff0c;所 以安装会提示你一大堆依赖错误。所以还是要自己来编译安装咯。安装前准备&…

【QT+QGIS跨平台编译】之三十六:【RasterLite2+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

文章目录 一、RasterLite2介绍二、文件下载三、文件分析四、pro文件五、编译实践一、RasterLite2介绍 RasterLite2是一个开源的轻量级栅格数据库,可以用于存储和管理各种类型的栅格数据,包括卫星遥感图像、数字高程模型等。 与传统的GIS数据存储方式不同,RasterLite2采用基…

[ubuntu]split命令分割文件

split 命令 $ split --help Usage: split [OPTION]... [INPUT [PREFIX]] Output fixed-size pieces of INPUT to PREFIXaa, PREFIXab, ...; default size is 1000 lines, and default PREFIX is x. With no INPUT, or when INPUT is -, read standard input.Mandatory argume…

Java集合补充

List和array的转换 Object[] arraylist.toArray(); Integer[] array list.toArray(new Integer[3]); 注意&#xff0c;这里的3是指创建array的大小&#xff0c;当数组小的话&#xff0c;会自动扩容为刚好的大小&#xff0c;若是大了&#xff0c;剩下的空间会变为null。可以使…

STM32自学☞PWM驱动舵机(按键控制)

PWM.c文件 #include "stm32f10x.h" /*初始化函数*/ void PWM_Init(void){ /*开启时钟*/ RCC_APB1PeriphClockCmd(RCC_APB1Periph_TIM2, ENABLE); //开启TIM2的时钟 RCC_APB2PeriphClockCmd(RCC_APB2Periph_GPIOA, ENABLE); //开启GPIOA的时钟 /*GPIO初始化*/ G…

Redis的删除策略

在Redis中的数据删除策略有三种&#xff1a;定时删除、惰性删除、定期删除 定时删除 当key设置有过期时间&#xff0c;且过期时间到达时&#xff0c;立即执行key的删除操作 优点&#xff1a;节约内存&#xff0c;到时就删除&#xff0c;立即释放不必要的内存占用 缺点&#xf…

「数据结构」线性表

定义和基本操作 定义&#xff1a;相同数据类型的 n ( n ≥ 0 ) n(n \ge 0) n(n≥0)个数据元素的有限序列&#xff0c;其中n为表长&#xff0c;当n0时线性表是一个空表一般表示&#xff1a; L ( a 1 , a 2 , … … , a i , a i 1 , a n ) L(a_1,a_2,……,a_i,a_{i1},a_n) L(a…
最新文章