组合数学在程序设计中的应用1

《组合数学在程序设计中的应用1》由会员分享，可在线阅读，更多相关《组合数学在程序设计中的应用1（16页珍藏版）》请在金锄头文库上搜索。

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

2、一个凸n边形的任意一条边都必然是一个三角形的一条边 ，边P1 Pn也不例外，再根据“不在同一直线上的三点可以 确定一个三角形”，只要在P2，P3，Pn-1点中找一 个点Pk(1=0的数列个 数。 序列a1a2ak的元素顺序保持不变，按不同 结合方式插入合法圆括号对的方案数。 n=4 (a(bc)d) (a(b(cd) (ab)(cd) (ab)c)d) (a(bc)d) 一个操作数序列，从1，2，一直到n，栈A的深度大于n。现在可以进行两种 操作：1 将一个数，从操作数列的头端移至栈的头端（对应栈的push操作）2 将一个数，从栈的头端移至输出序列的尾端（对应栈的pop操作）。 使用这两种操作

3、，由一个操作数序列就可以得到一系列的输出序列，下表为 由1 2 3 生成序列2 3 1 的过程。步骤0123456操作数 序列1232333 栈 1211311 输出序 列2223231你的程序将对给定的n，计算并输出由操作数序列1，2，n经过操作可能得到 的输出序列总数。一 栈(Noip2003 普及组第三题)结合定义我们很容易能发现：如果进栈看成1，出栈看成0，在 任何一位上累计的“0”的个数不大于累计的“1”的个数，因为必须 在栈里有数的情况下才能向外弹数。原题转化为n个1和n个0组成一个2n位的二进制数，要求从 左到右扫描，“0”的累计数不大于“1”的累计数，求满足条件的 数有多少。二

4、 Little rooks(SGU 222)将k个车摆在n*n的棋盘上，使得任何两个车不能互相 攻击（车可以横着或竖着走无限格，不能走斜线） 算法描述 组合数学：排列与组合由于题目里的棋子是“车”而不是“后”，所以一个棋子不会影 响到与其不同行或与其不同列的棋子。结合n皇后问题的方 案表示法，我们很容易想到排列组合。排列的定义：设A=a1,a2,a3an是n个不同元素的集合 ，r满足0=k，先从简单的情况下手：n=k。此 时的公式非常简单：P(n,k)。主要就是对于nk的情 况时的处理。因为每一列最多只能放一颗棋子，所以我们首先把没 有棋子的列去掉，再合并成一个n*k的棋盘，结合刚才 的数据结

5、构我们能很快知道在这个新棋盘上摆k个棋子 还是P( n , k )种方案，再把去掉的(n-k+1)列插入摆棋子 的k行中，插入方案总数易得为C( n , k )种。根据乘法原理，总方案数为C( n , k ) * P( n , k )种。这 样一来程序实现起来就方便多了。错排问题：n个数，分别为1n，排成一个长 度为n的排列。若每一个数的位置都与数的本 身不相等，则称这个排列是一个错排。例如， n=3，则错排有2 3 1、3 1 2。编写程序，求n的 错排个数。三 错排问题（经典问题）组合数学：递推我们设k个元素的错位全排列的个数记做：W(k)。四个元素的错位排列W(4)我们用穷举法可以找 到

6、如下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，4，1，3)(2，3，4，1)它们有什么规律呢？通过反复的试验，我们发现事实上有两种方式产生错位排列：A.将k与(1，2，k1)的某一个数互换，其他k2个数进 行错排，这样可以得到(k1)W(k-2)个错位排列。B.另一部分是将前k1个元素的每一个错位排列（有W(k- 1)个）中的每一个数与k互换，这样可以得到剩下的(k 1)W(k-1) 个错位排列。根据加法原理，我们得到求错位排列的递推公式W(k):W(k) = (k1) * W(k1)+W(k2)结论 其实视野看得发散一些，扩展一些，能融入程序设计的知 识点不仅限于组合数学，还有拓扑学，微积分，计算几何 甚至是物理，化学。这样跨学科的融合相信能给信息 学计算机这门学科焕发新的光彩。 从上述题我们能发现一个共同特点，也就是将组合数学融 入题目中，简单而又快速的解决题目。它说明：程序设计 不一定是拿着现成的思路或算法去生搬硬套，也许我们换 个角度，换个思路，或者进行数学建模与变换，将组合数 学里的一些结论，定理，性质与程序结合起来，达到事半 功倍的效果。当然，要熟练的掌握这方面的技能与技巧还 是在乎于我们平常的多看多想多练。