实用算法基础教程.pdf

努力就有进步，坚持就能成功 目 录 第一部分 常用算法 第一章 基础题 ………………………………………………………………………1 第二章 枚举法 ……………………………………………………………………15 第三章 不同进制数的转换及应用 ………………………………………………21 第四章 高精度计算 ………………………………………………………………27 第五章 数据排序 …………………………………………………………………32 第六章 排列和组合 ………………………………………………………………44 第七章 递推算法 …………………………………………………………………49 第八章 递归算法 …………………………………………………………………57 第九章 回溯算法 …………………………………………………………………63 第十章 贪心算法 …………………………………………………………………74 第十一章 分治算法策略 …………………………………………………………81 第十二章 深度优先有哪些信誉好的足球投注网站算法 ……………………………………………………89 第十三章 广度优先有哪些信誉好的足球投注网站算法 …………………………………………………101 第十四章 动态规划 ………………………………………………………………112 第一节 动态规划的基本模型 ……………………………………………112 第二节 动态规划与递推 …………………………………………………116 第三节 历届 NOIP 动态规划试题 ………………………………………128 第四节 背包问题…………………………………………………………147 第五节 动态规划应用举例 ………………………………………………158 第十五章 递推关系在竞赛中的应用 ……………………………………………180 第二部分 数据结构 第一章 线性表 …………………………………………………………………189 第二章 指针与链表 ……………………………………………………………191 第三章 栈 ………………………………………………………………………203 第四章 队列 ……………………………………………………………………213 第五章 树 ………………………………………………………………………224 第六章 图 ………………………………………………………………………252 0 努力就有进步，坚持就能成功 第一部分 常用算法 在计算机程序设计中讨论算法的目的则是将其作为编写程序的依据，它是软件设计的基 础。算法的好坏，将影响着软件的质量，因此研究算法对提高软件的质量起着很重要的作用。 本章将就程序设计中常见的典型算法做一些介绍。 第一章 基础题 奥林匹克信息学竞赛十分强调基础知识。每年的分区联赛（NOIP）都含一些直接考核选 手是否会编程的基础题，而每年的全国赛（NOI）、组队赛（CTSC）或国际赛（IOI）对灵活 应用基础知识的要求也愈来愈高。因此，在平日训练中既不要因为畏难而放弃大题难题，更 不要因为轻视而不屑做基础题。自信心和自知之明、夯实基础和破解难题是对立的统一。我 们在做大题难题的时候，为什么效果经常不尽如人意，除了采用算法错误的原因外，更多的 时候是因为细节上的一些瑕疵而导致算法的关键地方时效低下，甚至导致整个算法的时间复 杂度远远高于正常情况，最为严重的后果是导致正确