蓝桥杯之全排列函数next_permutation()运用

2019-11-11 01:26:41

字体：大中小

来源：转载

供稿：网友

在蓝桥杯的题目中大多数都可以运用到全排列函数充分运用可以节省很多的时间。话不多说来刷题

三羊献瑞观察下面的加法算式：祥瑞生辉

+ 三羊献瑞

三羊生瑞气 (如果有对齐问题，可以参看【图1.jpg】)其中，相同的汉字代表相同的数字，不同的汉字代表不同的数字。请你填写“三羊献瑞”所代表的4位数字（答案唯一），不要填写任何多余内容。

看到这题一看就知道用暴力搜索法，代码如下

#include<iostream>using namespace std;int check(int num[],int n){ for(int i = 0; i < n; i++) { if(num[i]==num[n]) { return 0; } } return 1;}int main(){ int num[8]; int count = 0; for(num[0] = 1; num[0] <=9; num[0]++) { if(check(num,0)) for(num[1] = 0; num[1] <=9; num[1]++) { if(check(num,1)) for(num[2] = 0; num[2] <=9; num[2]++) { if(check(num,2)) for(num[3] = 0; num[3] <=9; num[3]++) { if(check(num,3)) for(num[4] = 1; num[4] <=9; num[4]++) { if(check(num,4)) for(num[5] = 0; num[5] <=9; num[5]++) { if(check(num,5)) for(num[6] = 0; num[6] <=9; num[6]++) { if(check(num,6)) for(num[7] = 0; num[7] <=9; num[7]++) { if(check(num,7)) { int a = num[0]*1000+num[1]*100+num[2]*10+num[3]; int b = num[4]*1000+num[5]*100+num[6]*10+num[1]; int c = num[4]*10000+num[5]*1000+num[2]*100+num[1]*10+num[7]; if(a+b==c) { cout << b; } } } } } } } } }} return 0;}

看了一下六十多行，啊，学这么多好累啊！对于这种超过5个循环以上的暴力可以考虑用全排列函数第二种方法如下：

#include<iostream>#include<algorithm>using namespace std;int main1(){ int num[10] = {1,0,2,3,4,5,6,7,8,9}; int count = 0; do { if(num[0]!=0&&num[4]!=0) { int a = num[0]*1000+num[1]*100+num[2]*10+num[3]; int b = num[4]*1000+num[5]*100+num[6]*10+num[1]; int c = num[4]*10000+num[5]*1000+num[2]*100+num[1]*10+num[7]; if(a+b==c) { cout << b; break; } } }while(next_permutation(num,num+10)); return 0;}

这就简便多了，这里注意到题目答案唯一所以当瞒住条件后就可以跳出循环，算法的时间就可以大大减少自己总结了一下运用全排列的环境

五重循环以上数字不能重复要有顺序

上一篇：C 链表 - linux 如何实现

下一篇：1076. Forwards on Weibo (30)