组合数学在程序设计竞赛中的应用ppt课件.ppt-淘文阁

资源描述

《组合数学在程序设计竞赛中的应用ppt课件.ppt》由会员分享，可在线阅读，更多相关《组合数学在程序设计竞赛中的应用ppt课件.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、组合数学在程序设计竞赛中的应用组合数学在程序设计竞赛中的应用（一）（一）软件学院软件学院2003级穆浩英级穆浩英我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物内容提要内容提要l排列组合和容斥原理排列组合和容斥原理l群论与群论与Polya定理定理 l递推关系递推关系我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物两个基本原则两个基本原则1、加法原则、加法原则如果完成一件事情有两种方案，而第一个方案有如果完成一件事情有两种

2、方案，而第一个方案有m种种方法，第二个方案有方法，第二个方案有n中方法，则完成该事情共有中方法，则完成该事情共有m+n种种方法。方法。2、乘法原则、乘法原则如果完成一件事情需要两个步骤，第一步有如果完成一件事情需要两个步骤，第一步有m中方法，中方法，第二步又有第二步又有n种方法，则完成该事情共有种方法，则完成该事情共有m*n种方法种方法我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物排列组合的几个基本结论排列组合的几个基本结论1、相异元素不允许重复的排列数和组合数、相异元素不允许重复的排列数和组合数： n!

3、(n-r)!P(n,r)=C(n,r)= n!(n-r)!r! 2、不尽相异元素的全排列、不尽相异元素的全排列RP(n,n) = n!n1!n2!.nt!我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物排列组合的几个基本结论排列组合的几个基本结论3、相异元素不允许重复的圆排列、相异元素不允许重复的圆排列CP(n,n)=P(n,n) n4、相异元素允许重复的组合数、相异元素允许重复的组合数集合描述：设集合描述：设S=e1, e2, en,，从，从S中允许重中允许重复地取出复地取出r个元素，称为个元素，称为r

4、可重组合可重组合RC(,r)=C(n+r-1,r) = (n+r-1)! r!(n-1)! 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物排列组合例题排列组合例题例例1：电子锁：电子锁某机要部门安装了电子锁。某机要部门安装了电子锁。M工作人员每工作人员每人发一张磁卡，卡上有开锁的密码特征，为了人发一张磁卡，卡上有开锁的密码特征，为了确保安全，规定至少有确保安全，规定至少有N人同时使用各自的磁人同时使用各自的磁卡才能将锁打开。卡才能将锁打开。现在需要计算一下，电子锁上至少要有多现在需要计算一下，电子锁上至少

5、要有多少种特征，每个人的磁卡上至少要有多少特征。少种特征，每个人的磁卡上至少要有多少特征。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物排列组合例题排列组合例题先做一个简单的假设：先做一个简单的假设：M=7，N=4。对于问题一：任意对于问题一：任意3人在一起，至少缺一种特人在一起，至少缺一种特征，不能打开。征，不能打开。电子锁的至少应有电子锁的至少应有C(7,3)=35种特征。种特征。对于问题二：对任一位工作者的磁卡而言，其对于问题二：对任一位工作者的磁卡而言，其余余6人中任意人中任意3人在场至少缺

6、少一种人在场至少缺少一种A所具有的特征所具有的特征而无法打开大门。而无法打开大门。每张磁卡至少应有每张磁卡至少应有C(6,3)=20种特征种特征所以总终答案是所以总终答案是C(M,N-1)和和C(M-1,N-1)我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物排列组合例题排列组合例题例2：zju1976 Path On a Grid 求求n*m的方格图形中，从点（的方格图形中，从点（0，0）到点（）到点（n，m）的最短路径数目）的最短路径数目（0，0）（n，m）Sample Input （给定（给定n，

7、m）5 41 10 0Sample Output (路径数目)1262我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物排列组合例题排列组合例题我们用组合数学的思路来解题。最短路径必定是一条只向右我们用组合数学的思路来解题。最短路径必定是一条只向右上走得路。设向右走一步为上走得路。设向右走一步为x，向上走一步为，向上走一步为y。则每一条路。则每一条路线一定对应由线一定对应由n个个x，m个个y共共m+n个元素组成的排列。个元素组成的排列。以以n=5，m=4为例，为例，任意一条路线如下图所示，对应的任意一条路线

