蓝桥杯准备每日练习|【蓝桥杯技巧篇】next_permutation全排列详解算法|c++|蓝桥杯

欢迎关注
蓝桥杯每日练习合集
共同努力。

文章目录

一，next_permutation全排列
- 算法思想：
- 算法模板
二，上真题
- 算式问题
三，再来一道真题
- 凑算式

一，next_permutation全排列

头文件

next_permutation是一个非常强大的全排列函数，合理的使用它可以省去繁琐的打表流程。
算法思想：

1.首先从最尾端开始往前寻找两个相邻元素，令第一元素为i,第二元素为ii,且满足i<ii。
2.找到这样一组相邻元素后，再从最尾端开始往前检验，找出第一个大于i的元素，令为j，将i,j元素对调(swap)。
3.再将ii之后的所有元素颠倒(reverse)排序。
使用方法：next_permutation(数组头地址，数组尾地址); 若下一个排列存在，则返回真，如果不存在则返回假

算法模板

int a[10] = {1,2,3,4,5,6,7,8,9},sum=0; while(next_permutation(a,a+9)) { }

二，上真题算式问题本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
看这个算式：
☆☆☆ + ☆☆☆ = ☆☆☆
如果每个五角星代表 1 ~ 9 的不同的数字。
这个算式有多少种可能的正确填写方法？

#include using namespace std; int main() { int a[10] = {1,2,3,4,5,6,7,8,9},sum=0; while(next_permutation(a,a+9)) { int q,w,e; q=a[0]*100+a[1]*10+a[2]; w=a[3]*100+a[4]*10+a[5]; e=a[6]*100+a[7]*10+a[8]; if(q+w==e) {sum++; }} cout<; return 0; }

答案：

336

合理运用全排列函数，加快效率。
三，再来一道真题凑算式

标签：2016 省赛填空

题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

BDEF A + --- + ------- = 10 CGHI

这个算式中 A ~ I 代表 1 ~ 9 的数字，不同的字母代表不同的数字。
比如：

6+8/3+952/714 就是一种解法， 5+3/1+972/486 是另一种解法。

这个算式一共有多少种解法？

运行限制最大运行时间：1s 最大运行内存: 128M

思路：全排列用起来，还有一点，这道题通分很关键。
尝试把他们通分计算、
看我的解法：

#include using namespace std; int main() {//a,b,c,d,e,f,g,h,i //0,1,2,3,4,5,6,7,8 int a[10] = {1,2,3,4,5,6,7,8,9},sum=0; while(next_permutation(a,a+9)) { double xx,xxx; xx=a[3]*100+a[4]*10+a[5]; xxx=a[6]*100+a[7]*10+a[8]; if((xx*a[2]+a[1]*xxx)/(xxx*a[2])==10-a[0]) { sum++; }} cout<; return 0; }

答案：

29

这道题要注意乘法，这里有坑。
【蓝桥杯准备每日练习|【蓝桥杯技巧篇】next_permutation全排列详解】总结：
next_permutation()是按照字典序产生排列的，并且是从数组中当前的字典序开始依次增大直至到最大字典序。全排列功能强大，要善于用运。比手动排列省时的多。
对于蓝桥题目说是1~9不重复，给出一个条件，大概率用全排列函数可以解决的。