蓝桥杯:C++排列与组合

排列是暴力枚举时的常见操作。有以下两种情况。

C++的 next_permutation()是全排列函数,只能输出序列中所有元素的全排列。

本节将给出手写排列和组合的代码。因为在很多场合中不能使用系统自带的排列函数,所以需要自己编写。

全排列函数:next_permutation()

STL提供了求下一个排列组合的函数next_permutation()。例如对于由3个字符{a,b, c}组成的序列,next_permutation()能按字典序返回6个组合:abc、acb、bac、bca、cab、cba。

函数next_permutation()的定义有以下两种形式:

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);

返回值:如果没有下一个排列组合,则返回False,否则返回True。每执行一次next_ permutation(),新的排列就会被放到原来的空间里。

简称:前闭后开。

next_permutation()从当前的全排列开始,逐个输出更大的全排列,而不是输出所有的全排列,例如下面的代码。

#include <bits/stdc++.h>
using namespace std;
int main() {string s=”bca”;do {cout<<s<< " ";} while(next_permutation(s.begin(),s.end()));return 0;
}   //输出:bca cab cba

如果要得到所有的全排列,就需要从最小的全排列开始。如果初始的全排列不是最小的,则需要先用sort()对全排列排序,得到最小的全排列后,再使用next_permutation(),例如下面的代码。

#include <bits/stdc++.h>
using namespace std;
int main() {string s=”bca”;sort(s.begin(),s.end());  //字符串内部排序,得到最小的排列“abc”do {cout<<s<< " ";} while(next_permutation(s.begin(),s.end()));return 0;
}   //输出:abc acb bac bca cab cba

C++中还有一个全排列函数prev_permutation(),用于求前一个排列组合,与next_permutation()相反,即从大到小输出排列。

手写排列代码(暴力法):

#include <iostream>
#include <vector>//排列 
int main() {std::vector<int> s = {1, 2, 3, 4};for (int i = 0; i < 4; ++i) {for (int j = 0; j < 4; ++j) {if (j != i) {for (int k = 0; k < 4; ++k) {if (k != j && k != i) {std::cout << s[i] << s[j] << s[k] << ", ";}}}}}return 0;
}

手写组合代码(暴力法):

#include <iostream>
#include <vector>int main() {std::vector<int> s = {1, 2, 3, 4};for (int i = 0; i < 4; ++i) {for (int j = i + 1; j < 4; ++j) {for (int k = j + 1; k < 4; ++k) {std::cout << s[i] << s[j] << s[k] << ", ";}}}return 0;
}

例题1.排列序数

思路:先对输入的字符串s排序,然后用next_permutation()输出全排列,当全排列与初始的字符串相等时结束。

代码:

#include <bits/stdc++.h>
using namespace std;
int main() {string s,olds;cin>>s;olds=s;   //用olds记录最初的字符串int cnt = 0;sort(s.begin(),s.end());          //字符串内部排序,得到最小的排列do {if(s == olds) {cout<<cnt<<endl;break;}cnt++;} while(next_permutation(s.begin(),s.end()));return 0;
}

例题2.拼数

代码: 

#include<bits/stdc++.h>
using namespace std;
string a[21];  //记录20个数,用字符形式
bool cmp (string a, string b) {              //从大到小,按字典序的反序排列return a + b > b + a;                    //组合字符串,注意这个技巧,后面会详细讲解
}
int main( ) {int n;cin >> n;for(int i=0; i<n; i++)   cin >> a[i];sort(a, a+n, cmp);                       //从大到小,按字典序的反序排列for(int i=0; i<n; i++)     cout << a[i];return 0;
}

函数体中的这行代码:

return a + b > b + a;

是一个巧妙的比较方式,用于实现按字典序的反序(即从大到小)排列字符串。

如果 a + b 大于 b + a,说明 a 在字典序上大于 b,因此返回 true。