8、如下图所示，对应的xy序列序列为：为：xyxxxyxyy可见，只要能确定可见，只要能确定9个位置中个位置中4个个y的位置的位置就唯一确定了一条路径。就唯一确定了一条路径。所以，本题答案就是所以，本题答案就是C(n+m,m)我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物排列组合数的一般计算方法排列组合数的一般计算方法 20!12!8!C(20，12) =怎么计算？设计一个求阶乘的函数？怎么计算？设计一个求阶乘的函数？20！= 243290200817664000012！= 4790016008！ = 403

9、20C(20,12) = 125970显然显然2020！用！用intint表示一定是失败的，而表示一定是失败的，而C(20,12)C(20,12)的结果又完全的结果又完全可以用可以用intint来表示。来表示。回想我们是怎么计算的回想我们是怎么计算的? ? 先约分再计算！先约分再计算！我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物排列组合数的一般计算方法排列组合数的一般计算方法（一）计算组合数的函数（一）计算组合数的函数int gcd(int a, int b)if(b=0)return a;else r

10、eturn gcd(b,a%b);/欧几里德辗转相除法求最大公欧几里德辗转相除法求最大公约数约数int C(int n ,int m)int i,a,fz=1,fm=1;for( i = 1; i =1; i-) product = product / i * (n+i); return product; /* 在输出结果是应该注意要以在输出结果是应该注意要以整数形式输出整数形式输出.*/#include #include using namespace std; int mainint n,m;cinnm;coutsetiosflags(ios:fixed)setprecision(0)C2

11、(n,m)endl;return 0;我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物排列的生成算法排列的生成算法l字典序法字典序法:顾名思义顾名思义, ,这种方法就是将所有这种方法就是将所有n n元排列按元排列按“字典字典顺序顺序”排成队，以排成队，以12n12n为第一个排列，排序规则，为第一个排列，排序规则，即：由一个排列即：由一个排列P(pP(p1 1,p,p2 2ppn n) )直接生成下一个排列的直接生成下一个排列的算法可归结为：算法可归结为：（1 1）求满足）求满足p pk-1k-1ppk k的

12、的k k的最大值，设为的最大值，设为i, i,即即 i=maxk|pi=maxk|pk-1k-1ppk k （2 2）求满足）求满足p pi-1i-1ppk k的的k k的最大值，设为的最大值，设为j, j,即即 j=maxk|pj=maxk|pi-1i-1p=6)n(n=6)个数字，要求按字典序输出所有从个数字，要求按字典序输出所有从该该n n个数字中取个数字中取6 6个的组合个的组合。Sample Input7 1 2 3 4 5 6 7 7 1 2 3 4 5 6 7 8 1 2 3 5 8 13 21 34 0 8 1 2 3 5 8 13 21 34 0 Sample Output1

13、 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 71 2 3 4 5 71 2 3 4 6 71 2 3 4 6 71 2 3 5 6 71 2 3 5 6 71 2 4 5 6 71 2 4 5 6 71 3 4 5 6 71 3 4 5 6 72 3 4 5 6 72 3 4 5 6 71 2 3 5 8 13 1 2 3 5 8 13 1 2 3 5 8 21 1 2 3 5 8 21 1 2 3 5 8 34 1 2 3 5 8 34 1 2 3 5 13 211 2 3 5 13 21 n我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？

14、但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物组合的生成算法组合的生成算法Code:#include#include#includeusing namespace std;int k;int used13;int lotto13;void output();void choosenext(int I , int num);int main()int n_case = 0, i;while(cink&k) if(n_case+) coutendl; for (i = 0 ;i lottoi;sort(lotto,lotto+k);memset(used,0,sizeof(used);

15、choosenext(0,0);return 0;我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物组合的生成算法组合的生成算法void output()int i,n=0;for(i = 0 ;i k ; i +) if(usedi) if(n) cout ;coutlottoi;n+; coutendl;void choosenext(int I , int num)if(num = 6) output(); return ;if(I = k) return ;for(int i = I ;i k ;i

16、+) usedi = 1; choosenext(i+1,num+1); usedi = 0; 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物容斥原理容斥原理1、容斥原理、容斥原理： |A1+A2+An| =|Ai|- |AiAj| + |AiAjAk|- +(-1)n-1|A1A2An|ni=11 ij n1 ijk n2、逐步淘汰原理、逐步淘汰原理 |A1.A2An|=|S|-|Ai|+|AiAj|- |AiAjAk|+(-1)n|A1A2An|i=1n1 ij n1 ijk n另外容斥原理还有：另

