NOIP数学--排列组合.ppt

《NOIP数学--排列组合.ppt》由会员分享，可在线阅读，更多相关《NOIP数学--排列组合.ppt（28页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、信息学竞赛信息学竞赛-之数学之数学知识知识年份年份题目名称题目名称考查内容考查内容难度难度1998Power数学（进制转换）数学（进制转换）1999Cantor表表模拟模拟或或数学数学2000税收与补贴问题税收与补贴问题数学数学或或枚举枚举2001最大公约数和最小公倍数最大公约数和最小公倍数数学（辗转相除法）数学（辗转相除法）2002选数选数生成算法、素数判定生成算法、素数判定2003栈栈数学（卡特兰数）数学（卡特兰数）2005循环循环高精度运算、数论、快速幂高精度运算、数论、快速幂2006数列数列数学（进制转换）数学（进制转换）2007Hanoi双塔问题双塔问题数学、高精度数学、高精度200

2、9细胞分裂细胞分裂数论数论Noip历年提高组决赛题中的数学题及难度（最难5星）第一节第一节排列组合排列组合 加法原理、乘法原理 排列组合生成算法加法原理加法原理若事件若事件X能以能以x种方式发生，另一个不同的时间种方式发生，另一个不同的时间Y能以能以y种不同的方式发生，则事件种不同的方式发生，则事件X或者事件或者事件Y能以（能以（x+y）种方式发生。种方式发生。例：全系共三个班级，这三个班级准备参加例：全系共三个班级，这三个班级准备参加acm竞赛竞赛的学生人数分别是的学生人数分别是3，4，5，则全系准备参加，则全系准备参加acm竞赛竞赛的人数的人数3+4+5=12.乘法原理乘法原理若事件若事件

3、X能以能以x种方式发生，另一个不同的事件种方式发生，另一个不同的事件Y能以能以y种不同的方式发生，则事件种不同的方式发生，则事件x和事件和事件y能以能以xy种方式发种方式发生。生。例：求小于例：求小于10亿且不包含数字亿且不包含数字1的正整数的个数。的正整数的个数。解：解：首先计算不包含数字首先计算不包含数字1的数的个数，从的数的个数，从0，2-9中寻找中寻找9个符号的字符串，第一个数字有个符号的字符串，第一个数字有9种选择，第种选择，第二个数字有二个数字有9种选择，等等。种选择，等等。根据加法原理共有根据加法原理共有99=387420489个数，其中包括个数，其中包括000000000.如果

4、从如果从100000000中减去这样的数字，得中减去这样的数字，得到的答案为到的答案为612579511.排列与全排列排列与全排列从从n个不同元素中，有次序的选取个不同元素中，有次序的选取r个元素，称为从个元素，称为从n中取中取r个的排列，其排列数记为个的排列，其排列数记为P(n,r).当当r=n时，称为时，称为全排列。全排列。例如：从例如：从A,B,C,D中有序选取两个字母，则有中有序选取两个字母，则有12种选择。种选择。AB AC AD BA BC BD CA CB CD DA DB DCP(4,2)=12.定理：定理：p(n,rp(n,r)=)=n!/(n-rn!/(n-r)!)!例题：

5、从例题：从n个不同元素中选取个不同元素中选取r个元素围成一个圆。个元素围成一个圆。求选取的方案总数。求选取的方案总数。解：从解：从n个不同元素中选取个不同元素中选取r个元素选取的方案总数个元素选取的方案总数为为p(n,r).a1ar为其中一组解。为其中一组解。将其变换，将其变换，a2-ar,a1;a3-ar,a1,a2;.共有共有r个排列。但是个排列。但是这这n个排列对一个圆。所以题目中所求方案为个排列对一个圆。所以题目中所求方案为p/r组合组合从从n个不同元素中，选取个不同元素中，选取r个元素而不考虑其次序，成个元素而不考虑其次序，成为从为从n个中取个中取r个的组合，记为个的组合，记为c(n

6、,r).例：从（例：从（a,b,c,d）中选取出）中选取出2个元素的组合，则有如个元素的组合，则有如下情况：下情况：（a,b）(a,c)(a,d)(b,c)(b,d)(c,d)记作记作 c(4,2)=6;C(n,r)=p(n,r)/r!=n!/r!(n-r)!例题例题1如图所示的棋盘，若从左下角走到右上角，如图所示的棋盘，若从左下角走到右上角，并且规定只能向上想右走，问共多少种方案？并且规定只能向上想右走，问共多少种方案？解题思路：左右 4步下上 3步无论怎么选择均为右4+上3。0向右走1向上走所以可以走法可以看作由01组成的字符串即所求方案数为4个0和3个1组成的7位字符串的个数。C(7,4

7、)=?排列组合生成算法排列组合生成算法R-排列生成算法：排列生成算法：采用回溯法生成从采用回溯法生成从n中选中选r个元素的所有排列情况：个元素的所有排列情况：n个元素用个元素用1，2，n来表示来表示 函数函数done递归的层数递归的层数i表示当前正在生成排列中第表示当前正在生成排列中第i个位置的数。个位置的数。函数函数done(i)执行时，首先判断执行时，首先判断j是否在该排列以前是否在该排列以前的几个位置上出现过，若出现则说明的几个位置上出现过，若出现则说明j不可能出现在当不可能出现在当前位置上，此时前位置上，此时j值增值增1重复以上判断，重复以上判断，j=n时回溯；若时回溯；若j没有在该排

