C++ next_permutation

【蓝桥杯程序设计⼤赛感想】⼀路艰⾟⼀路收获故事开始：2014年来到⼤学，第⼀时间就听闻蓝桥杯，再听闻这个⽐赛全国总决赛的⽐赛地点是北京，我内⼼中瞬间涌现出⼀个信念：北京我是去定的了！我中职读的是计算机⽹络专业，期间⾃学了C语⾔，怀着试⼀试的⼼态⾃⼰⼀⼈搭车到佛⼭⼤学参加了下全国⼆级C语⾔的考试，当时报考后就买了⼀套未来教育出版的C语⾔教程和模拟题库，接下来就是⼀系列的题海战术，那段时间我是好充实，毕竟有个明确的⽬标，查成绩的时候68分！开⼼的我晚上差点没睡着，毕竟只是懂⼀点基础的知识，可以说连编写⼀个Hello world也要调试那么N次。

⼤⼀的时候虽然是意⽓风发，不过还是连个蓝桥杯校内的选拔赛都不敢参加，我⾃知能⼒不⾜，没那个底⽓也没那个勇⽓….⼤⼆我再听闻蓝桥时，让我想起了当初的誓⾔和约定，便⼀⾔不发的踏⼊了征程。

⼤⼆的我早已把C语⾔遗忘了，好在⼤⼀第⼆学期有C++课程，当时授课的是胡建荣⽼师，我把更多的时间和精⼒投⼊到C++知识的汲取和实践上，很快就熟悉了C++的基础知识，但我知道要应对校内的C++编程⾼⼿，⼴东省内各⾼校的⽜⼈甚⾄全国各省份的精英⼈才，我知道⾃⼰有多么的不⾜。

校内选拔：通过校内选拔赛我了解到了：程序=算法+数据结构，⽽数据结构和算法我还有很多很多是不甚了解的，线段树、AC⾃动机、KMP算法、DP、图论、平衡⼆叉树等等。

看着都头晕，但是⼜有谁是⽣来就会这些呢？想得到未曾拥有的，就要付出未曾付出的。

这是我⼀直以来的座右铭。

寒假当⼈⼈都沉醉在春节的欢声笑语中时，我却独⾃⼀⼈踏上了算法的道路，我喜欢安静独处的学习。

寒假我搜索了⼤量的学习资料，最终选择了学习鱼C论坛⼩甲鱼⽼师的数据结构和算法课程。

可以说他让我更清晰透彻的了解到程序设计的核⼼。

通过⼀个⽉的闭关学习，我⼤概了解了程序的底层运作原理，发现原来程序还可以这样写！那就像是发现了新⼤陆那样。

现实始终是残酷的，学到不⼀定⽤到。

在题库练习的过程中，我经历了⽆数的编译失败，⽆数的超时提醒，⽆数的数据溢出，⽆数的失败失败失败…..“⽣活就像海洋，只有意志坚强的⼈才能达到⽣命的彼岸。

排列组合算法基本概念从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。

当m=n时所有的排列情况叫全排列。

P(n,m)=n(n-1).(n-m+1)=n!-(n-m)! 特别的，定义0!=1组合数公式是指从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。

用符号c(n,m) 表示。

c(n,m)=p(n,m)-m!=n!-((n-m)!*m!)3、计算公式排列算法递归算法#include stdio.hvoid swap(int *a, int *b)void perm(int list[], int k, int m)for(i = 0; i = m; i++)printf("%d ", list[i]);printf("");for(i = k; i = m; i++)swap(list[k], list[i]);perm(list, k + 1, m);swap(list[k], list[i]);int main()int list[] = {1, 2, 3, 4, 5};perm(list, 0, 4);printf("total:%d", n);return 0;template typename Tinline void swap(T* array, unsigned int i, unsigned int j) T t = array[i];array[i] = array[j];array[j] = t;* 递归输出序列的全排列void FullArray(char* array, size_t array_size, unsigned int index)if(index = array_size)for(unsigned int i = 0; i array_size; ++i)cout array[i] ' ';for(unsigned int i = index; i array_size; ++i)swap(array, i, index);FullArray1(array, array_size, index + 1);swap(array, i, index);#include "iostream"using namespace std;void permutation(char* a,int k,int m)if(k == m)span style="white-space:pre"-spanfor(i=0;i=m;i++) span style="white-space:pre"-spancouta[i]; coutendl;for(j=k;j=m;j++)swap(a[j],a[k]);permutation(a,k+1,m);swap(a[j],a[k]);int main(void)char a[] = "abc";couta"所有全排列的结果为："endl;permutation(a,0,2);system("pause");return 0;}#include "iostream"#include "algorithm"using namespace std;void permutation(char* str,int length)sort(str,str+length);for(int i=0;ilength;i++)coutstr[i];coutendl;}while(next_permutation(str,str+length));int main(void)char str[] = "acb";coutstr"所有全排列的结果为："endl;permutation(str,3);system("pause");return 0;}--- 求从数组a[1.n]中任选m个元素的所有组合。

字符串的排列组合算法合集全排列在笔试面试中很热门，因为它难度适中，既可以考察递归实现，又能进一步考察非递归的实现，便于区分出考生的水平。

所以在百度和迅雷的校园招聘以及程序员和软件设计师的考试中都考到了，因此本文对全排列作下总结帮助大家更好的学习和理解。

对本文有任何补充之处，欢迎大家指出。

首先来看看题目是如何要求的（百度迅雷校招笔试题）。

一、字符串的排列用C++写一个函数, 如 Foo(const char *str), 打印出 str 的全排列,如 abc 的全排列: abc, acb, bca, dac, cab, cba一、全排列的递归实现为方便起见，用123来示例下。

123的全排列有123、132、213、231、312、321这六种。

