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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数学模型及二叉树的应用,什么是数学模型,?,计算机处理的是数,而题目的描述是文字,信息学与数学有什么相似，有什么不同？,思考方法,1,用自己的语言复述问题,这实际上是从自然语言上对信息原型的转化，有利于我们抓住其主要属性；,2,用数学的语言复述问题,我们抓住了信息原型的主要属性，接着用数学语言描述出来。实际上是将信息原型进行抽象，以建立适当的数学模型；,3,联想有关的知识,事实上，当我们用数学语言描述信息原型时，如果所得结果简单明了，可以直接形成算法或构造简单模型。我们就运用机理分析法一来解决了（即一级创造）。如果不行，则需要“联想有关知识”。这实际上是往“一级摹仿”靠近。主要联想的是相似的信息原型或存在关系的已知数学模型。,4,推出有用的事实,如果联想到的知识可以帮我们建立数学模型。那么，我们自然可以套用算法解题了。但进一步延伸下去，也就是达到“二级摹仿”。我们针对该信息原型的特有属性，得出某些“有用”的事实来改进优化模型和算法。,5,大胆的创造,当然，通过以上四步，我们能够较好的建立一个正确高效数学模型就不错了。但通过上述四步，我们很可能在脑海中酝酿着模糊的新模型。不要埋没它，大胆的创造，很有可能建立一种新的具有广泛适用性的模型或一套新的方法体系。这也就是我们所说的“二级创造”。,例题：,NOIP2005,篝火晚会,一共有,n,个同学，编号从,1,到,n,。一开始，同学们按照,1,，,2,，,，,n,的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。佳佳可向同学们下达命令，每一个命令的形式如下：,(b1,b2,.,bm,-1,bm,),这里,m,的值是由佳佳决定的，每次命令,m,的值都可以不同。这个命令的作用是移动编号是,b1,，,b2,，,bm,1,，,bm,的这,m,个同学的位置。要求,b1,换到,b2,的位置上，,b2,换到,b3,的位置上，,，要求,bm,换到,b1,的位置上。执行每个命令都需要一些代价。我们假定如果一个命令要移动,m,个人的位置，那么这个命令的代价就是,m,。我们需要求出最小的代价,这是一个实际问题,怎么找到问题的本质？,置换群？,另一个例题,对于任意一个,0,1,2.N-1,的排列,A0,A1.AN-1,。可以得到它的衍生序列,(Child,array)B,。,其中,B0=0,当,0iN,时，,Bi,=ABi-1,。,比如下列的排列及其衍生序列：,Permutation Child array,0,1,20,0,0,0,2,10,0,0,1,0,20,1,0,1,2,00,1,2,2,0,10,2,1,2,1,00,2,0,而一个排列被称为是完美,(Perfect),的，当且仅当其衍生序列也是一个,0,1,2.N-1,的排列。比如上面的排列,1,2,0,和,2,0,1,。,现在给你一个,0N-1,的排列,P,，他想找到一个完美排列,Q,。使得,P,和,Q,的差异最小。两个排列的差异即为使得,PiQi,的,i,的个数,(0=i0,，任意连续的,Q,个数,0,个结点的集合，根,+,其余结点分为,m=0,个集合，每一个集合本身又是一棵树（子树）,结点的,度：,该结点的子树数目,树的,度：,树中各结点度数的最大值,叶子、父结点、儿子结点、兄弟结点,祖先结点：,从根结点到该结点的路径上所有结点,层次、高度：,根为,1,依次往下数,有序树：,规定所有结点的儿子结点次序,，,否则为,无序树,森林：,m=0,棵互不相交树的集合,其它表示方法：,1.(A(B(L,E),C(F),D(G(I),H),2.,类似于书籍的目录表示法。,高度定义为层数或层数,1,，都可以；本书定义为层数。,A,B,C,D,E,F,G,H,I,L,高度为 4、度为 3 的树,例：结点总数为,3,时的所有二叉树的树的形状,二叉树的定义,空或有一个根，根有左子树、右子树；而左右子树本身又是二叉树。,和树的区别,：可为空,左右子树有序，不可颠倒,B,C,D,E,F,L,例：,二叉树,二叉树的性质,性质,1,：在二叉树的第,i,层上至多有 2,i-1,个结点,B,C,D,E,F,L,A,1,层：结点个数,2,1-1,=2,0,个,2,层：结点个数,2,2-1,=2,1,个,3,层：结点个数,2,3-1,=2,2,个,证：,k=1,时成立，设,k=i-1,时成立 则当,k=i,时,在二叉树的第,i,层上至多有,2,i-1-1,*2=2,i-1,个结点,性质,2,：高度为,k,的,二叉树至多有,2,k,-1,个结点,证：利用性质,1,，将第,1,层至第,k,层的最多的结点数进行相加：,1+2+2,2,+2,k-2,+2,k-1,=2,k,-1,性质,3,：二叉树的叶子结点数,n0,等于度为 2 的结点数,n2+1,证：设度为,1,的结点数为,n1,，,树枝的总数为,B,则：,B=n-1=n0+n1+n2-1,又,B=n1+2n2,；,原命题得证。,C,E,F,L,A,完全二叉树,B,C,D,E,F,L,A,P,S,Q,R,U,B,C,D,E,F,L,A,P,S,Q,R,X,U,W,V,满二叉树,:,每层结点,数最多,完全二叉树,:,1,、满二叉树,2,、从满二叉树最底层从右向左依次去掉若干结点形成的,性质,4,：具有,n,个结点的完全二叉树高度为,log,2,n +1,证：根据性质,2,和完全二叉树的定义：设其高度为,k,2,k-1,-1 n=2,k,-1,2,k-1,n+1=2,k,2,k-1,=n 2,k,故：,k-1=log,2,n k;,原命题得证。,完全二叉树,B,C,D,E,F,L,A,P,S,Q,R,U,性质,5,：对一棵有,n,个结点的完全二叉树按照从第一层（根所在的层次,到最后一层，并且,每一层都按照从左到右的次序进行编号。根结点的编号为,1,，最后一个结点的编号,为,n,。,1,：,对任何一个编号为,i,的结点而言，它的左儿子的编号为,2i(,若,2i=n),而右儿子的 编号为,2i+1(,若,2i+1 key,和树根关键字,t-key,进行比较，若,s-key=t-key,则无须插入，若,s-keykey,则插入到根的左子树中，若,s-keyt-key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点*,s,作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。,3.,二叉排序树的查找,:,在当前二叉排序树上找到某特定元素。,思考：怎么利用二叉排序树的性质加快查找？,4.,二叉排序树的应用,:,查找当前第,K,大元素,查询某元素在当前所有元素中的排名,堆,一个顺序存储的完全二叉树，如果任何一个结点的值都不小于或不大于它左右子树（如果有的话）中所有结点的值，那么这个顺序存储的序列就是堆。这个二叉树的根被称为堆顶，最后一层最右端的叶子结点称为堆底。,由于堆是一个顺序存储的完全二叉树，所以一个长度是,n,的序列要成为一个堆，必须存储在容量是,n+1,的顺序表中，其中,0,号单元不用。,堆顶,r1,是整个序列的最大值或者最小值。堆顶是最大值的堆被称为大顶堆或者极大堆；堆顶是最小值的堆被称为小顶堆或者极小堆。,怎么建堆？,自底向上调整？,堆排序,【,堆排序的基本思想,】,首先将一个序列构建成堆；然后将堆顶与堆底交换，再去掉堆底，剩余的序列可能不是堆，将它再调整成堆，再将堆顶与堆底交换。如此重复直到堆只有一个结点为止。,【,需要解决的问题,】,如何将一个替换掉堆顶的堆重新调整成堆？,一个完全二叉树，根的左右子树都是堆，而整棵二叉树不是堆。问如何将这棵二叉树调整成堆。,堆的应用,NOIP2004,合并果子等,