第十届蓝桥杯赛前自救-全排列算法

迈不过友情╰ 2022-03-02 15:08 175阅读 0赞

递归回溯生成全排列模板，适用于无重复元素的情况：

void f(int k)
    {
    	if(k==n)//n是范围数 数组下标从0开始
    	{if(check()) ans++;}//符合题目条件的话，ans就++
    	int t=0;
    	for（int i=k;i<n;++i）
    	{
       {t=a[i];a[i]=a[k];a[k]=t;}
    	f(k+1)；//递归
    	{t=a[i];a[i]=a[k];a[k]=t;}//回溯
    	}

若有重复元素，则：

bool isrepeat(int a[],int begin,int end)
    {
    	for(int i=begin;i<end;++i)
    	{
    		if(a[i]==a[end]) return false;
    	}
    	return true;
    }
    void f(int k)
    {
    	if(k==n)//n是范围数 数组下标从0开始
    	{if(check()) ans++;}//符合题目条件的话，ans就++
    	int t=0;
    	for（int i=k;i<n;++i）
    	{
    		if(isrepeat())
    		{
    		{t=a[i];a[i]=a[k];a[k]=t;}
    			f(k+1)；//递归
    			{t=a[i];a[i]=a[k];a[k]=t;}//回溯
    		}
    	}

上面是手写算法，一般来讲不会超时，但是STL库里面也有关于全排列的函数，在填空的时候可以用：next\_permutation

#include <algorithm>
     bool next_permutation(iterator start,iterator end)

但是用这个函数前必须保证序列是从小到大排好序的  
例子：

#include <iostream>
     #include <algorithm>
     using namespace std;
     int a[]={1,2,3,4,5};
     int main()
     {
     do{
     		cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<a[4]<<" "<<endl;
    	 }while(next_permutation(a,a+5);
    	 return 0;
    }

参考文献：[https://blog.csdn.net/hushhw/article/details/78112719][https_blog.csdn.net_hushhw_article_details_78112719]

[https_blog.csdn.net_hushhw_article_details_78112719]: https://blog.csdn.net/hushhw/article/details/78112719

发表评论取消回复

表情：

评论列表（有 0 条评论，175人围观）

还没有评论，来说两句吧...

相关阅读

相关蓝桥杯第十二届真题解析

目录前言考试技巧真题解析第一题（ASC）第二题（卡片）第三题（直线）第四题（货物摆放）第五题（路径）第六题（时间显示）第七

我就是我/ 2023年09月29日 08:49/ 0 赞/ 18 阅读

相关【手链样式】第六届蓝桥杯省赛【C++描述，全排列】

问题描述：小明有3颗红珊瑚，4颗白珊瑚，5颗黄玛瑙。他想用它们串成一圈作为手链，送给女朋友。现在小明想知道：如果考虑手链可以随意转动或翻转，一共可以有多少不

偏执的太偏执、/ 2023年03月04日 06:51/ 0 赞/ 8 阅读

相关蓝桥杯—next_permutation()全排列函数

/ 输出字符串的全排列 / include <iostream> include <algorithm> include <st

ゞ浴缸里的玫瑰/ 2022年06月18日 12:12/ 0 赞/ 170 阅读

相关第十届蓝桥杯赛前自救-全排列算法

递归回溯生成全排列模板，适用于无重复元素的情况： void f(int k) { if(k==n)//n是范围数数组下标从0开始 {if

迈不过友情╰/ 2022年03月02日 15:08/ 0 赞/ 176 阅读

相关第十届蓝桥杯赛前自救

2019.3.29更新：蓝桥杯省赛结果出来了，省三emmmm，有点意料之中吧，其实本来还期待省二的，可能编程大题只是过了样例，编程基础还是差吧。希望自己这半年能好好补基础一点点

客官°小女子只卖身不卖艺/ 2022年03月02日 05:54/ 0 赞/ 217 阅读

相关 2019年第十届蓝桥杯赛后总结

前言：本人湖北一个专科院校软件技术专业大二学生。第一听说蓝桥杯比赛是大一时，在计算机协会里听会长说的，当时才进入大学，对所学的这个专业也不是很了解，高中也没参加过什么比

分手后的思念是犯贱/ 2022年02月28日 13:38/ 0 赞/ 316 阅读

相关第十届蓝桥杯算法竞赛

试题A:组队 > 问题描述： > > 作为篮球队教练，你需要从以下名单中选出 1 号位至 5 号位各一名球员，组成球队的首发阵容。 > > 每位球员担任 1 号

太过爱你忘了你带给我的痛/ 2022年02月28日 04:04/ 0 赞/ 271 阅读

相关第十届蓝桥杯省赛

这是个悲伤的故事今天，第十届蓝桥杯比赛成绩公布了，我是第一次参加蓝桥杯（校内选拔不算），个人觉得，这次比赛的题目大都不难，甚至有部分真的太容易了，　　但是我的成绩

Dear 丶/ 2022年02月26日 13:42/ 0 赞/ 367 阅读

相关 2019第十届蓝桥杯国赛总结

这是第一次去外地参加比赛，加上，近些年来很少去北京，因此非常期待这次去北京参加比赛的机会。由于学校离北京比较远，我们只能坐火车前往。火车上的时间无比漫长，我只能与同学

逃离我推掉我的手/ 2021年12月12日 02:15/ 0 赞/ 456 阅读

相关蓝桥杯第八届迷宫

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

我不是女神ヾ/ 2021年07月17日 01:57/ 0 赞/ 491 阅读