首先考虑213和321这二个数是如何得出的。

显然这二个都是123中的1与后面两数交换得到的。

然后可以将123的第二个数和每三个数交换得到132。

同理可以根据213和321来得231和312。

因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。

找到这个规律后，递归的代码就很容易写出来了：view plaincopy#includeiostream?using?namespace?std;?#includeassert.h?v oid?Permutation(char*?pStr,?char*?pBegin)?{?assert(pStr?pBegin);?if(*pBegin?==?'0')?printf("%s",pStr);?else?{?for(char *?pCh?=?pBegin;?*pCh?!=?'0';?pCh++)?{?swap(*pBegin,*pCh);?P ermutation(pStr,?pBegin+1);?swap(*pBegin,*pCh);?}?}?}?int?m ain(void)?{?char?str[]?=?"abc";?Permutation(str,str);?retur n?0;?}?另外一种写法：view plaincopy--k表示当前选取到第几个数，m表示共有多少个数?void?Permutation(char*?pStr,int?k,int?m)?{?assert(pStr); if(k==m){staticintnum=1;--局部静态变量，用来统计全排列的个数?printf("第%d个排列t%s",num++,pStr);?}?else?{?for(int?i?=?k;?i?=?m;?i++)?{?swa p(*(pStr+k),*(pStr+i));?Permutation(pStr,?k?+?1?,?m);?swap( *(pStr+k),*(pStr+i));?}?}?}?int?main(void)?{?char?str[]?=?" abc";?Permutation(str?,?0?,?strlen(str)-1);?return?0;?}?如果字符串中有重复字符的话，上面的那个方法肯定不会符合要求的，因此现在要想办法来去掉重复的数列。

Delphi是一种强大的编程语言，可以用于开发各种类型的应用程序，包括字符串操作。

在Delphi中，可以使用一组字符串来生成所有可能的组合情况。

在本文中，我们将探讨如何使用Delphi来实现这一功能，并给出具体的代码示例，以便读者能够清楚地了解该过程。

1. 我们需要创建一个Delphi项目。

打开Delphi集成开发环境（IDE），并选择“新建项目”->“VCL Forms 应用程序”来创建一个新的窗体应用程序项目。

2. 在新建的项目中，我们需要添加一个按钮和一个编辑框控件。

按钮用于触发生成组合的操作，而编辑框用于输入字符串。

3. 在按钮的单击事件中，我们将编写代码来实现生成所有可能的组合情况。

代码的具体实现如下：```pascalprocedure TForm1.Button1Click(Sender: TObject);varstr: string;i: Integer;perm: TStrings;beginstr := Edit1.Text;perm := TStringList.Create;try// 生成所有可能的组合情况repeatperm.Add(str);until not NextPermutation(str);// 输出所有组合情况for i := 0 to perm.Count - 1 doMemo1.Lines.Add(perm[i]);finallyperm.Free;end;end;```在上述代码中，我们首先获取用户输入的字符串，并将其保存到一个变量中。

我们创建一个TStringList对象来存储所有可能的组合情况。

接下来，我们使用一个循环来生成所有可能的排列组合，并将它们添加到TStringList对象中。

我们将所有的组合情况输出到Memo控件中。

4. 我们需要实现一个用于生成下一个排列组合的函数NextPermutation。

该函数的具体实现如下：```pascalfunction NextPermutation(var str: string): Boolean; vari, j, n: Integer;temp: string;beginResult := False;n := Length(str);// 找到最后一个递减的位置i := n - 2;while (i >= 0) and (str[i] > str[i + 1]) doDec(i);if i >= 0 thenbegin// 找到大于str[i]的最小值j := n - 1;while (str[j] < str[i]) doDec(j);// 交换str[i]和str[j]的值temp := str[i];str[i] := str[j];str[j] := temp;// 反转str[i+1]至末尾的部分ReverseString(Copy(str, i + 1, n - i));Result := True;end;end;```在上述代码中，NextPermutation函数实现了生成下一个排列组合的逻辑。

