信息竞赛中的简单数学类问题及其数学构造方法.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 我们设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，4，1，3)(2，3，4，1) 它们有什么规律呢？ 分析 通过反复的试验，我们发现事实上有两种方式产生错位排列： ?A.将k与(1，2，…，k－1)的某一个数互换，其他k－2个数进行错排，这样可以得到(k－1)×W(k-2)个错位排列。 ?B.另一部分是将前k－1个元素的每一个错位排列（有W(k-1)个）中的每一个数与k互换，这样可以得到剩下的(k－1)×W(k-1) 个错位排列。 根据加法原理，我们得到求错位排列的递推公式W(k): W(k) = (k–1) * [W(k–1)+W(k–2)] 分析 构造法 “构造法”解题，就是构造数学模型解决问题。包括直接构造问题解答的模型，图论模型，网络流模型以及组合数学模型。 构造法解题的思路或步骤 构造法解题的类型： 直接构造问题解答。这只是构造法运用的一种简单类型。它只能针对问题本身，探索其独有性质，不具备可推广性。 数学建模。通过沿用经典的数学思想建立起模型；或者提取现实世界中的有效信息，用简明的方式表达其规律，这种规律可以是一条代数公式、一幅几何图形，一个物理原理、一个化学方程式，等等。 无论是直接构造问题解答还是构造数学模型，都要通过算法实现。如何设计一个有较低编程复杂度和时空复杂度且结构清晰的算法，十分重要。通常考虑的因素有 选择的模型必须尽量多地体现问题的本质特征。但这并不意味着模型越复杂越好，累赘的信息会影响算法的效率。 模型的建立不是一个一蹴而就的过程，而是要经过反复地检验、修改，在实践中不断完善。 数学模型通常有严格的格式，但程序编写形式可不拘一格。 利用数学方法进行构造 例1：求Fibonacci数列 定义：f0=f1=1, fn=fn-1+fn-2(n=2)。{fi}称为Fibonacci数列。 输入n，求fn mod q。其中1=q=30000。n=109 【解题分析】 简单的模拟显然不能满足题目的要求，我们考虑构造解答。 定义矩阵 0 1 1 1 为A, 发现（x,y）×A=(y,x+y),恰好与 数列性质相似 。 于是有，? 有(1,1)×A=(1,2), （Fi,Fi+1）×A=(Fi+1,Fi+Fi+1)=(Fi+1,Fi+2) , 即(1,1)×An=(Fn,Fn+1) 在㏒(n)的时间内即可出解。 ? 例题2： 毛毛虫是含N个节点的一棵树，它包含一条主链，所有点要么在链上，要么和主链上某点相邻。我们希望给毛毛虫的每个顶点标号1,2,3,…,N，使得所有边的两端节点标号差的绝对值恰好包含了1,2,3,…,N-1，每个数正好一次（N=10000）。 8 1 5 2 9 48 6 3 7 2 6 3 5 8 1 4 7 这个题目初看上去，似乎无从下手。由于题目中所给的这种特殊的树以及顶点标号的约束条件都是我们以前没有见到过的，再加上数据的规模很大，最大可以达到N=10000。使得我们不得不朝着贪心或者构造的方向去思考。 首先观察样例，再进行了一些尝试后，我们找到了对于样例的很多种合法的标号，其中有一种引起了我们的注意，如下图所示: 1 9 2 3 4 8 7 6 5 1 2 3 4 5 6 7 8 很容易发现，图中边的权值，也就是边的两端顶点标号差的绝对值，是从左向右依次递减的。这个发现使我们不由得想到，是不是对于所有的毛毛虫都存在一种这样的合法标号方式。 例题分析 一序列（见文本） 利用图论模型进行构造 例题3：圆桌吃饭问题 n个人围着一张圆桌吃饭，每个人都不愿意两天与同一人为邻，问最多能坐多少天，并给出一种排列方案？ 转化为图论模型 设G=(V,E)为一完全图，|V|=n。图中的每个顶点代表一个人，连结顶点的边表示人之间的相邻关系。因此，每种围绕圆桌的吃饭方案就成为图中的一条哈密尔顿回路。设L=v1,v2,…,vn为G中的一条哈密尔顿回路，其中所含的边的集合记为e(L)。问题转化为： 求m与L1,L2,…,Lm，使得e(Li)∩e(Lj)=φ， 并且m达到最大值。 构造方法 作一圆，把圆周分成n-1等分，标上n-1