17、外容斥原理还有：Jordan公式和对称原理、对称筛。公式和对称原理、对称筛。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物容斥原理应用容斥原理应用1、错排问题。、错排问题。问题描述问题描述：n n个元素一次给以标号个元素一次给以标号1 1，2 2，n n进进行全排列，求每个元素不再自己原来位置上的排行全排列，求每个元素不再自己原来位置上的排列数列数D Dn n。解解令令AiAi表示数表示数I I排在第排在第I I个位置上的所有排列，则个位置上的所有排列，则|Ai| = (n-1)!, I = 1,2,n

19、逐步淘汰原理得：根据逐步淘汰原理得：Dn = n! C(n,1)(n-1)! +C(n,2)(n-2)!-(-1)nC(n,n)0! = n!(1-1/1!+1/2!-+(-1)n1/n!)我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物容斥原理应用容斥原理应用例：例：zju1619zju1619PresentPresent n n个朋友每人买了一份礼物，混合在一起后，每个朋友每人买了一份礼物，混合在一起后，每人拿一份，求恰有人拿一份，求恰有mm人拿到了恰好是自己买的礼人拿到了恰好是自己买的礼物的概率。物的

20、概率。即即:n:n个数的全排列中，个数的全排列中，mm个保位个保位,(n-m),(n-m)个错位的排个错位的排列数占总排列数的比例。列数占总排列数的比例。全排列数：全排列数：n!n!mm个保位个保位,(n-m),(n-m)错位的排列数：错位的排列数：C(n,m)DC(n,m)Dn-mn-m结论：结论：p = C(n,m)Dp = C(n,m)Dn-mn-m/n!/n!我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物容斥原理应用容斥原理应用#include#includeusing namespace std

21、;double jc100; void JC()jc0 = 1.0;int i;for(i = 1; i nm) double res = 0; int i; for(i = 0 ;i = n-m; i+) if(i%2=0) res+=jci;else res-=jci; res*=jcm; coutsetiosflags(ios:fixed)setprecision(8 )resendl; return 0;我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物群论群论群：群：给定非空集合给定非空集合G G

22、及定义在及定义在G G上的二元运算上的二元运算“. .”，若满足以下四个条件，则称集合若满足以下四个条件，则称集合G G在运算在运算“.”.”下构成一下构成一个群，简称个群，简称G G群：群：(1)、封闭性：、封闭性：a,b G,则则a.b G;(2)、结合律：、结合律：(a.b).c=a.(b.c)(3)、单位元：存在、单位元：存在e G,对任意对任意aG,有有a.e=e.a=a; ;(4)、逆元素：对任意、逆元素：对任意a G,存在存在b G,使得使得a.b=b.a=e,称称b为为a的的逆元素，记为逆元素，记为a-1;我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世

23、界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物群论群论置换：置换：n个元素个元素1,2,n之间的一个置换：之间的一个置换：1 2 na1 a2 an 表示被表示被1到到n中的某个数中的某个数 a1取代，取代，2被被1到到n中的某个数中的某个数a取取代代，直到，直到n被被1中的某个数中的某个数an取代，且取代，且a1,a2an互不相同互不相同。置换群置换群: :置换群的元素是置换，运算是置换的连接。置换群的元素是置换，运算是置换的连接。例如：例如：1 2 3 4 1 2 3 4 3 1 2 4 4 3 2 1=1 2 3 42 4 3 1我吓了一跳，蝎子是多么丑恶和恐怖的