求int的上限与下限#include <stdio.h>//运行时间长,请等待.int main(){int min ,max;FILE *fin,*fout;fin=fopen("min of int.out","wb");fout=fopen("max of int.out","wb");for(min=-1;min<0;){min-- ;}fprintf(fin,"%d\n",min+1);for(max=1;max>0;){max++ ;}fprintf(fout,"%d\n",max-1);fclose(fin);fclose(fout);return 0;}1-1#include <stdio.h>int main(){int a,b,c;scanf("%d%d%d",&a,&b,&c);double average;average=(a+b+c)/3.0; //一定要将int型转为浮点型printf("Average=%.3lf",average );system("pause");return 0;}1-2#include <stdio.h>int main(){double f,c;printf("请输入华氏温度f\n");scanf("%lf",&f);c=(f-32)*5/9 ;printf("摄氏温度c=%.3lf\n",c);return 0;}1-3#include <stdio.h>int main(){int n;scanf("%d",&n);printf("%d\n",(1+n)*n/2) ;system("pause");return 0;}1-4#include <stdio.h>#include <math.h>int main(){const double pi =4.0*atan(1.0);int n;scanf("%d",&n);while(n>=360){printf("请输入小于360°的角\n");scanf("%d",&n);}printf("正弦:%lf\n余弦:%lf",sin(n*pi/180),cos(n*pi/180));system("pause");return 0;}1-5#include <stdio.h>#include <math.h>int main(){double x1,y1,x2,y2;printf("请输入点A的坐标\n");scanf("%lf%lf",&x1,&y1);printf("请输入点B的坐标\n");scanf("%lf%lf",&x2,&y2);double d;d=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));printf("%.3lf\n",d);return 0;}1-6#include <stdio.h>int main(){int a;scanf("%d",&a);if(a%2==0)printf("该数是偶数");else printf("该数非偶数");system("pause");return 0;}1-7#include <stdio.h>int main(){const int a=95;int n;printf("你要买多少件衣服\n");scanf("%d",&n);if(a*n>=300)printf("需要%.2lf元\n",a*n*0.85);else printf("需要%.2lf元\n",(double)a*n); //由于输出是小数%.2lf,故一定要将int型转化为浮点型system("pause");return 0;}1-8#include <stdio.h>#include <stdio.h>int main(){double a;scanf("%lf",&a);if(a>0)printf("%.2lf",a);else printf("%.2lf",-a);system("pause");return 0;}1-9(方法一)#include <stdio.h>int main(){int a,b,c,max,min,middle;scanf("%d%d%d",&a,&b,&c);while(a<0||b<0||c<0){printf("三边必须都是大于零的正整数");scanf("%d%d%d",&a,&b,&c);}min=a;if(a>b)min=b;if(a>c)min=c;max=a;if(a<b)max=b;if(a<c)max=c;middle=a+b+c-min-max;if(min+middle>max)printf("yes");else printf("no");system("pause");return 0;}1-9(方法二) #include <stdio.h>int main(){int a,b,c,t=0;scanf("%d%d%d",&a,&b,&c);while(a<0||b<0||c<0){printf("三边必须都是大于零的正整数");scanf("%d%d%d",&a,&b,&c);}if(a>b){t=a;a=b;b=t;}if(a>c){t=a;a=c;c=t;}if(b>c){t=b;b=c;c=t;}if(a+b>c)printf("yes");else printf("no");system("pause");return 0;}1-10#include <stdio.h>int main(){int n;scanf("%d",&n);if(n%4==0){if(n%100==0){if(n%400==0){printf("yes");}else printf("no");}else printf("yes");}else printf("no");system("pause");return 0;}3n+1解决篇1#include <stdio.h>int main(){int count=0;double i,m;scanf("%lf",&i);for(;i>1;){m=i/2;if(floor(m+0.5)!=m){i=3*i+1;i/=2;count+=2;}//floor(x)取x的整数部分.else {i/=2;count++;}}printf("%d\n",count);system("pause");return 0;}3n+1解决篇2#include<stdio.h>int main(){long long n, count = 0;//long long 的取值范围:-2^63~2^63-1scanf("%I64d", &n);while(n > 1) {if(n % 2 == 1) n = n*3+1;else n /= 2;count++;}printf("%I64d\n", count);return 0;}数据统计解决篇#include <stdio.h>int main(){int x,n=0,s=0,min,max;while(scanf("%d",&x)==1){if(n==0){min=max=x;}//读取第一个数的时候将第一个数赋值给min和max s+=x;if(x<min)min=x;if(x>max)max=x;n++;}printf("%d %d %.3lf\n",min,max,(double)s/n);system("pause");return 0;}2-1(fin)#include <stdio.h>int main(){FILE *fin,*fout;fin=fopen("digit.in","rb");fout=fopen("digit.out","wb");/*fin=stdin;fout=stdout;*/int a,i=0;fscanf(fin,"%d",&a);while(1){a/=10;i++;if(a<1)break;}fprintf(fout,"%d\r\n",i);fclose(fin);fclose(fout);//system("pause");return 0;}2-1(freopen)#include <stdio.h>//#define LOCAL//在编译选项中定义LOCALint main(){#ifdef LOCALfreopen("digit.in","r",stdin);freopen("digit.out","w",stdout);#endifint a,i=0;scanf("%d",&a);while(1){a/=10;i++;if(a<1)break;}printf("%d\n",i);return 0;}2-2(freopen)#include <stdio.h>//#define LOCAL//编译选项中定义int main(){#ifdef LOCALfreopen("daffodil.out","w",stdout);#endifint a,b,c,m;for(a=1;a<=9;a++){for(b=0;b<=9;b++){for (c=0;c<=9;c++){m=a*100+b*10+c;if(m==a*a*a+b*b*b+c*c*c)printf("%d\n",m);}}}//system("pause");return 0;}2-2(fin)#include <stdio.h>int main(){FILE *fout;fout=fopen("daffodil.out","wb");int a,b,c,m;for(a=1;a<=9;a++){for(b=0;b<=9;b++){for(c=0;c<=9;c++){m=a*a*a+b*b*b+c*c*c;if(m==a*100+b*10+c)fprintf(fout,"%d\r\n",m);}}}fclose(fout);return 0;}2-3(fin)#include<stdio.h>int main(){FILE *fin,*fout;fin=fopen("hanxin.in","rb");fout=fopen("hanxin.out","wb");//fin=stdin;//fout=stdout;int a,b,c,x,temp=0;//temp用来判断是否在10到100内存在这样的数fscanf(fin,"%d%d%d",&a,&b,&c);for(x=10;x<=100;x++){if(x%3==a&&x%5==b&&x%7==c){fprintf(fout,"%d\r\n",x);temp=1;break;}}if(!temp)fprintf(fout,"No answer\r\n");fclose(fin);fclose(fout);return 0;}2-3(freopen)#include<stdio.h>{//会在编译选项中定义LOCAL#ifdef LOCALfreopen("hanxin.in","r",stdin);freopen("hanxin.out","w",stdout);#endifint a,b,c,x,temp=0;scanf("%d%d%d",&a,&b,&c);for(x=10;x<=100;x++){if(x%3==a&&x%5==b&&x%7==c){printf("%d\n",x);temp=1;break;}}if(!temp)printf("No answer\n");return 0;}2-4(fin)#include<stdio.h>int main(){FILE *fin,*fout;fin=fopen("triangle.in","rb");fout=fopen("triangle.out","wb");//fin=stdin;//fout=stdout;int n,i,j,k;fscanf(fin,"%d\r\n",&n);for(i=1;i<=n;i++){for(j=1;j<i;j++)fprintf(fout," ");for(k=-2*i+2*n+1;k>=1;k--)fprintf(fout,"*");fprintf(fout,"\r\n");}fclose(fin);fclose(fout);return 0;}2-4(freopen)#include<stdio.h>{//在编译选项内定义LOCAL#ifdef LOCALfreopen("triangle.in","r",stdin);freopen("triangle.out","w",stdout);#endifint n,i,j,k;scanf("%d",&n);for(i=1;i<=n;i++){for(j=1;j<i;j++)printf(" ");for(k=2*n+1-2*i;k>=1;k--)printf("*");printf("\n");}return 0;}2-5(fin)#include<stdio.h>int main(){FILE *fin,*fout;fin=fopen("stat.in","rb");int n,a,i,m,count=0;fscanf(fin,"%d",&n);for(i=1;i<=n+1;i++){fscanf(fin,"%d",&a);if(i==n+1)m=a;}fclose(fin);fin=fopen("stat.in","rb");for(i=0;i<=n;i++){fscanf(fin,"%d",&a);if(i!=0){if(a<m)count++;}}fclose(fin);fout=fopen("stat.out","wb");fprintf(fout,"%d\r\n",count);fclose(fout);return 0;}2-5(freopen) #include<stdio.h>int main(){freopen("stat.in","r",stdin);freopen("stat.out","w",stdout);int n,a,i,m,count=0;scanf("%d",&n);for(i=1;i<=n+1;i++){scanf("%d",&a);if(i==n+1)m=a;}freopen("stat.in","r",stdin);for(i=0;i<=n;i++){scanf("%d",&a);if(i!=0){if(a<m)count++;}}printf("%d\n",count);return 0;}2-6(fin) #include<stdio.h>int main(){FILE *fin,*fout;fin=fopen("harmony.in","rb");int n,i;double H=0;fscanf(fin,"%d",&n);for(i=1;i<=n;i++){H+=(double)1/i;}fclose(fin);fout=fopen("harmony.out","wb");fprintf(fout,"%.3lf\r\n",H);fclose(fout);return 0;}2-6(freopen) #include<stdio.h>int main(){#ifdef LOCALfreopen("harmony.in","r",stdin);freopen("harmony.out","w",stdout);#endifint n,i;double H=0;scanf("%d",&n);for(i=1;i<=n;i++){H=H+double/i;}printf("%.3lf",H);return 0;}2-7(fin) #include<stdio.h>int main(){FILE *fout;int i;double H=0;for(i=1;2*i-1<1000000;i++){if(i%2==1)H+=(double)1/(2*i-1);else H-=(double)1/(2*i-1);}fout=fopen("approximation.out","wb");fprintf(fout,"%lf\r\n",H);return 0;}2-7(freopen) #include<stdio.h>int main(){#ifdef LOCALfreopen("approximation.in","r",stdin);freopen("approximation.out","w",stdout);#endifint i;double H=0;for(i=1;2*i-1<1000000;i++){if(i%2==1)H+=(double)1/(2*i-1);else H-=(double)1/(2*i-1);}printf("%lf",H);return 0;}2-8(fin,double)#include<stdio.h>#include<time.h>int main(){FILE *fin,*fout;fin=fopen("subsequence.in","rb");fout=fopen("subsequence.out","wb");int n,m,i;double H=0;double ii;fscanf(fin,"%d%d",&n,&m);for(i=n;i<=m;i++){ii=(double)i*i;H+=1/ii;}fprintf(fout,"%.5lf\r\n",H);fprintf(fout,"%.2lf\r\n",(double)clock()/CLOCKS_PER_SEC);//比较double和long long运行效率fclose(fin);fclose(fout);return 0;}2-8(fin,long long)#include<stdio.h>#include<time.h>int main(){FILE *fin,*fout;fin=fopen("subsequence.in","rb");fout=fopen("subsequence.out","wb");int n,m,i;double H=0;fscanf(fin,"%d%d",&n,&m);for(i=n;i<=m;i++){long long ii=1;//定义ii=ii*i*i; //不用ii=i*i也不是ii*=i*i,这样做是为了防止i*i溢出; 可以认为这一步将int型转化为long long 型H+=1/(double)ii;//不是(double)1/ii}fprintf(fout,"%.5lf\r\n",H);fprintf(fout,"%.2lf\r\n",(double)clock()/CLOCKS_PER_SEC); ////比较double和long long运行效率fclose(fin);fclose(fout);return 0;}2-8(freopen)#include<stdio.h>#define LOCALint main(){#ifdef LOCALfreopen("subsequence.in","r",stdin);freopen("subsequence.out","w",stdout);#endifint n,m,i;double H=0,ii;scanf("%d%d",&n,&m);for(i=n;i<=m;i++){H+=1/((double)i*i);}printf("%.5lf\n",H);return 0;}2-9(fin)#include<stdio.h>int main(){FILE *fin,*fout;fin=fopen("decimal.in","rb");fout=fopen("decimal.out","wb");int a,b,c;fscanf(fin,"%d%d%d",&a,&b,&c);fprintf(fout,"%.*lf\r\n",c,(double)a/b);fclose(fin);fclose(fout);return 0;}2-9(freopen)#include<stdio.h>int main(){#ifdef LOCALfreopen("decimal.in","r",stdin);freopen("decimal.out","w",stdout);#endifint a,b,c;scanf("%d%d%d",&a,&b,&c);printf("%.*lf",c,(double)a/b);return 0;}2-10(全书看完再看这段代码) #include<cstdio>#include<algorithm>using namespace std;int main(){freopen("permutation.ans","w",stdout);int d[]={1,2,3,4,5,6,7,8,9};do{int a=d[0]*100+d[1]*10+d[2];int b=d[3]*100+d[4]*10+d[5];int c=d[6]*100+d[7]*10+d[8];if(c==3*a&&b==2*a)printf("%d %d %d\n",a,b,c);}while(next_permutation(d,d+9));return 0;}。

