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

数学模型及二叉树的应用 什么是数学模型 计算机处理的是数而题目的描述是文字信息学与数学有什么相似 有什么不同 思考方法 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 的排列A 0 A 1 A N 1 可以得到它的衍生序列 Childarray B 其中B 0 0 当0 i N时 B i A B i 1 比如下列的排列及其衍生序列 PermutationChildarray 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 现在给你一个0 N 1的排列P 他想找到一个完美排列Q 使得P和Q的差异最小 两个排列的差异即为使得P i Q i 的i的个数 0 i N 问题看起来很复杂 怎么分析 还是置换群 两道看起来风马牛不相及的题 最终都可以化归到群论 这就是数学模型 例题3 构造一个长度为N的数列 An 满足任意连续的P个数 0 任意连续的Q个数 0 例如N 5 P 2 Q 3 则 23 23 2是满足条件的一个数列 题目本身似乎就已经有了模型 但怎么解题呢 定义Si A1 A2 Ai S0 0列出Si之间的不等关系 再建立一个图论模型 使用拓扑排序求解 二叉树 树和森林 树 n 0个结点的集合 根 其余结点分为m 0个集合 每一个集合本身又是一棵树 子树 结点的度 该结点的子树数目树的度 树中各结点度数的最大值叶子 父结点 儿子结点 兄弟结点祖先结点 从根结点到该结点的路径上所有结点层次 高度 根为1 依次往下数有序树 规定所有结点的儿子结点次序 否则为无序树森林 m 0棵互不相交树的集合 其它表示方法 1 A B L E C F D G I H 2 类似于书籍的目录表示法 高度定义为层数或层数 1 都可以 本书定义为层数 二叉树的定义 空或有一个根 根有左子树 右子树 而左右子树本身又是二叉树 和树的区别 可为空左右子树有序 不可颠倒 二叉树的性质 性质1 在二叉树的第i层上至多有2i 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层上至多有2i 1 1 2 2i 1个结点 性质3 二叉树的叶子结点数n0等于度为2的结点数n2 1 证 设度为1的结点数为n1 树枝的总数为B则 B n 1 n0 n1 n2 1又B n1 2 n2 原命题得证 完全二叉树 完全二叉树 1 满二叉树2 从满二叉树最底层从右向左依次去掉若干结点形成的 性质4 具有n个结点的完全二叉树高度为log2n 1 证 根据性质2和完全二叉树的定义 设其高度为k2k 1 1 n 2k 12k 1 n 1 2k2k 1 n 2k故 k 1 log2n 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 n 2 对任何一个编号为j的结点而言 它的父亲结点的的编号为j 2 根结点无父结点 证 对编号归纳 12 11 10 9 8 7 6 5 4 3 2 1 二叉树的顺序存储 一般情况 应用范围 适用于二叉树上的结点个数已知 或不支持动态存储分配的高级语言 二叉树的顺序存储 特殊情况 完全二叉树 A23B45C67D89E100F00G00H00I00L00 012345678910 right left data 应用范围 适用于完全二叉树 且结点个数已知 D C G E F B A H I L ABCDEFGHI 0123456789 L 二叉树的链接存储 仅定义结点的类型即可 结点之间的关系通过指针实现 dataleftright 标准形式 二叉链表 广义标准形式 三叉链表 dataleftrightParent 二叉树的链接存储 例 二叉树遍历 设N代表根节点 L代表左子树 R代表右子树 a 前序 或先序 如果二叉树为空 则操作为空 否则访问根结点 前序遍历左子树 前序遍历右子树 记为 NLR b 中序 如果二叉树为空 则操作为空 否则中序遍历左子树 访问根结点 中序遍历右子树 记为 LNR c 后序 如果二叉树为空 则操作为空 否则后序遍历左子树 后序遍历右子树 访问根结点 记为 LRN 前序 A L B E C D W X 中序 B L E A C W X D 后序 B E L X W D C A 二叉树的确定 前序 后序 中序唯一确定一棵二叉树例 前序 A B D E F C中序 D B E F A C 1 二叉排序树的概念 二叉排序树是一种动态树表 二叉排序树的定义 二叉排序树或者是一棵空树 或者是一棵具有如下性质的二叉树 若它的左子树非空 则左子树上所有结点的值均小于根结点的值 若它的右子树非空 则右子树上所有结点的值均大于根结点的值 左 右子树本身又各是一棵二叉排序树 二叉排序树的性质 按中序遍历二叉排序树 所得到的中序遍历序列是一个递增有序序列 二叉排序树 2 二叉排序树的插入 在二叉排序树中插入新结点 要保证插入后的二叉树仍符合二叉排序树的定义 插入过程 若二叉排序树为空 则待插入结点 S作为根结点插入到空树中 当非空时 将待插结点关键字S key和树根关键字t key进行比较 若s key t key 则无须插入 若s keykey 则插入到根的左子树中 若s key t key 则插入到根的右子树中 而子树中的插入过程和在树中的插入过程相同 如此进行下去 直到把结点 s作为一个新的树叶插入到二叉排序树中 或者直到发现树已有相同关键字的结点为止 3 二叉排序树的查找 在当前二叉排序树上找到某特定元素 思考 怎么利用二叉排序树的性质加快查找 4 二叉排序树的应用 查找当前第K大元素查询某元素在当前所有元素中的排名 堆 一个顺序存储的完全二叉树 如果任何一个结点的值都不小于或不大于它左右子树 如果有的话 中所有结点的值 那么这个顺序存储的序列就是堆 这个二叉树的根被称为堆顶 最后一层最右端的叶子结点称为堆底 由于堆是一个顺序存储的完全二叉树 所以一个长度是n的序列要成为一个堆 必须存储在容量是n 1的顺序表中 其中0号单元不用 堆顶r 1 是整个序列的最大值或者最小值 堆顶是最大值的堆被称为大顶堆或者极大堆 堆顶是最小值的堆被称为小顶堆或