NOIP初赛数学知识点.ppt

《NOIP初赛数学知识点.ppt》由会员分享，可在线阅读，更多相关《NOIP初赛数学知识点.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、初赛试题形式初赛试题形式 初赛：初赛全部为笔试，满分初赛：初赛全部为笔试，满分100分。试题由四部分组成：分。试题由四部分组成： 1、选择题：共、选择题：共20题，每题题，每题1.5分，共计分，共计30分。每题有分。每题有5个备选答案，前个备选答案，前10个题为单选题个题为单选题(即每题有且只有一个正确答案，选对得分即每题有且只有一个正确答案，选对得分)，后，后10题为不定项选题为不定项选择题择题(即每题有即每题有1至至5个正确答案，只有全部选对才得分个正确答案，只有全部选对才得分)。 2、问题求解题：共、问题求解题：共2题，每题题，每题5分，共计分，共计10分。试题给出一个叙述较为简分。试题

2、给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。考生给出的答案与标准答案相同，则得分：否则不得分。考生给出的答案与标准答案相同，则得分：否则不得分。 3、程序阅读理解题：共、程序阅读理解题：共4题，每题题，每题8分，共计分，共计32分。题目给出一段程序分。题目给出一段程序(不不一定有关于程序功能的说明一定有关于程序功能的说明)，考生通过阅读理解该段程序给出程序的输出。输，考生通过阅读理解该段程序给出程序的输出。输出与标准答案一致，则得分；否则不得分。出与标准答案一致，则得分；否则不

3、得分。 4、程序完善题：共、程序完善题：共2题，每题题，每题14分，共计分，共计28分。题目给出一段关于程序分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，一部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对则得分；否则不得分。填出被略去的语句。填对则得分；否则不得分。 信息学竞赛中的数学知识信息学竞赛中的数学知识 集合的运算 排列与组合 集合及其运算1 1、集合的运算：

4、并、交、补、差、集合的运算：并、交、补、差 2 2、容斥原理、容斥原理1 1、集合的运算：并、交、补、差、集合的运算：并、交、补、差并：并：交：交：补：补： 或或或或差差: -: -A AB BA AB BA AA AB BA BA BA BA BAA-BA-B8. 8. （NOIP9NOIP9）设全集）设全集E=1E=1，2 2，3 3，4 4，55，集合，集合A=1A=1，44，B=1B=1，2 2，55，C=2C=2，44，则集合（，则集合（A BA B）C C 为（为（ e e ）。）。 A A） 空集空集 B B） 1 C1 C） 33，5 D5 D）11，5 E5 E） 11，3

5、3，551 1、（、（NOIP10NOIP10）设全集）设全集I = a, b, c, d, e, f, gI = a, b, c, d, e, f, g，集合，集合A = a, b, cA = a, b, c， B = b, d, eB = b, d, e，C = e, f, gC = e, f, g，那么集合为（，那么集合为（ a a ）。）。 A. a, b, c, d B. a, b, d, e A. a, b, c, d B. a, b, d, e C. b, d, e D. b, c, d, e E. d, f, g C. b, d, e D. b, c, d, e E. d, f