如果 a + b 小于 b + a,说明 a 在字典序上小于 b,因此返回 false。

如果它们相等,说明 a 和 b 相等,但由于我们在排序时通常不需要处理相等的情况,所以这个比较方式在这种情况下也能正常工作。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

PHP+vue+mysql校园学生社团管理系统574cc

运行环境:phpstudy/wamp/xammp等 开发语言&#xff1a;php 后端框架&#xff1a;Thinkphp 前端框架&#xff1a;vue.js 服务器&#xff1a;apache 数据库&#xff1a;mysql 数据库工具&#xff1a;Navicat/phpmyadmin 前台功能&#xff1a; 首页&#xff1a;展示社团信息和活动…

黑马Java——集合进阶(不可变集合、Stream流、方法引用)

目录 一、不可变集合 1、创建不可变集合的应用场景 2、创建不可变集合的书写格式 2.1、不可变的List集合 2.2、不可变的Set集合 2.3、不可变的Map集合 3、小结 二、Stream流 1、体验Stream流的作用 2、Stream流的思想 3、Stream流的使用步骤 3.1、单列集合获取Strea…

Duilib List 控件学习

这是自带的一个示例; 一开始运行的时候List中是空的,点击Search按钮以后就填充列表框; 先看一下列表框列头是在xml文件中形成的; <List name="domainlist" bkcolor="#FFFFFFFF" ... menu="true"> <ListHeader height="24…

2048游戏C++板来啦!

个人主页&#xff1a;PingdiGuo_guo 收录专栏&#xff1a;C干货专栏 大家好呀&#xff0c;我是PingdiGuo_guo&#xff0c;今天我们来学习如何用C编写一个2048小游戏。 文章目录 1.2048的规则 2.步骤实现 2.1: 初始化游戏界面 2.1.1知识点 2.1.2: 创建游戏界面 2.2: 随机…

Leetcode 236.二叉树的最近公共祖先

题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大&#xff08;一个节点也可以是它自己的…

【sgSearch】自定义组件:常用搜索栏筛选框组件(包括表格高度变化兼容)。

sgSearch源码 <template><div :class"$options.name" :expand"expandSearch" :showCollapseBtn"showCollapseBtn"><!-- v-clickoutside"(d) > (expandSearch false)" --><ul class"search-list"&…

深度学习从入门到不想放弃-7

上一章的内容 深度学习从入门到不想放弃-6 (qq.com) 今天讲的也算基础(这个系列后来我一寻思,全是基础 ),但是可能要着重说下,今天讲前向计算和反向传播,在哪儿它都永远是核心,不管面对什么模型 前向计算: 有的叫也叫正向传播,正向计算的,有的直接把前向的方法梯度下…

解决 postman测试接口报404 Not Found

JDK版本&#xff1a;jdk17 IDEA版本&#xff1a;IntelliJ IDEA 2022.1.3 文章目录 问题描述原因分析解决方案 问题描述 当我使用postman测试接口时&#xff0c;报了 404 Not Found 的错误&#xff0c;报错截图如下所示 但我的后端程序中已经定义了该接口&#xff0c;如下所示 …

代码随想录算法训练营第三十一天 |基础知识,455.分发饼干,376.摆动序列,53.最大子序和(已补充)

基础知识&#xff1a; 题目分类大纲如下&#xff1a; #算法公开课 《代码随想录》算法视频公开课(opens new window)&#xff1a;贪心算法理论基础&#xff01;(opens new window),相信结合视频再看本篇题解&#xff0c;更有助于大家对本题的理解。 #什么是贪心 贪心的本质…

第一篇【传奇开心果系列】Python的pyttsx3库技术点案例示例:文本转换语言

传奇开心果短博文系列 系列短博文目录Python的pyttsx3库技术点案例示例系列 短博文目录前言一、pyttsx3主要特点和功能介绍二、pyttsx3文字转语音操作步骤介绍三、多平台支持介绍和示例代码四、多语言支持介绍和示例代码五、自定义语言引擎介绍和示例代码六、调整语速和音量介绍…

