蓝桥杯: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.mfbz.cn/a/388990.html

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

相关文章

《合成孔径雷达成像算法与实现》Figure6.18

% rho_r c/(2*Fr)而不是rho_r c/(2*Bw) % Hsrcf exp函数里忘记乘pi了 clc clear close all参数设置 距离向参数设置 R_eta_c 20e3; % 景中心斜距 Tr 2.5e-6; % 发射脉冲时宽 Kr 20e12; % 距离向调频率 alpha_os_r 1.2; …

如何使用六图一表七种武器

六图一表七种武器用于质量管理&#xff1a; 描述当遇到问题时应该用那张图来解决&#xff1a; 一、如果题目说出了质量问题需要找原因&#xff1f; 解&#xff1a;用因果图&#xff0c;因果图也称石川图或鱼骨图 二、如果要判断过程是否稳定受控&#xff1f; 解&#xff1a…

【zabbix】(五)-自定义监控项:MySQL主从状态-自动告警

一 查看主从状态 二 在zabbix-agent端配置监控脚本 2.1 首先定义监控项 [rootmysql-112 conf]# mysql -uroot -pLXYlxy2:024.#8u} -e "show slave status\G" | grep -w Slave_IO_Running | awk {print $2} mysql: [Warning] Using a password on the command line…

UI设计常见风格(1):一文读懂九个,教你如何辨识。

Hello&#xff0c;我是大千UI工场&#xff0c;设计风格是我们新开辟的栏目&#xff0c;上次讲了毛玻璃风格、辨识方法、应用场景、运用方法等&#xff0c;很受大家欢迎&#xff0c;本次带来常见的风格及辨识&#xff0c;让大家有个总览&#xff0c;以后会逐个讲解的&#xff0c…

Python一些可能用的到的函数系列124 GlobalFunc

说明 GlobalFunc是算网的下一代核心数据处理基础。 算网是一个分布式网络&#xff0c;为了能够实现真的分布式计算&#xff08;加快大规模任务执行效率&#xff09;&#xff0c;以及能够在很长的时间内维护不同版本的计算方法&#xff0c;需要这样一个对象/服务来支撑。Globa…

学法减分线上考试答案查找?分享九个搜题直接出答案的软件 #媒体#媒体#笔记

在信息爆炸的时代&#xff0c;选择适合自己的学习辅助工具和资料&#xff0c;能够提供更高效、便捷和多样化的学习方式。 1.试题猪 这是个微信公众号 一款聚合了好多款搜题软件的公众号&#xff0c;对话框可以直接搜题&#xff0c;题库好像挺多的&#xff0c;一次性能出好多…

计算机二级数据库之数据模型(三层相关的结构)

数据模型 模型的概念 模型的介绍模型是对现实世界特征的模拟和抽象&#xff0c; 数据模型的概念&#xff1a; 数据模型是对现实世界中数据特征的抽象&#xff0c;描述的是数据的共性。 数据模型是用来在数据库中抽象、表示和处理现实世界中的数据和信凹。 其相关的共同特…

阿里云幻兽帕鲁服务器中据点帕鲁数量上限是修改哪个参数?

在阿里云的计算巢管理中&#xff0c;找到你的这台部署幻兽帕鲁的服务器实例&#xff0c;选择右上角的“修改游戏配置” 然后选择“基地内工作帕鲁的最大数量”改成20 不过也有同学说更改上面的数字&#xff0c;根本不起作用。 参考资料&#xff1a;大多数人现在都知道&#xf…

AGV|RGV基本概念及导航分类与差异

AGV是自动导引运输车&#xff0c;装备采用电磁或光学等自动导引装置&#xff0c;能够沿规定的导引路径行驶&#xff0c;具有安全保护以及各种移载功能的运输车。其导航方式主要分磁条|磁钉导航、激光导航、激光反光板、激光自然导航、二维码导航、惯性导航等方式&#xff0c;广…

【51单片机】利用STC-ISP软件工具【定时器计算器】配置【定时器】教程(详细图示)(AT89C52)

前言 大家好吖&#xff0c;欢迎来到 YY 滴单片机系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过单片机的老铁 主要内容含&#xff1a; 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; YY的《C》专栏YY的《C11》专栏YY的…