8、列以前的位置上出现，则该位置上的值就没有在该排列以前的位置上出现，则该位置上的值就是是j，后判断递归的层数，后判断递归的层数i与与r的值是否相等。若的值是否相等。若i=r，输，输出一个新的排列并回溯。若出一个新的排列并回溯。若i=n;即：即：售票处将收到的售票处将收到的50的钞票最终全部找出，的钞票最终全部找出，将将100的钞票全部留下，并且一旦收到一张面值为的钞票全部留下，并且一旦收到一张面值为100的钞票，则一定要找出一张面值的钞票，则一定要找出一张面值50的钞票。的钞票。栈模型表示：若一人手持栈模型表示：若一人手持50的钞票购票，相当于一的钞票购票，相当于一个元素进栈。将问题转化为：个元

9、素进栈。将问题转化为：1n共共n个元素依次进个元素依次进栈，问共多少中出栈顺序。栈，问共多少中出栈顺序。n个元素的全排列共有个元素的全排列共有n！种方案，那么！种方案，那么n!种方案是种方案是否都是可能的出栈顺序？否都是可能的出栈顺序？若若a1,a2,a3,an是可能的出栈顺序，则一定不存在这是可能的出栈顺序，则一定不存在这样的情况，使得样的情况，使得ijk,且且ajakai?证明：若证明：若ijaj,那么那么aj出栈时，如果出栈时，如果ak已经在栈中，则已经在栈中，则ak比比aj先入栈，由输入序列知道：先入栈，由输入序列知道：akaj,所以有所以有akajai;当当aj出栈时，如果出栈时，如

10、果ak 尚未入栈，则由输入序尚未入栈，则由输入序列知道列知道ajaiak.(2）如果）如果aIaj,aiajak.因此：不可能出现因此：不可能出现ijk,aJakai的情况的情况栈模型算法栈模型算法 算法先产生算法先产生1-n共共n个数的全排列，对于每种排列，个数的全排列，对于每种排列，若符合前面所讲的出栈规则，那么这个排列便是一个若符合前面所讲的出栈规则，那么这个排列便是一个可能的出栈序列。计数器加可能的出栈序列。计数器加1，当，当n个全排列列举结束个全排列列举结束时，得到问题的解。时，得到问题的解。递归算法递归算法 令令f（m,n）表示）表示m个人手持个人手持50的钞票。的钞票。N个人手持

11、个人手持100的钞票时总共的方案数。的钞票时总共的方案数。（1）当）当n=0时，时，n=0意味着排队购票的所有人手中拿的都是意味着排队购票的所有人手中拿的都是50的，的，那么这个那么这个m的人排队方案总数为的人排队方案总数为1，即，即f(m,0)=1 (2)当当mn 当当mn时，即使时，即使m张张50全部找出，仍会找不开，所全部找出，仍会找不开，所以排队数为以排队数为0（3）其他）其他 第（第（m+n）个人站在第（）个人站在第（m+n-1）的后面，则第（）的后面，则第（m+n）个）个人的排队方式可由下列人的排队方式可由下列2种情况获得：种情况获得：1，第（，第（m+n）个人手持）个人手持100

12、，则在他之前的，则在他之前的M+n-1个人中个人中m人手持人手持50的，的，n-1个人手持个人手持100的钞票，此种情况共的钞票，此种情况共f(m,n-1)2,第（第（m+n）个人手持）个人手持50，则在他之前的，则在他之前的M+n-1个人中个人中m-1人手持人手持50的，的，n 个人手持个人手持100的钞票，此种情况共的钞票，此种情况共f(m-1,n)加法原理：加法原理：f(m,n)=f(m-1,n)+f(m,n-1)f(m,n)=0 1 f(m,n)=f(m-1,n)+f(m,n-1)4)递推算法递推算法递归算法：递归算法：f(4,4)14 f(3,4)0 f(4,3)14 f(3,3)5

