算法合集之数据联系简化.ppt

数据关系的简化;坐船问题 雅礼中学有n个学生去公园划船。一条船最多可以坐两个人。如果某两个学生同姓或者同名就可以坐在一条船上。 学校希望每个同学都坐上船，同时学校想要租用最少的船。请问：学校至少要租多少船？;伍昱;伍昱 伍平 何林 何刚 黄刚 何凡;树的构造;树的构造;树的构造;树的构造;树的构造;树的构造;树的匹配;树的匹配;树的匹配;树的匹配;树的匹配;每次让两个人坐上一条船 树始终保持连通 假设树中有n个点，[(n+1)/2]条船即可容纳所有人。 这无疑是最优解。;设森林中有m棵树，所有树的规模是n1, n2, …, nm。 对每棵树分别处理。 答案是∑(i=1..m)[(ni+1)/2];图--树小结;树的统计 一棵树含有n个节点。 节点编号为1, 2, 3, …, n。 定义t(v)为v的后代中所有编号小于v的节点个数。 求t(1), t(2), t(3), …, t(n)。;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性;树--线性 小结;图?树，树?序列。 有时候不需要包罗万象的所有信息 合理的组织数据之间的关系 利用简化数据关系实现数据的有序化 简化后的关系更明了，有利于窥见本质矛盾。;谢谢！