排列与组合的应用.doc

《排列与组合的应用.doc》由会员分享，可在线阅读，更多相关《排列与组合的应用.doc（23页珍藏版）》请在三一文库上搜索。

1、排列与组合的应用四川成都市大弯中学李植武摘要在信息学奥林匹克竞赛中，多次出现了排列与组合的竞赛题目。本文介绍了排列与组合的概念、公式，重点讲解了排列与组合的生成算法，最后通过几个竞赛题目的解决，体现了排列与组合在信息学竞赛中的应用。关键词排列组合生成应用说明：本文中的pascal程序在Lazarus v0.9.22 beta下调试完成，c程序dev-c+ 4.9.9.2下调试完成，所有程序通过相应数据测试。一、排列与组合 1排列及公式 (1)线排列一般地，从n个不同元素中，取出m(mn)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个线排列；从n个不同元素中取出m(mn)个

2、元素的所有线排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 表示。 规定 0！1。(2)圆排列从n个不同元素中取出m个元素按照某种次序（如逆时针）排成一个圆圈，称这样的排列为圆排列，圆排列个数为 。因为从n个不同元素中取出m个元素排成一列的个数是。不妨设一个排列是：a1a2am。而这个排列与排列a2ama1, a3ama1a2, ama1a2am-1，是一样的圆排列，共有m个，所以一个圆排列对应m个普通排列，所以有圆排列数。(3)无限重排列从n个不同元素中取r个元素按次序排列，每个元素可以取无限次，这样的排列称为无限重排列。显然，其排列数为nr。(4)有限重排列从k个不同元素 a

3、1a2ak 中取n个元素按次序排列，元素ai可以取ri次,r1+r2+.+rk =r，这样的排列称为有限重排列。实际上,这个问题与下面的问题等价：把r(r1+r2+.+rk =r)只彩色球放到n个编号不同的盒子中去的方法数。如r=n,则排列数有 。(5)错排问题一个排列使得所有的元素都不在原来的位置上，则称这个排列为错排。例如有3个元素，原来位置为：1 2 3，它的错排有两种3 1 2和2 3 1。用fn表示n个元素的错排数，利用容斥原理可以推出（过程略）：fn=。主要讲一下递推式。考虑任意一个满足条件的排列a1,a2,a3,an,显然有ann,不妨设n=ai,考虑书i的位置，它有两种情况：1

4、)i=an2)ian 对于1)，数i在位置n,而数n在位置i上，则是n-2的错排问题，这种情况的方法数为fn-2。对于)，可以把位置n看成位置i（位置i上不放数i,而此时位置n也不放数i，所以i和n可以等同看待）,则问题成了n-1个数的错排问题了。由1)与2)及i有n-1种取值，所以有fn=(n-1)(fn-2+fn-1)。：2组合及公式 (1)非重组合一般地，从n个不同元素中，取出m(mn)个元素，不允许元素重复，不考虑元素次序，叫做从n个不同元素中取出m个元素的一个非重组合；从n个不同元素中取出m(mn)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号表示. 组合数

5、的两个性质：（2）重组合从n个不同元素中,取出r个允许重复的元素而不考虑其次序时，称为从n个不同元素中取r个允许重复的组合，简称重组合。其组合数为. 这个问题，可以看作用r个相同的标记去标明这n个不同的对象，而每一个对象可以被标上多个标记，一个对象上最多r个标记。设n个元素为 a1a2an ，记ai被记了k次为ai(k),同一个元素标记不同次数，认为是不同的元素，那么第1次标记有n种方法，有n+1个元素 a1a2an ai(k),第2次标记就有n+1种方法，有n+2个元素，第r次标记有n+r-1种方法，有n-r个元素，而标记顺序对结果没有影响，所以有种方法，即。二、排列与组合生成算法 1.排列