蓝桥杯常考算法+知识点素数判断/素数筛埃⽒筛：const int N=10010;int prime[N];bool book[N]; // =1 表⽰不是素数void w(){book[0]=book[1]=1;// book[2]=1;int cnt=0;for(int i=1; i<=N; i++){if(!book[i]){prime[cnt++]=i;for(int j=i+i; j<=N; j+=i);book[j]=1;}}}朴素判断素数：int w(int n){for(int i=2; i<=sqrt(n); i++)if(i%n==0) return 0; //不是素数return 1; //是素数}进制转换int main(){printf("%03d\n",'a'); // 保留3位⾼位补零int x=10;printf("%03d\n",x); // ⼗进制输出printf("%05o\n",x);// ⼋进制输出printf("%05x\n",x); // ⼗六进制输出cout << "35的8进制:" << std::oct << 35<< endl;cout << "35的10进制" << std::dec << 35 << endl;cout << "35的16进制:" << std::hex << 35 << endl;cout << "35的2进制: " << bitset<8>(35) << endl; //<8>：表⽰保留8位输出return 0;}参考博客：1.2.Dijkstrabool book[N];int dis[N];void dijkstra(int x){for(int i=1; i<=n; i++)dis[i]=e[1][i],book[i]=0;book[x]=1;for(int i=2; i<=n; i++){int minn=inf,u;for(int j=1; j<=n; j++){if(!book[j]&&dis[j]<minn)u=j,minn=dis[j];}book[u]=1;for(int k=1; k<=n; k++){if(e[u][k]<inf&&dis[u]+e[u][k]<dis[k]) dis[k]=dis[u]+e[u][k];}}}FloydSPFAKMP查找⼦串（模式串）在原串中出现了⼏次。