24、东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物群论群论循环记：(a1a2an)=a1 a2 an-1 ana2 a3 an a1称为：称为：n n阶循环。每个置换都可以写成若干个互不相交的阶循环。每个置换都可以写成若干个互不相交的循环的乘积，两个循环循环的乘积，两个循环(a(a1 1a a2 2aan n) )和和(b(b1 1b b2 2bbn n) )互不相交互不相交是指是指a ai i b bj j, i,j = 1,2,n., i,j = 1,2,n.例如：例如：1 2 3 4 5 63 5 6 4 2 1= (1 3 6)(2

25、 5)(4)循环又叫循环又叫轮换轮换，二阶轮换叫，二阶轮换叫对换对换我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物群论群论轮换上乘上一个对换的效果：(1)(1)、对换的两个元素分属于不同、对换的两个元素分属于不同的轮换中的轮换中两个轮换合并两个轮换合并成一个轮换。成一个轮换。有连个轮换有连个轮换( (a a1 1,a ,a2 2,a ,a3 3,a,an n),(b),(b1 1,b,b2 2,b,b3 3,b,bn n), ),一个对换一个对换(a(a1 1,b,b1 1) )( (a a1 1,a

26、 ,a2 2,a ,a3 3,a,an n) (a) (a1 1,b,b1 1)(b)(b1 1,b,b2 2,b,b3 3,b,bn n)=(a)=(a1 1,a ,a2 2,b,b1 1,b,b2 2bbn n) )(2)(2)、对换的两个元素属于同一个轮换、对换的两个元素属于同一个轮换一个轮换拆分成了一个轮换拆分成了两个轮换两个轮换(a1,a2,a3,an)(a1,ai) = (a1,a2,ai-1)(ai,ai+1,an)我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物群论群论例：传球游戏例：传球

27、游戏两个组进行传球比赛。每组两个组进行传球比赛。每组n n人，围成一个圈，每人有一个人，围成一个圈，每人有一个在该组中唯一的编号（在该组中唯一的编号（1n1n之间），每人有一个编号（之间），每人有一个编号（1n1n）在改组唯一的球。每个人的球的编号是任意给定的。然后，游在改组唯一的球。每个人的球的编号是任意给定的。然后，游戏开始，每组的人开始进行组内对传，争取以最短的时间把球戏开始，每组的人开始进行组内对传，争取以最短的时间把球传到位。传到位是指一个组中的每每人手中的球的编号与他自传到位。传到位是指一个组中的每每人手中的球的编号与他自己的编号相同。最后获胜的就是那个用最少的地传球次数把球己的

28、编号相同。最后获胜的就是那个用最少的地传球次数把球传到位的组。传到位的组。现需要你编一个程序从初始状态确定至少需几次对传才能将球现需要你编一个程序从初始状态确定至少需几次对传才能将球传到位。传到位。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物群论群论分析：分析：初始状态为一个置换，假设为：初始状态为一个置换，假设为：1 2 3 4 5 6 3 5 6 4 3 2末状态为末状态为n n个长度为个长度为1 1的轮换：的轮换： (1)(2)(3)(4)(5)(6)1 2 3 4 5 6 3 5 6 4 3 2

29、= (1 3 6)(2 5)(4)乘以乘以(2 5) (1 3 6)(2)(5)(4)乘以乘以(1 3) (1 6)(3)(2)(5)(4)乘以乘以(1 6)所以：在该假设下，至少需要所以：在该假设下，至少需要次对换，分别是次对换，分别是(2 5)(1 3)(1 6)(2 5)(1 3)(1 6)我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物群论群论结论结论: : 1 1、把初始状态转化成一系列轮换之积、把初始状态转化成一系列轮换之积2 2、若原轮换的长度为、若原轮换的长度为n n，次数为，次数为n-1n

30、-1；我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物Polya定理定理例：手镯例：手镯pku1286pku1286如果手镯有如果手镯有n n个位置可用来嵌入宝石，有个位置可用来嵌入宝石，有mm种宝种宝石可以嵌入，能生产出多少种不同类的手镯？石可以嵌入，能生产出多少种不同类的手镯？如果将其中一只手镯做某种旋转或翻转使得两如果将其中一只手镯做某种旋转或翻转使得两个手镯完全一样，我们认为这两个手镯是同类的。个手镯完全一样，我们认为这两个手镯是同类的。翻转翻转旋转旋转我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么

31、把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物Polya定理定理对于有对于有4 4个嵌宝个嵌宝石位置的手镯石位置的手镯来说，有来说，有4 4种旋种旋转方式，有转方式，有4 4种种翻转方式，用翻转方式，用轮换相乘来表轮换相乘来表示：示：1234置换置换轮换相乘轮换相乘C(i)C(i)循环节数循环节数旋转旋转1 1 (1)(2)(3)(4)4旋转旋转2 2(1 2 3 4)1旋转旋转3 3(1 3)(2 4)2旋转旋转4 4(1 4 3 2)1翻转翻转1 1 (1 4)(2 3)2翻转翻转2 2(1)(3)(2 4)3我吓了一跳，蝎子是多么丑恶和恐怖的东