6、生成 有N本不同的书摆在书架上，设其编号分别为，.，编程求解这本书的不同摆放方案和摆放方案总数。程序名：pailie.pas/c/cpp输入文件：pailie.in输出文件：pailie.out输入文件的格式为：仅为一个数N输出文件的格式为：依次为每一行为一种方案,每个数之间用一个空格隔开，最后一行为方案数23样例input2output1 22 12数据规模1=N1)and(ai-1ai) do dec(i); fi:=i; end; function fk:longint; var k:longint; begin k:=n; while (k1)and(ak1 do begin k:=f

7、k; t:=ai-1; ai-1:=ak; ak:=t; for j:=i to (n+i)div 2 do begin t:=an+i-j; an+i-j:=aj; aj:=t; end; print; i:=fi; end; writeln(s); close(input); close(output);end.（）回溯算法产生排列用pi记录一个排列的第i个数， 伪代码描述的产生排列的第i个数的方法Procedure try(i) Begin If in then begin 输出排列；返回end;/产生了一个完整排列，输出 For j=1 to n do If not aj then /

8、 j这个数没有用 Begin Pi=j; Aj=true;/占位 Try(i+1);/搜索下一个数 End; End;Pascal版参考程序：program pailie;var p:array1.10 of longint; a:array1.10 of boolean; n,tot,i:longint; fil:text;procedure print; var i:longint; begin inc(tot); for i:=1 to n do write(fil,pi, ); writeln(fil); end;procedure tryy(i:longint); var j:lon

9、gint; begin if in then begin print;exit end; for j:=1 to n do if not aj then begin aj:=true; pi:=j; tryy(i+1); aj:=false; end; end;begin assign(fil,pailie.in); reset(fil); readln(fil,n); close(fil); assign(fil,pailie.out); rewrite(fil); fillchar(a,sizeof(a),false); tot:=0; tryy(1); writeln(fil,tot);

10、 close(fil);end.C语言版参考程序：# include long a15,n,s;bool f15;FILE *fp;void shu(long a) long i; for (i=1;i=n;i+) fprintf(fp,%d ,ai); fprintf(fp,n); s+; void pai(long i) long j,k; if (i=n+1) shu(a); return; for (j=1;j=n;j+) if (fj) fj=false; ai=j; pai(i+1); fj=true; int main() long i,j,k,m; fp=fopen(paili

11、e.in,r); fscanf(fp,%d,&n); fp=fopen(pailie.out,w); for (i=1;i=n;i+) fi=true; s=0; pai(1); fprintf(fp,%dn,s); fclose(fp); return 0;2.组合生成有N本不同的书摆在书架上，设其编号分别为，.，现要从其中取出本书，编程求解这本书的不同组合方案和方案总数。程序名：zuhe.pas/c/cpp输入文件：zuhe.in输出文件：zuhe.out输入文件的格式为：仅为一行，两个数N和，之间用一个空格隔开输出文件的格式为：依次为每一行为一种组合,每个数之间用一个空格隔开，最后一行为

