算法合集之《浅谈数据的合理组织》

浅谈数据的合理组织四川省绵阳南山中学　 何森【摘要】信息学是一门高深的学科，它正在高速的发展。随着信息学的发展，其题目中的关系也变得越来越错宗复杂，给我们解题带来困难。对数据进行合理地组织，正是我们面

浅谈数据的合理组织 四川省绵阳南山中学何森 摘要 【】 信息学是一门高深的学科，它正在高速的发展。随着信息学的发展，其题目 中的关系也变得越来越错宗复杂，给我们解题带来困难。对数据进行合理地组织， 正是我们面对上述题目时的一种有效手段。 本文用几个经典例题从数据的结构和顺序两个方面进行合理组织，达到优化 “” 模型或是提升算法效率的目的。介绍了合理组织数据在信息学中建立模型和优 化算法方面的一些应用，例题包含了动态规划、数据结构、图论类型的题目。目 的在于引起读者对于数据的合理组织的关注，并在今后的解题中能积极并灵活地 运用这一手段。 关键字 【】 组织数据数据结构动态规划图树序列 正文 【】 引言 【】 一个简单的例子： N() 给出个数字数字会比较大，然后给出一些询问，询问一个数字有没有在 N 给出的个数字当中。 当然我们有很多已知的办法： HASHTRIE+…… 表、、预排序二分查找 这些算法都是通过对数据进行合理的组织而起到了减少工作量的作用。 HASHTRIE 不同的是表和是利用数据形式的重新组织，而预排序＋二分查找是 通过对数据顺序的重新组织来达到优化算法的目的的。我们组织数据，主要就是 “”“” 通过从形式和顺序这两个角度来考虑。事实上，这两个方面在实际运用中往 往不是独立的，通常需要联合运用。 我们已经学习了很多经典的数据结构，它们都是合理组织数据的表现。在优 化算法中有很好表现。对数据组织的合理化，不仅在我们设计算法时能起到优化 程序效率的作用，有时，我们在建立解题模型时，合理地组织数据可能给我们提 供新的思考角度，从而优化解题模型，例一就是这样的一个例子。 ［例一］金明的预算方案及其加强版 金明的预算方案 【题意描述】 N(<50000)(<10000) 给出个物品，每个物品都有一个权值和一个价格。我们 称可以直接被购买的物品为主件，称不能被直接购买的物品为附件，附件只有当