c++ std扩展函数
C++标准库是一个强大的资源，提供了许多函数来处理各种任务。

除了标准的函数，C++标准库还提供了一些扩展函数，用于更高级或特殊的任务。

其中一些扩展函数包括：
1. std::next_permutation() - 在给定的范围中，找到下一个排列并返回true，如果没有下一个排列，则返回false。

2. std::prev_permutation() - 在给定的范围中，找到前一个排列并返回true，如果没有前一个排列，则返回false。

3. std::is_permutation() - 在两个范围内比较元素是否相同，但也考虑它们的排列是否相同。

4. std::partial_sum() - 将范围中的元素相加，同时在指定范围内存储部分和。

5. std::inner_product() - 在范围内对两个序列进行内积运算，将对应元素相乘并相加。

这些函数涉及多种数据结构和算法，可用于许多不同类型的应用程序。

了解这些扩展函数可以帮助您更好地利用C++标准库，并简化代码编写过程。

程序设计大赛暴力求解法一、知识点二、题目应用1．输入正整数n，按从小到大的顺序输出所有形如abcde/fghij=n的表达式，其中a~j 恰好为数字0~9的一个排列，2<=n<=79。

样例输入：62样例输出：79546 / 01283 = 6294736 / 01528 = 62【分析】枚举0~9的所有排列？没这个必要。

只需要枚举fghij就可以算出abcde，然后判断是否有所有数字都不相同即可。

不仅程序简单，而且枚举量也从10！=3628800降低至不到1万。

由此可见，即使采取暴力枚举，也是需要认真分析问题的。

#include <stdio.h>#include <stdlib.h>int test(int i,int j){int a[11];int k=0;while(i!=0) //此程序最重要的地方也就是比较这十个数字各不相同，要用数组存起来{a[k++]=i%10;i/=10;}while(j!=0){a[k++]=j%10;j/=10;}int flag;if(k==9) flag=0; //有十个数，所以这里是9int l;for(k=0;k<10;k++)for(l=k+1;l<10;l++)if(!flag) //如果flag为0说明分母为四位，则第一位为0if(a[k]==a[l]||a[k]==0) return 0;else if(flag)if(a[k]==a[l]) return 0;return 1;}int main(int argc, char *argv[]){int i,n,m;scanf("%d",&n);for(i=1234;i<98765;i++) //i<=49876{m=i*n;if(m>100000) break;else if(test(m,i)){printf("%d/%05d=%d\n",m,i,n);}}return 0;}2 最大乘积输入n个元素组成的序列S，你需要找出一个乘积最大的连续子序列。

习题解析第1章1. 解析：算法主要是指求解问题的方法。

计算机中的算法是求解问题的方法在计算机上的实现。

2. 解析：算法的五大特征是确定性、有穷性、输入、输出和可行性。

3. 解析：计算的算法，其中n是正整数。

可以取循环变量i的值从1开始，算i的平方，取平方值最接近且小于或者等于n的i即可。

4. 解析：可以使用反证法，设i=gcd(m, n)=gcd(n, m mod n)，则设m=a*i，n=b*i，且a与b互质，这时m mod n=（a-x*b）*i，只需要证明b和a-x*b互质，假设二者不互质，可以推出a与b 不互质，因此可以得到证明。

5. 解析：自然语言描述：十进制整数转换为二进制整数采用“除2取余，逆序排列”法。

具体做法是：用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为0时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。

流程图：如图*.1图*.1 十进制整数转换成二进制整数流程图6. 解析：a.如果线性表是数组，则可以进行随机查找。

