算法与数据结构-实用算法基础教程

《算法与数据结构-实用算法基础教程》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、努力就有进步，坚持就能成功目录第一部分常用算法第一章基础题………………………………………………………………………1第二章枚举法……………………………………………………………………15第三章不同进制数的转换及应用………………………………………………21第四章高精度计算………………………………………………………………27第五章数据排序…………………………………………………………………32第六章排列和组合………………………………………………………………44第七章递推算法…………………………………………………………………49第八章递归算法…………………………………………………………………57第九章

2、回溯算法…………………………………………………………………63第十章贪心算法…………………………………………………………………74第十一章分治算法策略…………………………………………………………81第十二章深度优先搜索算法……………………………………………………89第十三章广度优先搜索算法…………………………………………………101第十四章动态规划………………………………………………………………112第一节动态规划的基本模型……………………………………………112第二节动态规划与递推…………………………………………………116第三节历届NOIP动态规划试题………………………………………12

3、8第四节背包问题…………………………………………………………147第五节动态规划应用举例………………………………………………158第十五章递推关系在竞赛中的应用……………………………………………180第二部分数据结构第一章线性表…………………………………………………………………189第二章指针与链表……………………………………………………………191第三章栈………………………………………………………………………203第四章队列……………………………………………………………………213第五章树………………………………………………………………………224第六章图…………………………………………

4、……………………………2520努力就有进步，坚持就能成功第一部分常用算法在计算机程序设计中讨论算法的目的则是将其作为编写程序的依据，它是软件设计的基础。算法的好坏，将影响着软件的质量，因此研究算法对提高软件的质量起着很重要的作用。本章将就程序设计中常见的典型算法做一些介绍。第一章基础题奥林匹克信息学竞赛十分强调基础知识。每年的分区联赛（NOIP）都含一些直接考核选手是否会编程的基础题，而每年的全国赛（NOI）、组队赛（CTSC）或国际赛（IOI）对灵活应用基础知识的要求也愈来愈高。因此，在平日训练中既不要因为畏难而放弃大题难题，更不要因为轻视而不屑做基础题。自信心和自知之明、夯实基础和破解

5、难题是对立的统一。我们在做大题难题的时候，为什么效果经常不尽如人意，除了采用算法错误的原因外，更多的时候是因为细节上的一些瑕疵而导致算法的关键地方时效低下，甚至导致整个算法的时间复杂度远远高于正常情况，最为严重的后果是导致正确的算法无法实现。出现“因小失大，功亏一簧”的主观原因是好高骛远、轻视基础。因此我们应该注意从小题、中题练起，积累经验，强化内功，夯实基础。【例1】计算多项式23iixxxx-10设多项式exp(x)=1+x+++……+(≤10)2!3!i!i!输入x输出exp(x)的值（保留小数点后四位）题解设s—和；t—当前项；i—x的幂次。即s=t0+t1+t2+……+ti1.确

6、定重复条件abs（t）>1e-10；2.确定重复体i-1xxx由ti=*=ti-1*得出重复体(i-1)!iii←i+1；xt←t*；is←s+t；1努力就有进步，坚持就能成功3.设定初值i←0；t←1；s←1；由此得出程序：vari，X：integer；{x的幂次和自变量}t，s：real；{当前项和多项式的值}beginreadln(x)；{读自变量的值}i：=0；t：=1；s：=1；{赋初值}whileabs(t)>1e-10do{若当前项未达到精度要求，则新增一项}begini：=i+1；t：=t*x/i；s：=s+t；end；{while}writeln(’EXP(’，X，’)=

7、’，S：0：4)；{输出多项式的值}readln；END.{main}【例2】计算灯的开关状态有N个灯放在一排，从1到N依次顺序编号。有N个人也从1到N依次编号。1号将灯全部关闭，2将凡是2的倍数的灯打开；3号将凡是3的倍数的灯作相反处理(该灯如为打开的，则将它关闭；如关闭的，则将它打开)。以后的人都和3号一样，将凡是自己编号倍数的灯作相反处理。试计算第N个操作后，哪几盏灯是点亮的。(0-表示灯打开1-表示灯关闭)题解设