组合数学在信息学奥赛中的应用课件.ppt

《组合数学在信息学奥赛中的应用课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、组合数学在程序设计中的应用程序设计一直与数学联系得非常的紧密，特别是像组合数学这一分支，与程序设计有着千丝万缕的联系。对于某些题目，我们用正常的做法想法也许无从下手，但是如果我们把题目的全局或者局部与组合数学联系起来，或许就会“柳暗花明又一村”——找到了一种特别独特，特别有效率的数学方法，把无从下手的棘手题变得简单易行。这就是组合数学在程序中的运用。下面使用几个实例说明组合数学在程序中的运用。引言Catalan数定义：一个凸n边形通过不相交于n边形内部的对角线把n边形拆分成若干三角形的不同拆分数。分析设Cn表示凸n边形的拆分方案总数。由题目中的要求可知一个凸n边形的任意一条边

2、都必然是一个三角形的一条边，边P1Pn也不例外，再根据“不在同一直线上的三点可以确定一个三角形”，只要在P2，P3，……，Pn-1点中找一个点Pk(1

3、为，同时考虑到计算的方便，约定边界条件C2=1P1Pn①②③图4P2P3PkPn--1=C(2n,n)/(n+1)具体实现时，若直接用上述公式计算，对数字的精度要求较高。可将其化为递归式再进行递推计算，并且注意类型的定义要用comp型。n个+1，n个-1构成2n项a1,a2,a3,a4,,,,,,a2n其部分和满足a1+a2+......ak(k=1,2,3,...2n)>=0的数列个数。序列a1a2..ak的元素顺序保持不变，按不同结合方式插入合法圆括号对的方案数。n=4(a((bc)d))(a(b(cd)))((ab)(cd))(((ab)c)d)((a(

4、bc))d)一个操作数序列，从1，2，一直到n，栈A的深度大于n。现在可以进行两种操作：1． 将一个数，从操作数列的头端移至栈的头端（对应栈的push操作）2． 将一个数，从栈的头端移至输出序列的尾端（对应栈的pop操作）。使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下表为由123生成序列231的过程。步骤0123456操作数序列1232333栈1211311输出序列2223231你的程序将对给定的n，计算并输出由操作数序列1，2，……，n经过操作可能得到的输出序列总数。一栈(Noip2003普及组第三题)结合定义我们很容易能发现：如果进栈看成1，出栈看成0，

5、在任何一位上累计的“0”的个数不大于累计的“1”的个数，因为必须在栈里有数的情况下才能向外弹数。原题转化为——n个1和n个0组成一个2n位的二进制数，要求从左到右扫描，“0”的累计数不大于“1”的累计数，求满足条件的数有多少。二Littlerooks(SGU222)将k个车摆在n*n的棋盘上，使得任何两个车不能互相攻击（车可以横着或竖着走无限格，不能走斜线）算法描述组合数学：排列与组合由于题目里的棋子是“车”而不是“后”，所以一个棋子不会影响到与其不同行或与其不同列的棋子。结合n皇后问题的方案表示法，我们很容易想到排列组合。排列的定义：设A={a1,a2,a3……an}是n个

6、不同元素的集合，r满足0<=r<=n。任取A中r个元素按顺序排成一列，称为从A中取r个的一个排列。组合的定义：当从n个元素中取出r个而不考虑它的顺序时，称为从n中取r的组合。根据鸽巢原理n>=k，先从简单的情况下手：n=k。此时的公式非常简单：P(n,k)。主要就是对于n>k的情况时的处理。因为每一列最多只能放一颗棋子，所以我们首先把没有棋子的列去掉，再合并成一个n*k的棋盘，结合刚才的数据结构我们能很快知道在这个新棋盘上摆k个棋子还是P(n,k)种方案，再把去掉的(n-k+1)列插入摆棋子的k行中，插入方案总数易得为C(n,k)种。根据乘法原理，总方案数为C(n,k)*P(

7、n,k)种。这样一来程序实现起来就方便多了。错排问题：n个数，分别为1~n，排成一个长度为n的排列。若每一个数的位置都与数的本身不相等，则称这个排列是一个错排。例如，n=3，则错排有231、312。编写程序，求n的错排个数。三错排问题（经典问题）组合数学：递推我们设k个元素的错位全排列的个数记做：W(k)。四个元素的错位排列W(4)我们用穷举法可以找到如下9个：(4，3，2，1)(3，4，1，2)(2，1，4，3)　　(4，1，2，3)(3，4，2，1)(3，1，4，2)　　(4，3，1，2)(2，