由于有序，因此可以进行折半查找，这样可以在最少的比较次数下完成查找。

b.如果线性表是链表，虽然有序，则只能进行顺序查找，从链表头部开始进行比较，当发现当前节点的值大于待查找元素值，则查找失败。

7. 解析：本题主要是举例让大家了解算法的精确性。

过程中不能有含糊不清或者二义性的步骤。

大家根据可行的方式总结一下阅读一本书的过程即可。

8. 解析：数据结构中介绍的字典是一种抽象数据结构，由一组键值对组成，各个键值对的键各不相同，程序可以将新的键值对添加到字典中，或者基于键进行查找、更新或删除等操作。

由于本题已知元素唯一，因此大家可以据此建立一个自己的字典结构。

实现字典的方法有很多种：•最简单的就是使用链表或数组，但是这种方式只适用于元素个数不多的情况下；•要兼顾高效和简单性，可以使用哈希表；•如果追求更为稳定的性能特征，并且希望高效地实现排序操作的话，则可以使用更为复杂的平衡树。

2020-2021年度第⼆届全国⼤学⽣算法设计与编程挑战赛（冬季赛）题解热⾝赛题⽬描述：海的那边是敌⼈！为了夺回⾃由，艾尔迪亚帝国开始筹备起帝国巨⼈军队，利⽤艾伦始祖巨⼈之⼒，来指挥军队征战。

现在有12名巨⼈，他们的个⼦⾮常奇怪，第i i名巨⼈的⾝⾼为i i⽶。

现在，艾伦要将这12名巨⼈排成⼀排。

他想知道这12名巨⼈的排列⽅式有多少种。

例如：对于3名巨⼈的排列⽅式有6种：{1,2,3}、{1,3,2}、{2,3,1}、{2,1,3}、{3,1,2}、{3,2,1}请输出12名巨⼈的排列⽅式有多少种。

题意：输出12的全排列的个数思路1：使⽤全排列秘技：next_permutation#include<bits/stdc++.h>using namespace std;int main(){int sum = 1;int tr[] = {1,2,3,4,5,6,7,8,9,10,11,12};while (next_permutation(tr, tr + 12)) {sum++;}cout<<sum<<endl;}思路2:其实就是⾼中的排列组合⽽已，A（n,n）#include<bits/stdc++.h>using namespace std;int main(){int sum = 1;for(int i = 1; i <= 12; ++i)sum *= i;cout<<sum<<endl;}题⽬描述：在遥远的卡拉迪亚⼤陆，⼈们喜好骑马喜好砍杀。

⼤陆征战向来⾎⾬腥风，但为了社会主义的和谐发展，我们可以通过三⼦棋来决胜负！已知棋盘规模为 S*T ，具体参加三⼦棋的⼈数并不固定，现在你开了上帝之眼，你能看出来，究竟是谁赢下来这场「⾎腥」三⼦棋吗？胜利条件为：某⼀⾏或某⼀列或某⼀个斜⽅向（从左上到右下斜⽅向或从右上到左下斜⽅向）上有连续⾄少三个相同的棋⼦，则这枚棋⼦为获胜玩家的棋⼦。

字符串的全排列（字典序排列）题⽬描述输⼊⼀个字符串，打印出该字符串中字符的所有排列。

例如输⼊字符串abc，则输出由字符a、b、c 所能排列出来的所有字符串abc, acb, bac, bca, cab, cba。

题⽬分析穷举与递归⼜是⼀个经典问题，最容易想到的解决⽅法仍然是穷举（我实在是太爱穷举法了，每当被问到算法问题不知道如何解决的时候，总可以祭出穷举⼤旗，从⽽多争取3分钟的思考时间）。

穷举虽好，但它⼤多数情况下都不是被需要的那个答案，是因为看起来代码太Low不够⾼⼤上吗？在这种情况下，穷举法裹着貂⽪⼤⾐的亲戚——递归就出现了。

虽然空间复杂度和时间复杂度没有任何改进，⽽且还增加了系统开销（关于递归法的系统开销不在这⾥讨论，之后再找专门的时间阐述），但是就是因为长得好看（代码看起来精炼），递归的B格⼉就⾼了很多。

递归法对于这个题⽬同样⾮常适⽤，基本思路就是固定⼀个字符，然后对剩余的字符做全排列……不赘述，请⾃⼰想。

如果你也跟我⼀样永远想不明⽩递归，那就画画图，写写代码，debug⼀下，每天花3-4个⼩时，静下⼼来仔细捉摸，总（ye）会（bu）想（hui）明⽩的。

贴⼀段July和他伙伴们在《程序员编程艺术：⾯试和算法⼼得》中的代码实现，供做噩梦时使⽤。

