noip数学模型及二叉树的应用

1、数学模型及二叉树的应用,什么是数学模型?,计算机处理的是数 而题目的描述是文字 信息学与数学有什么相似，有什么不同？,思考方法,1用自己的语言复述问题 这实际上是从自然语言上对信息原型的转化，有利于我们抓住其主要属性；,2用数学的语言复述问题 我们抓住了信息原型的主要属性，接着用数学语言描述出来。实际上是将信息原型进行抽象，以建立适当的数学模型；,3联想有关的知识 事实上，当我们用数学语言描述信息原型时，如果所得结果简单明了，可以直接形成算法或构造简单模型。我们就运用机理分析法一来解决了（即一级创造）。如果不行，则需要“联想有关知识”。这实际上是往“一级摹仿”靠近。主要联想的是相似的信息原型或

2、存在关系的已知数学模型。,4推出有用的事实 如果联想到的知识可以帮我们建立数学模型。那么，我们自然可以套用算法解题了。但进一步延伸下去，也就是达到“二级摹仿”。我们针对该信息原型的特有属性，得出某些“有用”的事实来改进优化模型和算法。,5大胆的创造 当然，通过以上四步，我们能够较好的建立一个正确高效数学模型就不错了。但通过上述四步，我们很可能在脑海中酝酿着模糊的新模型。不要埋没它，大胆的创造，很有可能建立一种新的具有广泛适用性的模型或一套新的方法体系。这也就是我们所说的“二级创造”。,例题：NOIP2005篝火晚会,一共有n个同学，编号从1到n。一开始，同学们按照1，2，n的顺序坐成一圈，而实

3、际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。 佳佳可向同学们下达命令，每一个命令的形式如下： (b1, b2,. bm -1, bm) 这里m的值是由佳佳决定的，每次命令m的值都可以不同。这个命令的作用是移动编号是b1，b2， bm 1，bm的这m个同学的位置。要求b1换到b2的位置上，b2换到b3的位置上，要求bm换到b1的位置上。 执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置，那么这个命令的代价就是m。我们需要求出最小的代价,这是一个实际问题 怎么找到问题的本质？ 置换群？,另一个例题

4、,对于任意一个0,1,2.N-1的排列A0,A1.AN-1。可以得到它的衍生序列(Child array)B。 其中B0=0,当0iN时，Bi = ABi-1。 比如下列的排列及其衍生序列： Permutation Child array 0, 1, 2 0, 0, 0 0, 2, 1 0, 0, 0 1, 0, 2 0, 1, 0 1, 2, 0 0, 1, 2 2, 0, 1 0, 2, 1 2, 1, 0 0, 2, 0 而一个排列被称为是完美(Perfect)的，当且仅当其衍生序列也是一个0,1,2.N-1的排列。比如上面的排列1, 2, 0和2, 0, 1 。 现在给你一个0N-1的

5、排列P，他想找到一个完美排列Q。使得P和Q的差异最小。两个排列的差异即为使得PiQi的i的个数(0= 0 个集合，每一个集合本身又是一棵树（子树） 结点的度：该结点的子树数目 树的度：树中各结点度数的最大值 叶子、父结点、儿子结点、兄弟结点 祖先结点：从根结点到该结点的路径上所有结点 层次、高度：根为1, 依次往下数 有序树：规定所有结点的儿子结点次序，否则为无序树 森林： m = 0 棵互不相交树的集合,其它表示方法： 1. ( A(B(L,E),C(F),D(G(I),H) 2. 类似于书籍的目录表示法。 高度定义为层数或层数1，都可以；本书定义为层数。,二叉树的定义,空或有一个根，根有左

6、子树、右子树；而左右子树本身又是二叉树。 和树的区别：可为空 左右子树有序，不可颠倒,二叉树的性质,性质1：在二叉树的第 i 层上至多有 2 i-1个结点,B,C,D,E,F,L,A,1层：结点个数 21-1=20 个 2层：结点个数 22-1=21 个 3层：结点个数 23-1=22 个,证：k = 1 时成立，设 k = i-1 时成立 则当 k = i 时在二叉树的第 i 层上至多有 2 i-1-1 * 2 = 2 i-1 个结点,性质3：二叉树的叶子结点数 n0 等于度为 2 的结点数 n2 + 1,证：设度为 1 的结点数为 n1，树枝的总数为 B 则：B = n-1=n0+n1+n

7、2-1 又 B = n1+2n2； 原命题得证。,完全二叉树,完全二叉树: 1、满二叉树 2、从满二叉树最底层从右向左依次去掉若干结点形成的,性质4：具有 n 个结点的完全二叉树高度为 log2n + 1,证：根据性质 2 和完全二叉树的定义：设其高度为 k 2k-1-1 n = 2k -1 2k-1 n + 1 = 2k 2k-1 = n 2k 故：k-1 = log2n k ; 原命题得证。,完全二叉树,B,C,D,E,F,L,A,P,S,Q,R,U,性质5：对一棵有 n 个结点的完全二叉树按照从第一层（根所在的层次到最后一层，并且 每一层都按照从左到右的次序进行编号。根结点的编号为 1，

8、最后一个结点的编号 为 n。 1：对任何一个编号为 i 的结点而言，它的左儿子的编号为 2i( 若 2i key进行比较， 若s-key = t-key,则无须插入，若s-keykey,则插入到根的左子树中， 若s-keyt-key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同， 如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。,3.二叉排序树的查找: 在当前二叉排序树上找到某特定元素。 思考：怎么利用二叉排序树的性质加快查找？,4.二叉排序树的应用: 查找当前第K大元素 查询某元素在当前所有元素中的排名,堆,一个顺序存储的完全二叉树，如果任何一个结点的值都不小于或不大于它左右子树（如果有的话）中所有结点的值，那么这个顺序存储的序列就是堆。这个二叉树的根被称为堆顶，最后一层最右端的叶子结点称为堆底。 由于堆是一个顺序存储的完全二叉树，所以一个长度是n的序列要成为一个堆，必须存储在容量是n+1的顺序表中，其中0号单元不用。 堆顶r1是整个序列的最大值或者最小值。堆顶是最大值的堆被称为大顶堆或者极大堆；堆顶是最小值的堆被称为小顶堆或者极小堆。,怎么建堆？,自底向上调整？,堆排序,【堆排序的基本思想】 首先将一个序列构建成堆；然后将堆顶与堆底交换，再去掉堆