OpenAI全新发布文生视频模型Sora - 现实,不存在了

OpenAI&#xff0c;发他们的文生视频大模型&#xff0c;Sora了。。。。。 而且&#xff0c;是强到&#xff0c;能震惊我一万年的程度。。。 https://openai.com/sora 如果非要用三个词来总结Sora&#xff0c;那就是“60s超长长度”、“单视频多角度镜头”和“世界模型” &am…

一周学会Django5 Python Web开发-项目配置settings.py文件-资源文件配置

锋哥原创的Python Web开发 Django5视频教程&#xff1a; 2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~共计17条视频&#xff0c;包括&#xff1a;2024版 Django5 Python we…

深度学习之梯度下降算法

梯度下降算法 梯度下降算法数学公式结果 梯度下降算法存在的问题随机梯度下降算法 梯度下降算法 数学公式 这里案例是用梯度下降算法&#xff0c;来计算 y w * x 先计算出梯度&#xff0c;再进行梯度的更新 import numpy as np import matplotlib.pyplot as pltx_data [1.0,…

紫微斗数双星组合:武曲破军在巳亥

文章目录 前言内容总结 前言 紫微斗数双星组合&#xff1a;武曲破军在巳亥 内容 紫微斗数双星组合&#xff1a;武曲破军在巳亥 性格分析 在紫微斗数命盘中&#xff0c;武曲星入命之人性格大都为正直、刚强、果决、重视原则。假如与破军星同守命宫时&#xff0c;身边的破军是…

【防网盘在线解压】Peazip 豌豆压缩 v9.7.0

软件介绍 Peazip 是一个免费的文件归档应用程序&#xff0c; 支持跨平台&#xff0c;是和WinRar、WinZip类似软件的开源免费替代品&#xff1b;支持压缩/ 存档到 7Z&#xff0c; ARC、Brotli BR、BZip2、GZip、 PAQ、PEA、RAR、自解压档案、TAR、WIM、XZ、Zstandard ZST、打开…

如何为你的幻兽帕鲁服务器手动配置虚拟内存或Swap、Zram

其实非常简单&#xff0c;如果是Windows系统服务器的话&#xff0c;直接远程连接到服务器桌面。 连上之后&#xff0c;打开设置&#xff0c;找到“高级系统设置” 可以参考视频教程&#xff1a; 拒绝卡顿&#xff01;幻兽帕鲁服务器内存优化攻略&#xff01; 详细教程地址&…

多进程面试题汇总

这里写目录标题 一、多进程1、进程的定义&#xff1a;2、单核多任务CPU执行原理3、进程的优点和缺点4、创建进程15、创建进程26、进程池6.1、进程池的作用6.2、原理图6.3、使用进程池的优点 7、进程间的通信&#xff08;Queue&#xff09;7.1、需求1&#xff1a;采用多进程将10…

《合成孔径雷达成像算法与实现》FIgure6.20

% rho_r c/(2*Fr)而不是rho_r c/(2*Bw) % Hsrcf exp函数里忘记乘pi了 clc clear close all参数设置 距离向参数设置 R_eta_c 20e3; % 景中心斜距 Tr 2.5e-6; % 发射脉冲时宽 Kr 20e12; % 距离向调频率 alpha_os_r 1.2; …

【经验】JLINK无法(单步)调试,JLINK固件的烧写

昨天终于准备开始进行S3C6410的裸机开发&#xff0c;写好了程序&#xff0c;编译生成了.axf文件&#xff0c;一切顺利的准备利用JLINK进行在线调试了&#xff0c;突然有种成功就在前面的感觉&#xff0c;Jlink也能被电脑正常的识别&#xff0c;利用AXD进行Jlink的相关设置也很正…

[office] Excel CHITEST 函数 使用实例教程 #媒体#知识分享#其他

Excel CHITEST 函数 使用实例教程 提示 此函数已由 CHISQ.TEST 函数替换&#xff0c;新函数可以提供更好的精确度&#xff0c;其名称更好地反映其用法。旧函数仍可用于与早期版本Excel 的兼容。但是&#xff0c;如果不需要向后兼容&#xff0c;那么应考虑直接使用新函数&…