12、组合方案数样例input3 2output1 21 32 33数据规模1=N，R0) and (ci=n-(r-i) do dec(i); findi:=i; end;begin assign(fil,zuhe.in);reset(fil); readln(fil,n,r); close(fil); for i:=1 to r do ci:=i; assign(fil,zuhe.out);rewrite(fil); tot:=0; repeat print; i:=findi; if i0 then begin inc(ci); for j:=i+1 to r do cj:=cj-1+1; e

13、nd; until i=0; writeln(fil,tot); close(fil);end.（）回溯算法产生组合用i记录一个组合的第i个数， 伪代码描述产生组合第i个数的方法Procedure try(i,last) /last 表示第i-1个数的取值 Begin If ir then begin 输出组合；返回end;/产生了一个完整组合，输出 For j=last+1 to n do Begin ci=j; Try(i+1,j);/搜索下一个数 End; End;Pascal版参考程序：program zuhe;var c:array1.30 of longint; n,r,i,j,t

14、ot:longint; fil:text;procedure print; var i:longint; begin inc(tot); for i:=1 to r do write(fil,ci, ); writeln(fil); end;procedure tryy(i,last:longint); var j:longint; begin if ir then begin print;exit; end; for j:=last+1 to n do begin ci:=j; tryy(i+1,j); end; end;begin assign(fil,zuhe.in);reset(fil

15、); readln(fil,n,r); close(fil); assign(fil,zuhe.out);rewrite(fil); tot:=0; tryy(1,0); writeln(fil,tot); close(fil);end.C语言版参考程序：# include long a35,n,s,r;FILE *fp;void shu(long a) long i; for (i=1;i=r;i+) fprintf(fp,%d ,ai); fprintf(fp,n); s+; void pai(long i,long k) long j; if (i=r+1) shu(a); return

16、 ; for (j=k;j=n;j+) ai=j; pai(i+1,j+1); int main() long i,j,k,m; fp=fopen(zuhe.in,r); fscanf(fp,%d %d,&n,&r); fp=fopen(zuhe.out,w); s=0; pai(1,1); fprintf(fp,%dn,s); fclose(fp); return 0;三、排列与组合应用1.火星人（noip2004普及组）【问题描述】人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人

17、把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。火星人用一种非常简单的方式来表示数字掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为1，2，3。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指拇指、食指、中指、无名指和小指分别编号为1，2，3，4和5，当它们按正常顺序排列时，形成了5位数12345，当你交换无名指和小指的位置时，会形成5位数12354，当你把五个手指的顺序完全颠倒时，会形成54321，在

18、所有能够形成的120个5位数中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指时能够形成的6个3位数和它们代表的数字：三进制数123132213231312321代表的数字123456现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。【输入文件】输入文件martian.in包括三行，第一行有一个正整数N，表示火星人手指的数目（1

19、= N = 10000）。第二行是一个正整数M，表示要加上去的小整数（1 = M = 100）。下一行是1到N这N个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。【输出文件】输出文件martian.out只有一行，这一行含有N个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。【样例输入】531 2 3 4 5【样例输出】1 2 4 5 3【数据规模】对于30%的数据，N=15；对于60%的数据，N=50；对于全部的数据，Nfingerj) and (j1) do j:=j-1; findi:=j; end; function findj(i:

20、integer):integer; var j:integer; begin j:=n; while (fingerjfingeri-1) do j:=j-1; findj:=j; end; procedure change(k,l:integer); var i,j:integer; begin j:=fingerk-1;fingerk-1:=fingerl;fingerl:=j; for i:=k to (n+k) div 2 do begin j:=fingeri;fingeri:=fingern+k-i;fingern+k-i:=j; end; end; procedure print

