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出栈时,如果出栈时,如
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- NOIP 数学 排列组合
限制150内