p.s. 我已加了注释/** Permute full array of input string by general recusion* @ char* perm [in/out] The string need to do permutation* @ int from [in] The start position of the string* @ int to [in] The end position of the string*/void CalcAllPermutation(char* perm, int from, int to){if (to <= 1){return;}if (from == to){//all characters has been permutedfor (int i = 0; i <= to; i++)cout << perm[i];cout << endl;}else{// always select one character, then full array the left ones.for (int j = from; j <= to; j++){swap(perm[j], perm[from]); //swap the selected character to the beginning of stringCalcAllPermutation(perm, from + 1, to); // Permute left characters in full array.swap(perm[j], perm[from]); //recovery the string to original one (swap the selected character back to its position.)}}}字典序这是⼀个⽐递归更有趣的答案，不知道算不算经典解法，起码开拓了思路，跟每⼀次接触新鲜的算法⼀样，仍然想了半天的时间，因此照例把思考过程更细致的记录下来（虽然July和他伙伴们在《程序员编程艺术：⾯试和算法⼼得》中已经说了很多），再加上⼀些⼩修改。

排列组合算法排列：从n个不同元素中，任取m(m<=n)个元素按照⼀定的顺序排成⼀列，叫做从n个不同元素中取出m个元素的⼀个排列；从n个不同元素中取出m(m<=n)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，⽤符号A(n,m)表⽰。

A(n,m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)! 此外规定0!=1组合：从n个不同元素中，任取m(m<=n)个元素并成⼀组，叫做从n个不同元素中取出m个元素的⼀个组合；从n个不同元素中取出m(m<=n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。

⽤符号C(n,m) 表⽰。

C(n,m)=A(n,m)/m!=n!/((n-m)!*m!)；C(n,m)=C(n,n-m)。

C语⾔使⽤标志位实现#include <iostream>using namespace std;#define MaxN 10char used[MaxN];int p[MaxN];char s[MaxN];//从n个元素中选r个进⾏排列void permute(int pos,const int n,const int r){int i;/*如果已是第r个元素了，则可打印r个元素的排列 */if(pos == r){for(i=0; i<r; i++)cout<<s[p[i]];cout<<endl;return;}for (i=0; i<n; i++){if(!used[i]){/*如果第i个元素未⽤过*//*使⽤第i个元素，作上已⽤标记，⽬的是使以后该元素不可⽤*/used[i] = 1;/*保存当前搜索到的第i个元素*/p[pos] = i;/*递归搜索*/permute(pos+1,n,r);/*恢复递归前的值，⽬的是使以后改元素可⽤*/used[i] = 0;}}}//从n个元素中选r个进⾏组合void combine(int pos,int h,const int n,const int r){int i;/*如果已选了r个元素了，则打印它们*/if (pos == r){for(i=0; i<r; i++)cout<<s[p[i]];cout<<endl;return;}for(i=h; i<=n-r+pos; i++) /*对于所有未⽤的元素*/{if (!used[i]){/*把它放置在组合中*/p[pos] = i;/*使⽤该元素*/used[i] = 1;/*搜索第i+1个元素*/combine(pos+1,i+1,n,r);/*恢复递归前的值*/used[i] = 0;}}}//产⽣0~2^r-1的⼆进制序列void binary_sequence(int pos,const int r){for(i=0; i<r; i++)cout<<p[i];cout<<endl;return;}p[pos] = 0;binary_sequence(pos+1,r);p[pos] = 1;binary_sequence(pos+1,r);}//利⽤上⾯的⼆进制序列打印字符串的所有组合//如"abc"输出a、b、c、ab、ac、bc、abc。

24点游戏算法关于二十四点游戏的编程思路与基本算法漫长的假期对于我来说总是枯燥无味的，闲来无聊便和同学玩起童年时经常玩的二十四点牌游戏来。

此游戏说来简单，就是利用加减乘除以及括号将给出的四张牌组成一个值为24的表达式。

但是其中却不乏一些有趣的题目，这不，我们刚玩了一会儿，便遇到了一个难题——3、6、6、10（其实后来想想，这也不算是个太难的题，只是当时我们的脑筋都没有转弯而已，呵呵）。

问题既然出现了，我们当然要解决。

冥思苦想之际，我的脑中掠过一丝念头——何不编个程序来解决这个问题呢？文曲星中不就有这样的程序吗？所以这个想法应该是可行。

想到这里我立刻开始思索这个程序的算法，最先想到的自然是穷举法（后来发现我再也想不到更好的方法了，悲哀呀，呵呵），因为在这学期我曾经写过一个小程序——计算有括号的简单表达式。

只要我能编程实现四个数加上运算符号所构成的表达式的穷举，不就可以利用这个计算程序来完成这个计算二十四点的程序吗？确定了这个思路之后，我开始想这个问题的细节。

首先穷举的可行性问题。

我把表达式如下分成三类—— 1、无括号的简单表达式。

2、有一个括号的简单表达式。

3、有两个括号的较复4、杂表达式。

穷举的开始我对给出的四个数进行排列，其可能的种数为4*3*2*1=24。

我利用一个嵌套函数实现四个数的排列，算法如下: /* ans[] 用来存放各种排列组合的数组 */ /* c[] 存放四张牌的数组 */ /* k[] c[]种四张牌的代号，其中k[I]=I+1。

用它来代替c[]做处理，考虑到c[]中有可能出现相同数的情况 */ /* kans[] 暂存生成的排列组合 */ /* j 嵌套循环的次数 */ int fans(c,k,ans,kans,j) int j,k[],c[];char ans[],kans[]; { int i,p,q,r,h,flag,s[4],t[4][4]; for(p=0,q=0;p<4;p++) { for(r=0,flag=0;rif(k[p]!=kans[r]) flag++; if(flag==j) t[j][q++]=k[p]; } for(s[j]=0;s[j]<4-j;s[j]++) { kans[j]=t[j][s[j]]; if(j==3) { for(h=0;h<4;h++) ans[2*h]=c[kans[h]-1]; /* 调整生成的排列组合在最终的表达式中的位置 */ for(h=0;h<3;h++) symbol(ans,h); /* 在表达式中添加运算符号 */ } else { j++; fans(c,k,ans,kans,j); j--; } } } 正如上面函数中提到的，在完成四张牌的排列之后，在表达式中添加运算符号。

排列组合算法最近一直在考虑从m个数里面取n个数的算法。

最容易理解的就是递归，但是其效率，实在不能使用。

一直找寻中，今日得果2。

算法来源与互联网组合算法本程序的思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标代表的数被选中，为0则没选中。

首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。

然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。

当第一个“1”移动到数组的m-n的位置，即n个“1”全部移动到最右端时，就得到了最后一个组合。

例如求5中选3的组合：1 1 1 0 0 //1,2,31 1 0 1 0 //1,2,41 0 1 1 0 //1,3,40 1 1 1 0 //2,3,41 1 0 0 1 //1,2,51 0 1 0 1 //1,3,50 1 1 0 1 //2,3,51 0 0 1 1 //1,4,50 1 0 1 1 //2,4,50 0 1 1 1 //3,4,5全排列算法从1到N，输出全排列，共N！条。

分析：用N进制的方法吧。

设一个N个单元的数组，对第一个单元做加一操作，满N进一。

每加一次一就判断一下各位数组单元有无重复，有则再转回去做加一操作，没有则说明得到了一个排列方案。

//////////////////////////////////////////////////////递归算法全排列是将一组数按一定顺序进行排列，如果这组数有n个，那么全排列数为n!个。

现以{1, 2, 3, 4, 5}为例说明如何编写全排列的递归算法。

1、首先看最后两个数4, 5。

它们的全排列为4 5和5 4, 即以4开头的5的全排列和以5开头的4的全排列。

由于一个数的全排列就是其本身，从而得到以上结果。

2、再看后三个数3, 4, 5。

它们的全排列为3 4 5、3 5 4、4 3 5、4 53、5 34、5 4 3 六组数。

实验三、应用 Apriori 算法挖掘频繁项集学院计算机科学与软件学院•实验目的：（1）熟悉 VC++编程工具和 Apriori 频繁项集挖掘算法。

（2）根据管理层的需求，确定数据挖掘的任务，明确数据挖掘的功能，也就是明确要挖掘什么。

（3）由确定的数据挖掘任务，从实验一处理后的结果中，采用切块或切片等联机分析处理技术，选择出挖掘任务相关数据。

（4）用 VC++编程工具编写 Apriori 算法的程序，对任务相关数据运行 Apriori算法，挖掘出所有的频繁项集。

1.写出实验报告。

•实验原理：1 、Apriori 算法Apriori 使用一种称作逐层搜索的迭代方法，k 项集用于探索（k+1）项集。

首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁 1 项集的集合。

该集合记作 L 1 。

然后，L 1 用于找频繁 2 项集的集合L 2 ，L 2 用于找 L 3 ，如此下去，直到不能再找到频繁 k 项集。

找每个 L k 需要一次数据库全扫描。

2、提高频繁项集逐层产生的效率Apriori 性质：频繁项集的所有非空子集也必须是频繁的。

三、实验内容：1、实验内容在给定的数据中提取统一购物篮购买的商品信息，由这些数据构成事务数据库 D，挖掘其中的频繁项集 L。

挖掘频繁项集的算法描述如下：Apriori 算法：使用逐层迭代找出频繁项集输入：事务数据库 D；最小支持度阈值。

输出：D 中的频繁项集 L。

（1） L 1 = find_frequent_1-itemsets(D); // 挖掘频繁 1-项集，比较容易（2） for (k=2;L k-1 ≠Φ ;k++) {（3） C k = apriori_gen(L k-1 ,min_sup); // 调用 apriori_gen 方法生成候选频繁k-项集分为两步：合并、减枝（4） for each transaction t ∈ D { // 扫描事务数据库 D（5） Ct = subset(C k ,t);（6） for each candidate c ∈ Ct（7） c.count++; // 统计候选频繁 k-项集的计数（8） }（9） L k ={c ∈ Ck|c.count≥min_sup} // 满足最小支持度的 k-项集即为频繁 k-项集（10） }（11） return L= ∪ k L k ; // 合并频繁 k-项集（k>0）算法在根据频繁 k-1 项集生成频繁 K 项集过程中要计算频繁 K 项集中每个元素的支持度，并计算 K 项集中每个 k-1 项子集是否在 F k-1 中，上述两条任何一条不满足，则删去这个 K 项集中的元素。

H国的⾝份证号码（搜索）个⼈⼼得：巧妙利⽤数字进⾏维护就好了，深搜还是有点⼼得的；#1558 : H国的⾝份证号码I时间限制:10000ms单点时限:1000ms内存限制:256MB描述H国的⾝份证号码是⼀个N位的正整数(⾸位不能是0)。

此外，由于防伪需要，⼀个N位正整数是合法的⾝份证号码当且仅当每位数字都⼩于等于K，并且任意相邻两位数字的乘积也⼩于等于K。

例如对于K=5, 101、211、210等都是合法的号码，⽽106、123、421等都是⾮法的号码。

给定⼀个正整数N以及K，请从⼩到⼤输出所有合法的号码。

输⼊两个整数N和K。

对于80%的数据，1 ≤ N ≤ 6。

对于100%的数据，1 ≤ N ≤ 9，1 ≤ K ≤ 5。

输出按从⼩到⼤的顺序输出所有合法的N位号码，每个号码占⼀⾏。

样例输⼊2 4样例输出1011121314202122303140411 #include<iostream>2 #include<cstdio>3 #include<cstring>4 #include<string>5 #include<queue>6 #include<algorithm>7using namespace std;8int pow(int i,int j)9 {10if(j==0) return1;11int s=1;12for(int k=1;k<=j;k++)13 s*=i;14return s;15 }16int n,m;17int number[10];18int s[1000000];19int flag=1;20void dfs(int i,int j,int q)21 {22if(j==n)23 {24 s[flag++]=q;25return ;26 }27for(int k=0;k<=m;k++)28 {29if(k*i<=m)30 dfs(k,j+1,q+k*pow(10,n-j-1));31 }3233 }34int main()35 {36 cin>>n>>m;37for(int i=1;i<=m;i++)38 dfs(i,1,i*pow(10,n-1));39 sort(s+1,s+flag+1);40for(int i=1;i<=flag;i++)41if(s[i])42 cout<<s[i]<<endl;43return0;4445 }。