6、, g2. 2. （NOIP11NOIP11）设全集）设全集I = a, b, c, d, e, f, g, hI = a, b, c, d, e, f, g, h， 集合集合BABA= a, b, c, d, e, f= a, b, c, d, e, f， C AC A= c, d, e= c, d, e，AB = a, dAB = a, d，那么集合，那么集合C B A C B A 为（为（a a ）。）。 A. c, e B. d, e C. e D. c, d, e E. d, fA. c, e B. d, e C. e D. c, d, e E. d, f)()(BCBA2 2、容斥

7、原理、容斥原理在计数时，为了使重叠部分不被重复计算，人们研在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：究出一种新的计数方法，这种方法的基本思想是：先先不考虑重叠不考虑重叠的情况，把包含于某内容中的的情况，把包含于某内容中的所有对所有对象的数目象的数目先计算出来，然后再把计数时先计算出来，然后再把计数时重复计算的数目重复计算的数目排斥出去，排斥出去，使得计算的结果既无遗漏又无重复，这种计使得计算的结果既无遗漏又无重复，这种计数的方法称为数的方法称为容斥原理容斥原理。对有限集合对有限集合S S，用表示，用表示S S的元素个数的元素个数 S容斥原理的第一形

8、式：容斥原理的第一形式：设设A A，B B是有限集合，则是有限集合，则ABABAB容斥原理的第二形式：设容斥原理的第二形式：设A A、B B、C C是有限集合，则是有限集合，则ABCABCBCCAABABC 1 1、（、（NOIP10NOIP10）7575名儿童到游乐场去玩。他们可以骑名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中旋转木马，坐滑行铁道，乘宇宙飞船。已知其中2020人这三种东西都玩过，人这三种东西都玩过，5555人至少玩过其中的两人至少玩过其中的两种。若每样乘坐一次的费用是种。若每样乘坐一次的费用是5 5元，游乐场总共收元，游乐场总共收入入700700，

9、可知有，可知有 10 10 名儿童没有玩过其中任何一名儿童没有玩过其中任何一种。种。2 2、某学校足球队有球衣、某学校足球队有球衣3030件，篮球队有球衣件，篮球队有球衣1515件，件，排球队有球衣排球队有球衣1818件，三队队员总数为件，三队队员总数为5050人，其中人，其中有有2 2人同时参加人同时参加3 3个队，那么同时个队，那么同时只只参加两个队的参加两个队的队员有多少？队员有多少？ 9 9、分母是、分母是10011001的最简分数一共有多少个？的最简分数一共有多少个？只是玩过其中两种的有55-20=35人只是玩过其中一种人所花费用 700-20*（5*3）-35*（5*2）=50元只

10、是其中一种的人数 505=10人没有玩过其中任何一种的人数 75-20-35-10=10人容斥原理A+B+C-（A与B重合-A与C重合-B与C重合）+A、B、C重合=总数30+15+18-（A与B重合-A与C重合-B与C重合）+2=50（ A 与 B 重 合 - A 与 C 重 合 - B 与 C 重 合 ）=30+15+18+2-50=15人 15-2*3=9人1001=71113分子中不能含有质因数7、11、13即1至1001中，不能被7、11、13整除的数有多少个？10017=143100111=91100113=7710017,11=13, 7,11-7和11的最小公倍数10017,1

11、3=11, -100111,13=7, -10017,11,13=1 143+91+77-(13+11+7)+1=281个不能被7，11，13整除的数有 1001-281=720个排列与组合排列与组合1.1.排列的定义排列的定义: :从从n n个不同元素中个不同元素中, ,任取任取m m个元素个元素, ,按照一定的顺序排成一按照一定的顺序排成一列列, ,叫做从叫做从n n个不同元素中取出个不同元素中取出m m个元素的一个排列个元素的一个排列. .)!(!)1()2)(1(mnnmnnnnPmn排列数公式排列数公式: :全排列问题：全排列问题： n n个不同的元素排成一排，排列方法有：个不同的元

12、素排成一排，排列方法有：nnP=n=n* *(n-1)(n-1)* *(n-2)(n-2)* * *2 2* *1=n!1=n!2.2.组合的定义组合的定义: :从从n n个不同元素中个不同元素中, ,任取任取m m个元素个元素, ,并成一组并成一组, ,叫做从叫做从n n个个不同元素中取出不同元素中取出m m个元素的一个组合个元素的一个组合. .组合数公式组合数公式: :排列与组合的区别与联系排列与组合的区别与联系: :与顺序有关的为排列问题与顺序有关的为排列问题, ,与顺序与顺序无关的为组合问题无关的为组合问题. .)!(!)1()2)(1(mnmnmmnnnnPPCmmmnmn加法原理和

13、乘法原理加法原理和乘法原理从从A到到C共有多少中走法？共有多少中走法？ABC例例1 1 :学校师生合影，共学校师生合影，共8 8个学生，个学生，4 4个老师，要个老师，要求老师在学生中间，且老师互不相邻，共有多求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式？少种不同的合影方式？解解 先排学生共有先排学生共有 种排法种排法, ,然后把老师插入学生然后把老师插入学生之间的空档，共有之间的空档，共有7 7个空档可插个空档可插, ,选其中的选其中的4 4个空档个空档, ,共共有有 种选法种选法. .根据乘法原理根据乘法原理, ,共有的不同坐法为共有的不同坐法为 种种. .88P47P478

14、8PP结论结论1 1 插入法插入法: :对于某两个元素或者几个元素要求对于某两个元素或者几个元素要求不相邻的问题不相邻的问题, ,可以用插入法可以用插入法. .即先排好没有限制条即先排好没有限制条件的元素件的元素, ,然后将有限制条件的元素按要求插入排好然后将有限制条件的元素按要求插入排好元素的空档之中即可元素的空档之中即可. .例例2 : 2 : 5 5个男生个男生3 3个女生排成一排个女生排成一排,3,3个女生要排在一起个女生要排在一起, ,有多少种不同的排法有多少种不同的排法? ? 解解 因为女生要排在一起因为女生要排在一起, ,所以可以将所以可以将3 3个女生看成是个女生看成是一个人一

15、个人, ,与与5 5个男生作全排列个男生作全排列, ,有有 种排法种排法, ,其中女生内其中女生内部也有部也有 种排法种排法, ,根据乘法原理根据乘法原理, ,共有共有 种不同的排种不同的排法法. .33P66P3366PP结论结论2 2 捆绑法捆绑法: :要求某几个元素必须排在一起的问题要求某几个元素必须排在一起的问题, ,可以用捆绑法来解决问题可以用捆绑法来解决问题. .即将需要相邻的元素合并即将需要相邻的元素合并为一个元素为一个元素, ,再与其它元素一起作排列再与其它元素一起作排列, ,同时要注意合同时要注意合并元素内部也可以作排列并元素内部也可以作排列. .例例3 3 : : 袋中有不

16、同年份生产的袋中有不同年份生产的5 5分硬币分硬币2323个个, ,不同年份生产的不同年份生产的1 1角硬币角硬币1010个个, ,如果从袋中取如果从袋中取出出2 2元钱元钱, ,有多少种取法有多少种取法? ?解解 把所有的硬币全部取出来把所有的硬币全部取出来, ,将得到将得到 0.050.0523+0.1023+0.1010=2.1510=2.15元元, ,所以比所以比2 2元多元多0.150.15元元, ,所所以剩下以剩下0.150.15元即剩下元即剩下3 3个个5 5分或分或1 1个个5 5分与分与1 1个个1 1角角, ,所以所以共有共有 种取法种取法. .110123323CCC结论

17、结论3 3 剩余法剩余法: :在组合问题中在组合问题中, ,有多少取法有多少取法, ,就有多少就有多少种剩法种剩法, ,他们是一一对应的他们是一一对应的, ,因此因此, ,当求取法困难时当求取法困难时, ,可可转化为求剩法转化为求剩法. .分析分析 此题是一个组合问题此题是一个组合问题, ,若是直接考虑取钱的问若是直接考虑取钱的问题的话题的话, ,情况比较多情况比较多, ,也显得比较凌乱也显得比较凌乱, ,难以理出头绪难以理出头绪来来. .但是如果根据组合数性质考虑剩余问题的话但是如果根据组合数性质考虑剩余问题的话, ,就就会很容易解决问题会很容易解决问题. .例例4 4 学校安排考试科目学校

18、安排考试科目9 9门门, ,语文要在数学之前考语文要在数学之前考, ,有有多少种不同的安排顺序多少种不同的安排顺序? ?解解 不加任何限制条件不加任何限制条件, ,整个排法有整个排法有 种种, ,“语文安排语文安排在数学之前考在数学之前考”, ,与与“数学安排在语文之前考数学安排在语文之前考”的排法的排法是相等的是相等的, ,所以语文安排在数学之前考的排法共有所以语文安排在数学之前考的排法共有 种种. .99P9921P结论结论4 4 对等法对等法: :在有些题目中在有些题目中, ,它的限制条件的肯定与它的限制条件的肯定与否定是对等的否定是对等的, ,各占全体的二分之一各占全体的二分之一. .

19、在求解中只要求在求解中只要求出全体出全体, ,就可以得到所求就可以得到所求. .分析分析 对于任何一个排列问题对于任何一个排列问题, ,就其中的两个元素来讲就其中的两个元素来讲的话的话, ,他们的排列顺序只有两种情况他们的排列顺序只有两种情况, ,并且在整个排列并且在整个排列中中, ,他们出现的机会是均等的他们出现的机会是均等的, ,因此要求其中的某一种因此要求其中的某一种情况情况, ,能够得到全体能够得到全体, ,那么问题就可以解决了那么问题就可以解决了. .并且也避并且也避免了问题的复杂性免了问题的复杂性. .例例5 5 某个班级共有某个班级共有4343位同学位同学, ,从中任抽从中任抽5

20、 5人人, ,正、副正、副班长、团支部书记至少有一人在内的抽法有多少种班长、团支部书记至少有一人在内的抽法有多少种? ?解解 4343人中任抽人中任抽5 5人的方法有人的方法有 种种, ,正副班长正副班长, ,团支部团支部书记都不在内的抽法有书记都不在内的抽法有 种种, ,所以正副班长所以正副班长, ,团支部书团支部书记至少有记至少有1 1人在内的抽法有人在内的抽法有 种种. .543C540C540543CC结论结论5 5 排异法排异法: :有些问题有些问题, ,正面直接考虑比较复杂正面直接考虑比较复杂, ,而而它的反面往往比较简捷它的反面往往比较简捷, ,可以先求出它的反面可以先求出它的反

21、面, ,再从整再从整体中排除体中排除. .分析分析 此题若是直接去考虑的话此题若是直接去考虑的话, ,就要将问题分成好几就要将问题分成好几种情况种情况, ,这样解题的话这样解题的话, ,容易造成各种情况遗漏或者重容易造成各种情况遗漏或者重复的情况复的情况. .而如果从此问题相反的方面去考虑的话而如果从此问题相反的方面去考虑的话, ,不不但容易理解但容易理解, ,而且在计算中也是非常的简便而且在计算中也是非常的简便. .这样就可这样就可以简化计算过程以简化计算过程. .圆周排列：圆周排列： 从从n n个不同的元素中取个不同的元素中取r r个沿一圆周排列，排列的方案：个沿一圆周排列，排列的方案：r

22、nP/rN N个元素的圆周排列：个元素的圆周排列：nnP/n= =（n-1n-1）! !有重复元素的排列问题：有重复元素的排列问题：如：如：n n1 1个个a a，n n2 2个个b b，n n3 3个个c c，排成一排，有多少种排列方法。，排成一排，有多少种排列方法。123123()!*!*!nnnnnn1.1.（NOIP7NOIP7）平面上有三条平行直线，每条直线上分别有）平面上有三条平行直线，每条直线上分别有7 7，5 5，6 6个点，且不同直线上三个点都不在同一条直线上。个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？问用这些点为顶点，能组成多少个

23、不同四边形？225022502 2、 （NOIP10NOIP10）由）由3 3个个a a，5 5个个b b和和2 2个个c c构成的所有字符串中，构成的所有字符串中，包含子串包含子串“abc”abc”的共有（的共有（ ）个。）个。 A. 40320 B. 39600A. 40320 B. 39600由由3 3个个a a，5 5个个b b和和2 2个个c c构成的所有构成的所有字符串中，包含子串字符串中，包含子串“abc”abc”的共有的共有C. 840 C. 840 D D. 780 . 780 E. 60E. 60 当abc在第一位时,后面一共有105种排列(7!/(2!*4!)=105)当

24、abc在第二位时,也是105种.当abc在第八位时,也是105.105*8=840种里面有重复的减去有2个字字串abc的.一共60种(6!/(2!*3!)=60)所以840-60=780种 1 1 (NOIP8)(NOIP8) 在书架上放有编号为在书架上放有编号为1 1 ，2 2 ，n n的的n n本书。本书。现将现将n n本书全部取下然后再放回去，当放回去时要求每本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：本书都不能放在原来的位置上。例如：n = 3n = 3时：时： 原来位置为：原来位置为：1 2 31 2 3 放回去时只能为：放回去时只能为：3 1 2 3

25、 1 2 或或 2 3 1 2 3 1 这两种这两种 问题：求当问题：求当n = 5n = 5时满足以上条件的放法共有多少时满足以上条件的放法共有多少种？（不用列出每种放法）种？（不用列出每种放法）4444错排问题：错排问题： n n个不同元素的错排问题：个不同元素的错排问题： 如：如：1 1，2 2，3 3，。，。，n n 的错排问题，的错排问题，i i不在第不在第i i个位置的排列方法。个位置的排列方法。分析：分析： 设设f(n)f(n)为为n n个不同元素的错排方案。个不同元素的错排方案。 第一部分：第一部分：n n先不动，把另外的先不动，把另外的n-1n-1个数错排，方案是：个数错排，

26、方案是：f f（n-1n-1），然后），然后n n和和另外的另外的n-1n-1个每一个交换，共有个每一个交换，共有(n-1)(n-1)* *f(n-1)f(n-1)种方案。种方案。 第二部分：第二部分：n n和其他的和其他的n-1n-1个之一交换，其余的个之一交换，其余的n-2n-2个错排，共有个错排，共有 （n-1n-1）* *f f（n-2n-2）种方案。）种方案。由加法原理：由加法原理： f(n)=(n-1)f(n)=(n-1)* *(f(n-1)+f(n-2)(f(n-1)+f(n-2) f(1)=0;f(2)=1; f(1)=0;f(2)=1;11111( )!(.( 1)2!3!4

27、!5!nf nnn错排的计算公式：错排的计算公式：几类重要的递推关系：几类重要的递推关系：一、第二类一、第二类Stirling数数 问题一：放置小球问题一：放置小球n个有区别的球放到个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类表示，称为第二类Stirling数数 设有设有n个不同的球，分别用个不同的球，分别用b1,b2,bn表示。从中取出一个球表示。从中取出一个球bn，bn的放法有以下两种：的放法有以下两种：1)bn独自占一个盒子；那么剩下的球只能放在独自占一个盒子；那么剩下的球只能放在m-1个盒子中

28、，方案数为个盒子中，方案数为 S(n-1,m-1) 2)bn与别的球共占一个盒子；那么可以事先将与别的球共占一个盒子；那么可以事先将b1,b2,bn-1这这n-1个球放入个球放入m个个盒子中，然后再将球盒子中，然后再将球bn可以放入其中一个盒子中，方案数为可以放入其中一个盒子中，方案数为 m*S(n-1,m) S(n,m)=m*S(n-1,m)+S(n-1,m-1) (n1,m1)边界条件：边界条件：S(n,1)=1；S(n,n)=1；S(n,k)=0(kn)问题二：集合划分问题。问题二：集合划分问题。设设S是一个包含是一个包含n个元素的集合，个元素的集合，S=b1,b2,b3,bn,现需要将

29、现需要将S集集合划分为合划分为m个满足如下条件的集合个满足如下条件的集合S1,S2, Sm。Si;SiSj=;S1S2Sm=S; (1=I ,j=m)则称则称S1,S2, ,Sm是是S的一个划分。的一个划分。编程：输入编程：输入n和和m的值，输出不同的划分方案数。的值，输出不同的划分方案数。要求：输入数据有一行，第一个数是要求：输入数据有一行，第一个数是n,第二个数第二个数m。样例：样例： 输入：输入：4 3 输出：输出：6noip131给定给定n 个有标号的球，标号依次为个有标号的球，标号依次为1，2，n。将这将这n 个球放入个球放入r 个相同的盒子里，不允许有空盒，个相同的盒子里，不允许有

30、空盒，其不同放置方法的总数记为其不同放置方法的总数记为S(n,r)。例如，。例如，S(4,2)=7，这这7 种不同的放置方法依次为种不同的放置方法依次为(1),(234), (2),(134), (3),(124), (4),(123), (12),(34), (13),(24),(14),(23)。当。当n=7,r=4 时，时，S(7,4)= _350_递推公式递推公式S(n,r)=S(n-1,r)*r+S(n-1,r-1).因为把因为把n个球放入个球放入r个个箱子箱子,相当于先把相当于先把n-1个球放好再放最后一个个球放好再放最后一个.最后一个有两种最后一个有两种放法：放入前面已经有球的箱

31、子或者独占一个箱子放法：放入前面已经有球的箱子或者独占一个箱子.前者对前者对应应S(n-1,r)*r (放入每一个不同的箱子都是一种不同的放法放入每一个不同的箱子都是一种不同的放法,因因为箱子内原来的球不同为箱子内原来的球不同),后者对应后者对应S(n-1,r-1).二、二、Catalan数数问题一：凸问题一：凸n边形的三角形剖分边形的三角形剖分在一个凸在一个凸n边形中，通过不相交于边形中，通过不相交于n边形内部的对角线，把边形内部的对角线，把n边形拆分成若边形拆分成若干三角形，不同的拆分数目用干三角形，不同的拆分数目用f(n)表之，表之，f(n)即为即为Catalan数。例如五边形数。例如五

32、边形有如下五种拆分方案，故有如下五种拆分方案，故f(5)=5。求对于一个任意的凸。求对于一个任意的凸n边形相应的边形相应的f(n)。区域是一个凸区域是一个凸k边形，区域是一个凸边形，区域是一个凸n-k+1边形，边形，区域的拆分方案总数是区域的拆分方案总数是f(k)；区域的拆分方案数为区域的拆分方案数为f(n-k+1)；故包含故包含P1PkPn的的n 边形的拆分方案数为边形的拆分方案数为f(k)* f(n-k+1)种种 121)i-f(n *f(i)niF(n)= 问题二：二叉树数目问题二：二叉树数目问题描述：求问题描述：求n个结点能构成不同二叉数的数目。个结点能构成不同二叉数的数目。【问题分析

33、问题分析】：设设F(n)为为n个结点组成二叉树的数目。个结点组成二叉树的数目。容易知道：容易知道：f(1)=1; f(2)=2, f(3)=5选定其中选定其中1个结点为根，左子树结点的个数为个结点为根，左子树结点的个数为i，二叉树数目，二叉树数目f（i）种；右子树结点数目为种；右子树结点数目为n-i-1，二叉树数目，二叉树数目f（n-i-1）种，）种，I的可取的可取范围范围0，n-1。所以有：。所以有：F(n)= 为了计算的方便：约定为了计算的方便：约定f（0）=1101)- i -f(n *f(i)ni211nnCn问题三：出栈序列问题三：出栈序列问题描述：问题描述：N个不同元素按一定的顺序

34、入栈，求不同的出栈序列数目。个不同元素按一定的顺序入栈，求不同的出栈序列数目。【问题分析问题分析】：设设f（n）为）为n个元素的不同出栈序列数目。个元素的不同出栈序列数目。容易得出：容易得出：f（1）=1；f（2）=2。第第n个元素可以第个元素可以第i（1=i=n）个出栈，前面已出栈有）个出栈，前面已出栈有i-1个元素，出栈方个元素，出栈方法：法：f（i-1）；后面出栈）；后面出栈n-i 个元素，出栈方法为：个元素，出栈方法为：f（n-i）。所以有：）。所以有：ni 1i)-f(n *1)-f(iF(n)=三、集合取数问题三、集合取数问题1、设、设f(n,k)是从集合是从集合1，2，。，。，n

35、中能够选择的中能够选择的没有没有两个连续两个连续整数的整数的k个元素子集的数目，求递归式个元素子集的数目，求递归式f(n,k)。【问题分析问题分析】：N有两种情况：有两种情况： 当当n在子集时，则在子集时，则n-1一定不在子集中，即在一定不在子集中，即在1，2，。，。，n-2中选中选k-1个元素，数目为个元素，数目为f(n-2,k-1)。 当当n不在子集中时，则在不在子集中时，则在1，2，。，。，n-1中选中选k个元素，数目为个元素，数目为f(n-1,k)。所以：所以：f(n,k)= f(n-2,k-1) +f(n-1,k)边界条件：边界条件：F(n,1)=n, f(n,k)=0 ( n=k)

36、四、整数划分问题四、整数划分问题 1、将整数、将整数n分成分成k份，且每份不能为空，任意两种分法不能相同份，且每份不能为空，任意两种分法不能相同(不不考虑顺序考虑顺序)。例如：例如：n=7，k=3，下面三种分法被认为是相同的。，下面三种分法被认为是相同的。1，1，5; 1，5，1; 5，1，1;问有多少种不同的分法。问有多少种不同的分法。输入：输入：n，k (6n=200，2=k=2，可以先那出，可以先那出j个个1分到每一分到每一份，然后再把剩下的份，然后再把剩下的i-j分成分成j份即可，分法有：份即可，分法有：f(i-j,j). 2) : j份中至少有一份为份中至少有一份为1的分法，可以先那

37、出一个的分法，可以先那出一个1作为单独的作为单独的1份，剩下份，剩下的的i-1再分成再分成j-1份即可，分法有：份即可，分法有：f(i-1,j-1).所以所以：f(i,j)= f(i-j,j)+ f(i-1,j-1)边界条件：边界条件：f（i，1）=1，f（i，j）=0， （ij）2、自然数、自然数n的拆分方案。的拆分方案。n=5,拆分数拆分数6n=6,拆分数拆分数10n=7,拆分数拆分数141:5=1+42:5=1+1+33:5=1+1+1+24:5=1+1+1+1+15:5=1+2+26:5=2+3nj=2f(n-j,j)+ f(n-1,j-1)用母函数法：用母函数法：当当n=5时：时：构

38、造母函数如下：构造母函数如下：F(x)=(x0+x1+x2+x3+x4+x5)(x20+x21+x22)(x30+x31) (x40+x41)(x50+x51) =(1+x+x2+x3+x4+x5)(1+x2+x4)(1+x3)(1+x4)(1+x5) =1+x+2x2+3x3+5x4+7x5+项项aiXi的系数的系数ai，ai-1即自然数即自然数i的拆分数的拆分数.减减1是因为包含了是因为包含了i=i的一种拆分方案。的一种拆分方案。采用采用a,b,c三个数组，三个数组，a：被乘数，：被乘数，b：乘数，：乘数，c：乘积。：乘积。多个多项式采用逐次相乘的方法。每次借助多个多项式采用逐次相乘的方法

39、。每次借助k从从b中取中取项。项。3、将整数、将整数n分成分成k份，且每份不能为空，且最大值不份，且每份不能为空，且最大值不超过超过m的分法的分法 。任意两种分法不能相同。任意两种分法不能相同(不考虑顺序不考虑顺序)。重复元素的组合问题：重复元素的组合问题： 从从n n种不同的元素中取种不同的元素中取r r个的元素的组合，允个的元素的组合，允许有重复元素的组合：许有重复元素的组合：1rn rC 典型模型：典型模型： r r个相同的小球，放到个相同的小球，放到n n个不同的盒子里，所有个不同的盒子里，所有的放置方法。的放置方法。r个相同的球放入个相同的球放入n个不同的盒子个不同的盒子,条件可以变成条件可以变成:n+r个球放入个球放入n个盒子个盒子,每个盒子最少放每个盒子最少放1个球个球.用插空法用插空法:n+r个球之间有个球之间有n+r-1个空个空,插插n-1个隔板进去个隔板进去,有有C(n-1,n+r-1)=C(r,n+r-1）个组合）个组合结束结束