13、 f(4,2)9 f(2,3)0 f(3,2)5 f(3,2)f(4,1)4 f(2,2)2 f(3,1)3 f(2,2)f(3,1)f(1,2)0 f(2,1)2 f(1,2)0 f(2,1)2 我们发现f（3，2）等节点有重复计算，课件递归算法产生大量的数据冗余，这些冗余数据是限制递归算法的主要因素，从而导致了模型3虽进行了数学抽象，但是算法实现起来的效率并不高。如何解决呢？计算中保留数值-采用递推法保证同一个数据只计算一次。O(n2)复杂度复杂度Done()for（a=1;a=n;a+）dataa1=a;for(a=2;a=n;a+)for(b=2;bj;若节点若节点i是节点是节点K的左

14、儿子，的左儿子，节点节点j是节点是节点k的右儿子，则的右儿子，则ij.中序遍历时最左边的节点一定是第一个节点，最右中序遍历时最左边的节点一定是第一个节点，最右边的节点一定是最后一个节点。对于任意一个具有边的节点一定是最后一个节点。对于任意一个具有n个节点的二叉树，前序遍历顺序为个节点的二叉树，前序遍历顺序为1n,即即n个元素的个元素的入栈顺序，中序遍历顺序便是这入栈顺序，中序遍历顺序便是这n个元素的出栈顺序，个元素的出栈顺序，即即2n个人的排队方式总数为个人的排队方式总数为n个节点的二叉树的个数，个节点的二叉树的个数，又因为具有又因为具有n个节点的二叉树的个数为个节点的二叉树的个数为cn=1/

15、n+1 c(2n n)catalan数。数。前序遍历遍历结果：ABDECF中序遍历遍历结果：DBEAFC排列组合的方法：排列组合的方法：用用1表示一个手拿表示一个手拿50的人，用的人，用0表示一个手拿表示一个手拿100的的人，那么求解的问题可以转化为：人，那么求解的问题可以转化为：n个个1和和n个个0组合一组合一个个2n位的二进制数，要求从左向右扫描，位的二进制数，要求从左向右扫描，1的累计数不的累计数不小于小于0的累计数，求满足这个条件的二进制的数的个的累计数，求满足这个条件的二进制的数的个数。数。在在2n位上填入位上填入n个个1的方案数为的方案数为c(2n,n)不填不填1的其的其余余n位自

16、动填入位自动填入0.从从c(2n,n)中减去不符合要求的方案中减去不符合要求的方案数就是问题的解。不符合要求的方案即从左向右扫描，数就是问题的解。不符合要求的方案即从左向右扫描，出现出现0的累计次比的累计次比1的多。的多。不符合条件数的特征：从左向右扫描，必然会在不符合条件数的特征：从左向右扫描，必然会在某一个奇数位某一个奇数位2m+1位上首先出现位上首先出现m+1个个0和和m个个1；而；而后的后的2（n-m）-1位上有位上有n-m个个1，n-m-1个个0.如果把后如果把后面这部分面这部分2（n-m）-1位的位的0和和1交换，使之成为交换，使之成为n-m个个0，n-m-1个个1，结果得到一个由

17、，结果得到一个由n+1个个0和和n-1个个1组成的组成的2n位数。即不符合要求的数字对应一个由位数。即不符合要求的数字对应一个由n+1个个0和和n-1个个1 组成的一个排列。组成的一个排列。反之，任何一个由反之，任何一个由n+1个个0 和和n-1个个1组成的组成的2n位数，位数，由于由于0的个数多于的个数多于2个，个，2n是偶数，所以一定在某一个是偶数，所以一定在某一个奇数位上出现奇数位上出现0的累计数超过的累计数超过1的累计数，同样后面部的累计数，同样后面部分，令分，令0和和1交换，使之成为一个交换，使之成为一个n个个0和和n个个1组成的组成的2n位数，即位数，即n+1个个0和和n-1个个1

18、组成的组成的2n位数，一定对应着位数，一定对应着一个不符合要求的数。一个不符合要求的数。所以不符合要求的数的总数为所以不符合要求的数的总数为 c(2n n+1)所以结果为所以结果为C(2n n)-c(2n n+1)=1/n+1*C(2n n)五种算法的实际运行时间五种算法的实际运行时间n运行结果运行结果T1(n)T2(n)T3(n)T4(n)T5(n)5420.00010.00010.00010.00010.000110167960.00011.15380.00010.0001600.24270.0001603.68130.00016013.51650.00016049.50550.00010.0001