32、西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物Polya定理定理PolyaPolya定理定理：设设G G是是p p个对象的一个置换群，用个对象的一个置换群，用k k种颜色突然这种颜色突然这p p个对象，个对象，若一种染色方案在群若一种染色方案在群G G的作用下变为另一种方案，则这两个的作用下变为另一种方案，则这两个方案当作是同一种方案，这样的不同染色方案数为：方案当作是同一种方案，这样的不同染色方案数为：L = 1 G f Gkc(f)对于手镯一题，设对于手镯一题，设n=4,m=2n=4,m=2L = (2L = (24 4+2+2+2+

33、22 2+2+2+2+22 2+2+23 3+2+22 2+2+23 3)/8=6)/8=6我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物Polya定理定理置换及循环节数的计算方法置换及循环节数的计算方法: :对于有对于有n n个位置的手镯，有个位置的手镯，有n n种旋转置换和种旋转置换和n n种翻转置换种翻转置换对于旋转置换对于旋转置换: c(fi) = gcd(n,i) i: c(fi) = gcd(n,i) i为一次转过为一次转过i i颗宝石。颗宝石。 i = 0 i = 0 时时 c=n;c=n;

34、对于翻转置换对于翻转置换: :如果如果n n为偶数为偶数 c(f) = n/2 c(f) = n/2 的置换有的置换有n/2n/2个个; ; c(f) = n/2+1 c(f) = n/2+1 的置换有的置换有n/2n/2个个如果如果n n为奇数，为奇数，c(f) = n/2+1;c(f) = n/2+1;我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物Polya定理定理Code#include #include #include using namespace std;int gcd(int a,int

35、 b) return b?gcd(b,a%b):a; double go(int n);int main() int n; while(cinn & n!=-1) if(n=0)cout0endl; else coutsetiosflags(ios:fixed) setprecision(0)go(n)endl; return 0; 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物Polya定理定理double go(int n) double r=0; int i; for(i=0;in;i+) if(i

36、=0)r+=pow(3.0,n); else r+=pow(3.0,gcd(n,i); if(n%2=0) r+=n/2*(pow(3.0,n/2+1)+pow(3.0,n/2); else r+=n*(pow(3.0,(n-1)/2+1); return r/n/2;我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物递推关系递推关系在一些计数问题中，很难直接得到计数序列在一些计数问题中，很难直接得到计数序列aiai的通项公式，但是可以建立相邻几项的关系，的通项公式，但是可以建立相邻几项的关系，可以利用这些

37、关系一步步计算出需要的值，或者可以利用这些关系一步步计算出需要的值，或者求解递推关系得到通项公式。求解递推关系得到通项公式。例例1 1上楼梯问题上楼梯问题某人欲登上某人欲登上n n级楼梯，若没次只能跨一级或级楼梯，若没次只能跨一级或两级，问他从地面上到第两级，问他从地面上到第n n级楼梯，共有多少种不同的方法。级楼梯，共有多少种不同的方法。解，假设上到第解，假设上到第n n级楼梯的方法数为级楼梯的方法数为a an n，那么，第一步无非有，那么，第一步无非有两种走法：两种走法：（1 1）跨一级，则余下的）跨一级，则余下的n-1n-1级有级有a an-1n-1种上法；种上法；（2 2）跨两级，

38、则余下的）跨两级，则余下的n-2n-2级有级有a an-2n-2种上法；种上法；所以所以 an = aan = an-1n-1 + a + an-2n-2; ;我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物递推关系递推关系例zju1475 ranklistn个人参加比赛，有多少种不同的名次排列方法，注意多人并列的情况。Sample InputSample Input123-1Sample OutputSample Output1313n输入输入结束结束我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在

39、这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物递推关系递推关系分析：分析：设设n n个人参加比赛，个人参加比赛，mm个不同名次的个不同名次的ranklistranklist共共有有F(n,m)F(n,m)个，则：个，则：F(n,m)=F(n,m)=( (在在n n个人个人m-1m-1个不同名次的个不同名次的ranklistranklist中增加一个名次共有中增加一个名次共有mm中方法中方法) )mF(n-1,m-1)mF(n-1,m-1)mF(n-1,m)mF(n-1,m)( (将新增加的一人加到将新增加的一人加到mm个名次中个名次中的任一个中有的任一个中有mm中方法中方法) )结论：结论：An = F(n,1)+F(n,2)+F(n,n)An = F(n,1)+F(n,2)+F(n,n)

展开阅读全文