21、; var i:integer; begin assign(ff,martian.out); rewrite(ff); for i:=1 to n-1 do write(ff,fingeri, ); write(ff,fingern); close(ff); end;begin init; for i:=1 to m do change(findi,findj(findi); print;end.C语言版参考程序：# include long f10050;int main() long m,n,j,i,k,a,b,t; FILE *fp; fp=fopen(martian.in,r); fs

22、canf(fp,%dn%dn,&n,&m); for (i=1;i=n;i+) fscanf(fp,%d,&fi); for (i=1;i1)&(fj1)&(fkfj-1) k-; t=fk; fk=fj-1; fj-1=t; a=j; b=n; while (ab) t=fa; fa=fb; fb=t; a+; b-; fp=fopen(martian.out,w); for (i=1;i=n;i+) fprintf(fp,%d ,fi); fclose(fp); return 0;（）回溯算法产生下一个排列用回溯算法的难点在于，怎么从给定的排列开始产生下一个。且数组a记录已知的排列，第一次

23、产生排列的第i个数时，初值设为ai，而以后，都从开始去判断。所以回溯后均将ai设为。具体实现见程序。Pascal版参考程序：program martian; var a,b:array1.1005 of longint; flag:array1.1005 of boolean; n,m,tot:longint; procedure init; var i:longint; begin assign(input,martian.in);reset(input); assign(output,martian.out);rewrite(output); readln(n); readln(m); f

24、or i:=1 to n do read(ai); tot:=0; fillchar(flag,sizeof(flag),true); end; procedure print; var i:longint; begin for i:=1 to n-1 do write(bi, ); writeln(bn); end; procedure tryy(i:longint); var j:longint; begin if i=n+1 then begin inc(tot); if tot=m+1 then begin print; close(input);close(output); halt

25、 end; end; for j:=ai to n do if flagj then begin flagj:=false; bi:=j; tryy(i+1); flagj:=true; ai:=1;/将下一次第i个数初值设为 end; end;begin init; tryy(1);end.C语言版参考程序：# include # include # include long a10005,n,s,m;bool f10005;FILE *fp;void p(long a) long i; for (i=1;in;i+) fprintf(fp,%d ,ai); fprintf(fp,%dn,a

26、n);void tryy(long i) long j; if (i=n+1) s+; if (s=m+1) p(a); exit(0); for (j=ai;j=n;j+) if (fj) ai=j; fj=false; tryy(i+1); fj=true; ai=1;/将下一次第i 个数初值设为 int main() long i; fp=fopen(martian.in,r); fscanf(fp,%dn%d,&n,&m); for (i=1;i=n;i+) fscanf(fp,%d,&ai); memset(f,true,sizeof(f); fp=fopen(martian.out

27、,w); s=0; tryy(1); fclose(fp); return 0;2、Jam的计数法(noip2006普及组) 【问题描述】Jam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为Jam数字。在Jam数字中，每个字母互不相同，而且从左到右是严格递增的。每次，Jam还指定使用字母的范围，例如，从2到10，表示只能使用b,c,d,e,f,g,h,i,j这些字母。如果再规定位数为

28、5，那么，紧接在Jam数字“bdfij”之后的数字应该是“bdghi”。（如果我们用U、V依次表示Jam数字“bdfij”与“bdghi”，则UV，且不存在Jam数字P，使UPV）。你的任务是：对于从文件读入的一个Jam数字，按顺序输出紧接在后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。【输入文件】输入文件counting.in 有2行，第1行为3个正整数，用一个空格隔开：s t w（其中s为所使用的最小的字母的序号，t为所使用的最大的字母的序号。w为数字的位数，这3个数满足：1st26, 2wt-s ） 第2行为具有w个小写字母的字符串，为一个符合要求的Jam数字

29、。所给的数据都是正确的，不必验证。【输出文件】输出文件counting.out 最多为5行，为紧接在输入的Jam数字后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。每行只输出一个Jam数字，是由w个小写字母组成的字符串，不要有多余的空格。【输入样例】 2 10 5 bdfij【输出样例】bdghibdghjbdgijbdhijbefgh分析：本题实际上是给定第s个到第t个连续的t-s+1个字母的组合问题，求出给定组合后的紧接着个组合。同样也可以用两种方法来解决。（）由上一个组合产生下一个组合的方法（见组合生成算法）。Pascal版参考程序：program count;

30、/myself var s,t,w,i,j,k:longint; st:string;begin readln(s,t,w); readln(st); i:=0; while i=1) and (stj=chr(96+t-(w-j) do dec(j); if j0 then begin stj:=succ(stj); for k:=j+1 to w do stk:=succ(stk-1); writeln(st); inc(i); end else i:=5; end; readln;end.C语言版参考程序：# include char a30;int main() long i,j,t,

31、n,k,w,x,s; FILE *fp; fp=fopen(count.in,r); fscanf(fp,%d %d %d %s,&s,&t,&w,a); fp=fopen(count.out,w); for (i=1;i=0)&(aj=t+j-w+97) j-; if (j=0) aj=aj+1; for (k=j+1;k=w-1;k+) ak=ak-1+1; fprintf(fp,%sn,a); else break; fclose(fp);（）回溯算法产生下一个组合用回溯算法的难点在于，怎么从给定的组合开始产生下一个。且数组a记录已知的组合，第一次产生组合的第i个数时，初值设为ai，而以

32、后，都从正常的下一个数去产生。所以回溯后均将ai设为。具体实现见程序。Pascal版参考程序：program count; var a:array1.26 of longint; s,t,w,tot:longint; x:char; procedure init; var i:longint; begin assign(input,count.in);reset(input); assign(output,count.out);rewrite(output); readln(s,t,w); for i:=1 to w do begin read(x); ai:=ord(x)-96; end; close(input); tot:=0; end; procedure print; var i:longint; begin for i:=1 to w do write(char(ai+96); writeln; end; procedure tryy(i,k:longint); var j:longint; begin if i=w+1 then begin i