【Mybatis】从0学习Mybatis(2)

前言 本篇文章是从0学习Mybatis的第一篇文章&#xff0c;由于篇幅太长CSDN会限流&#xff0c;因此我打算分开两期来写&#xff0c;这是第二期&#xff01;第一期在这儿&#xff1a;【Mybatis】从0学习Mybatis&#xff08;1&#xff09;-CSDN博客 1.什么是ResultMap结果映射&am…

【教程】C++语言基础学习笔记(七)——Array数组

写在前面&#xff1a; 如果文章对你有帮助&#xff0c;记得点赞关注加收藏一波&#xff0c;利于以后需要的时候复习&#xff0c;多谢支持&#xff01; 【C语言基础学习】系列文章 第一章 《项目与程序结构》 第二章 《数据类型》 第三章 《运算符》 第四章 《流程控制》 第五章…

蓝桥杯第十四届电子类单片机组程序设计

目录 前言 蓝桥杯大赛历届真题&#xff08;点击查看&#xff09; 一、第十四届比赛题目 1.比赛原题 2.题目解读 1&#xff09;任务要求 2&#xff09;注意事项 二、任务实现 1.NE555读取时机的问题 1&#xff09;缩短计数时间 2&#xff09;实时读取 2.温度传感器读…

机器学习和统计学的区别?

1、本质区别&#xff1a; 目标&#xff1a;机器学习的核心目标是建立一个可以自动学习和改进的模型&#xff0c;以预测未知数据。它更关注结果的准确性和模型的泛化能力&#xff0c;通常不关心模型是否可以解释。而统计学的目标是探究变量之间的关系&#xff0c;理解数据的内在…

算法沉淀——队列+宽度优先搜索(BFS)(leetcode真题剖析)

算法沉淀——队列宽度优先搜索&#xff08;BFS&#xff09; 01.N 叉树的层序遍历02.二叉树的锯齿形层序遍历03.二叉树最大宽度04.在每个树行中找最大值 队列 宽度优先搜索算法&#xff08;Queue BFS&#xff09;是一种常用于图的遍历的算法&#xff0c;特别适用于求解最短路径…

知识价值2-什么是IDE?新手用哪个IDE比较好?

IDE是集成开发环境&#xff08;Integrated Development Environment&#xff09;的缩写&#xff0c;是一种软件应用程序&#xff0c;旨在提供集成的工具集&#xff0c;以方便开发人员进行软件开发。IDE通常包括代码编辑器、编译器、调试器和其他工具&#xff0c;以支持软件开发…

python+django+vue汽车票在线预订系统58ip7

本课题使用Python语言进行开发。基于web,代码层面的操作主要在PyCharm中进行&#xff0c;将系统所使用到的表以及数据存储到MySQL数据库中 使用说明 使用Navicat或者其它工具&#xff0c;在mysql中创建对应名称的数据库&#xff0c;并导入项目的sql文件&#xff1b; 使用PyChar…

PHP开发日志 ━━ 深入理解三元操作与一般条件语句的不同

概况 三元运算符的功能与“if…else”流程语句一致。 在一般情况下&#xff0c;三元操作替换if条件语句可以精简代码&#xff0c;并且更为直观&#xff0c;但是在下面的情况中使用三元操作将会返回警告。 借图&#xff1a; 案例 比如原代码&#xff1a; class classA{publ…

详解tomcat中的jmx监控

目录 1.概述 2.如何开启tomcat的JMX 3.tomcat如何实现JMX的源码分析 1.概述 本文是博主JAVA监控技术系列文章的第二篇&#xff0c;前面一篇文章中我们介绍了JAVA监控技术的基石——jmx&#xff1a; 【JMX】JAVA监控的基石-CSDN博客 本文我们将从使用和源码实现两个方面聊…