资源描述：
《离散数学在信息学竞赛中的运用ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、离散数学在信息学竞赛中的运用YellowVigorousPine目录重集全排列Catalan数简单数论矩阵的简单运用棋盘多项式与任务分配置换群与pólya定理重集全排列一般我们认为排列或组合的元素必须两两相异，现取消这一限制。例如一个排列可以是aaaaabbbbbaaaabbbb等等，一个组合可以只{a，a，b，b}。对于重集S＝{p1a1,p2a2……pkak}，其中pi表示ai在集合中的个数。那么这个重集的全排列个数是(∑Pi)!/∏(Pi!)，其中(i=1tok)。字符串序号字符串acab含有两个a,一个b,一个
2、c,和acab含的字母和每个字母的个数都相等的字符串还有：aacb,baca等，因为他们也是含有两个a,一个b,一个c。所有满足这个性质的字符串按字典顺序排列后，acab是第5个，我们就说acab的序号是5.再如：ba的序号是2,aa的序号是1.编程求出给定字符串S（长度<=100）的序号P（保证<=30000）注意：字符串只含小写字母。本题可以逐位利用重集全排列的公式，计算出解。飞行问题在n×m×k一只飞蛾从空间上的(0,0,0)点飞到(n,m,k)点，规定飞蛾每次只能向右，向前，向下飞行一单位距离，问飞蛾有多少种不
3、同的路径可以飞到终点。向右飞行计为a，向前计为b，向下计为c。那么每一个飞行过程就对应着一个多个a多个b多个c的排列，反之也对应。而a有n个，b有m个，c有k个。所以这些字母全排列的个数对应着飞行路径的个数－(m+n+k)!/m!n!k!。Catalan数堆栈问题栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。考虑这样一个问题：一个操作数序列，从1，2，一直到n（图示为1到3的情况），栈A的深度大于n。Catalan数现在可以进行两种操作：1.将一个数，从操作数序列的头端移到栈的头端（
4、对应数据结构栈的push操作）2.将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作）使用这两种操作，由一个操作数序列就可以得到一系列的输出序列。例如12345为初始序列，经过进栈，出栈，进栈，进栈，进栈，出栈，进栈，出栈，出栈操作后，序列变为了14532Catalan数试问一个序列1……n经过堆栈处理之后，有多少种出栈序列。要知道这个问题如何解决，先将这个问题的模型转换一下。进栈时，我们在纸上画一个左括号，出栈时，画一个右括号。这样就把整个进栈出栈的过程转化成了一个括号序列。而且任何一个进栈出栈的过程
5、都对应着唯一的括号序列。Catalan数好括号列的定义：（1）空列是好括号列。（2）若A和B是好括号列，则AB是好括号列。（3）若A是好括号列，（A）是好括号列。由好括号的定义可知，任何一个进栈出栈过程转化成的括号序列都是好括号列。那么任何一个好括号列也对应着一个唯一的进栈出栈过程。计算出长度为n（n为完整括号个数，一个左括号加上一个右括号算作一个完整括号）的好括号列的个数也就是计算出了堆栈问题的答案。经过数学证明，长度为n的好括号列的个数是C（n）＝C(2n,n)-C(2n,n-1)=C(2n,n)/(n+1)。这个
6、数被称为Catalan数(卡特兰数)。Catalan数考虑新X1×X2×X3……×Xn，对这个乘式加括号搞结合律，则共加n-1个括号，那么添加括号的方案数是C(n－1)种。若最后一次乘法是(X1,X2……Xk)×(Xk+1,Xk+2……Xn)，那么组合方式也是相乘的(乘法原理)，设前k个元素的填括号方式有a(k)种，后面的n-k个元素有a(n－k)种，则a(n)=∑a(k)×a(n-k)，其中k＝1ton-1，a1=1。这就是Catalan数的递推公式。由上述的递推公式可以知道，包含n个结点的二叉树有C(n)棵。小结可
7、以运用Catalan数的地方：设圆周上2n个点，用n条彼此在圆内部无公共交点的弦连接这些点，共有C（n）种连接方式。在n×n的矩阵中，从(0,0)点走到(n,n)点，规定只能向下或向右走，且不能穿过左上到右下的对角线，共有C(n)种走的方式。填括号问题进栈出栈问题结点数是n的二叉树的个数数论这里简要介绍一些实用的数论算法。求最大公约数(欧几里德算法)Functiongcd(a,b:longint):longint;Beginifamodb=0thengcd:=belsegcd:=gcd(b,amodb);End;这里，
8、调用gcd(a,b)函数可以求出a和b的最大公约数。欧几里德算法狼找兔子一座山周围有n个洞，顺时针编号为0,1,2,…n-1。而一只狼从0号洞开始，顺时针方向计数，每遇到m个洞就进洞找兔子。例如n=5，m=3，狼经过的洞依次为0,3,1,4,2,0。输入n和m。试问兔子有没有幸免的机会，如果有，该藏在哪儿？狼找兔子不妨让兔子躲在1
