东北师范大学研究生课程—算法与程序设计

1、算法与程序设计硕士学位课程教材系列算法与程序设计Algorithm and Program Design目录目录········································

2、3;····························02课程信息····················

3、3;············································03专题一 信息学竞赛简介与算法基础··

4、3;······································06专题二 数制转换与高精度计算·········

5、····································22专题三 字符串基础············&

6、#183;··········································41专题四 查找算法·····

7、83;·················································

8、83;·53专题五 排序算法···············································

9、;··········68专题六 递归算法······································&

10、#183;··················89专题七 贪心算法·····························

11、83;··························117专题八 图论······················

12、······································130专题九 动态规划··········&

13、#183;·············································145专题十 模拟算法··&#

14、183;·················································&#

15、183;····167阅读文献············································&

16、#183;···················196课程信息【课程性质】专业必修课【课程学分】2学分。【教学目标】这是为教育硕士开设的一门专业课程，其主要目标旨在使学生进一步体验算法思想，了解算法和程序设计在解决问题过程中的地位和作用；能从简单问题出发，设计解决问题的算法，并能初步使用一种程序设计语言编制程序，实现算法解决问题，能够胜任中小学计算机竞赛的培训。具体的教学目标包括：1. 知识与技能（1）理解

17、算法、程序、语言等内涵及其相互关系。（2）了解顺序、选择、循环三种基本结构及其重要作用。（3）掌握计算机程序的基本概念，能解释计算机程序执行的基本过程。（4）了解程序设计语言、编辑程序、编译程序、连接程序以及程序开发环境等基本知识。（5）了解面向对象与软件工程的基本思想。 2. 过程与方法（1）结合实例，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程，认识算法和程序设计在其中的地位和作用。（2）掌握用自然语言、流程图或伪代码等方法描述算法的过程。（3）通过观看演示、模仿、探究、实践等活动，在使用计算机解决实际问题的过程中，分析其特点，了解人与计算机解决问题的异同。 3. 情感态度

18、与价值观（1）培养对算法与程序设计的兴趣。（2）感受计算机解决问题的优势。（3）逐步养成运用计算机分析问题、解决问题的习惯。【教学方式】采用网络授课和假期集中授课相结合的方式。由学生在网络平台进行自我学习，PPT按教学内容制作，便于同学形象理解。教学视频由老师录制，与上课同步，使网络授课的学生也能得到在课堂上的效果。以上资源在网上共享，便于同学下载学习。程序设计例题以online judge上的题目为主，阅读文献以国家集训队论文为主。【考核方式】本课程采用多种考核评价方式，包括自我评价、同伴评价、教师评定。侧重于对学生的过程评价。课程一共分为10个专题，每个专题一个算法，每个算法除了理论知识外

19、，还有相应的实例。并且每个专题都留有相应的练习题，需要学生在课后之余训练，而且都是通过在线评判系统提交。在线评判系统及时反馈评测结果，这样达到学生进行自我评价。每个专题的练习结果都将作为最终评价的一部分，这样可以更好地突出学生整个的学习状况和程度。在寒暑期集中学习阶段，结合分组讨论，进行同伴评价。最终的评价将由主讲老师结合这3个方面给出每个学生的成绩。【学习建议】算法与程序设计是一门实践性非常强的课程，因此要求学习者多动手，多上机，为此我们给出以下学习建议：（1）算法与数据结构相辅相成，密不可分程序设计不仅仅需要算法，还需要相应的数据结构来支撑。因此要想学好程序设计，除了要学会和掌握相应的算法

20、，还需要掌握数据结构的内容。因此建议学习者在学习算法与程序设计课程之前，复习已经学过的数据结构的内容，重点掌握像线性表、堆栈、队列、串、树、图等常见的数据结构。（2）算法的描述方法、算法的设计、算法的分析优化，是学习和掌握各种算法的基础建议学习者在学习这门课程之前学习有关算法设计和分析方面的理论知识。（3）在“做中学”和“学中做”调查表明,我们所掌握的知识，有10是通过“阅读”得来的，有15是“听”来的，有80是亲身经历获得来的。对于算法和程序设计来说，众多的算法是前辈们通过各种途径总结出来的，是非常经典的。要想学会和掌握它们，仅仅通过阅读和背诵是不行的，必须多上机练习，掌握其实际的应用，这样

21、才能达到学以致用。（4）各个专题的重点内容第一专题：信息学竞赛简介与算法基础重点掌握信息学竞赛的整体状况和NOI竞赛的比赛规则、试题类型、知识范畴，以及算法基础知识。第二专题：数制转换与高精度计算重点掌握各种数制及其它们之间转换以及高精度数的各种运算。第三专题：字符串处理重点掌握字符串的比较、查找等处理。第四专题：排序算法重点掌握各种常见排序算法及其使用，如冒泡排序、插入排序、快速排序。第五专题：搜索算法重点掌握二分查找法。第六专题：递归算法重点掌握递归算法的设计，注意递归出口。第七专题：贪心算法重点掌握贪心算法的基本思想以及贪心算法解题的基本要素。第八专题：图论重点掌握图的搜索算法，如深度优

22、先搜索和广度优先搜索。第九专题：动态规划重点掌握动态规划求解时如何寻找“子问题”，如何定义“状态”，如何给出“状态转移方程”。第十专题：模拟重点掌握用计算机模拟解决现实中难以用公式解决的问题。专题一 信息学竞赛简介与算法基础【主要内容】1.信息学奥林匹克相关知识：介绍信息学奥林匹克竞赛的基本常识、比赛规则、题目范围等。2.算法与程序设计的基础：介绍算法的基本常识以及常见的算法介绍等。【学习重点】信息学奥林匹克竞赛的基本常识、算法的基本介绍，包括信息学奥林匹克竞赛的基本常识、比赛规则、题目范围以及算法的基本常识以及常见的算法介绍等。一、信息学竞赛简介（一）信息学竞赛概述信息学奥林匹克竞赛是一项旨

23、在推动计算机普及的学科竞赛活动，重在培养学生能力，使得有潜质有才华的学生在竞赛活动中锻炼和发展。近年来，信息学竞赛活动组织逐步趋于规范和完善，基本上形成了“地级市省（直辖市）全国国际”四级相互接轨的竞赛网络。信息学竞赛系列活动主要包括以下六个方面：（1）各省市组织的与NOI有关的培训和竞赛活动；（2）全国青少年信息学奥林匹克联赛（National Olympiad in Informatics in Provinces，简称NOIP）；（3）全国青少年信息学奥林匹克竞赛（National Olympiad in Informatics，简称NOI），同时举行夏令营和全国青少年信息学奥林匹克团体

24、对抗赛；（4）全国青少年信息学奥林匹克竞赛冬令营；（5）亚洲和太平洋地区信息学奥林匹克竞赛（Asia and Pacific Informatics Olympiad，简称APIO）；（6）国际信息学奥林匹克中国队选拔赛，全国信息学奥林匹克精英赛，参加国际信息学奥林匹克（International Olympiad in Informatics，简称IOI）。其大致顺序为：先举办全国信息学（计算机）奥林匹克分区联赛（NOIP），联赛分高中组，初中组进行，以普及为主。在分区联赛的基础上，各省市组成自己的代表队，参加第二个层次的比赛，即全国青少年信息学奥林匹克竞赛（NOI）。第三个层次是从NOI中

25、选拔优秀选手（20人），经过培训，考试选拔，组成国家队（一般4-5人），参加国际信息学奥林匹克竞赛，即IOI，这是国际性的最高水平的竞赛。（二）各类比赛简介1全国青少年信息学奥林匹克竞赛（NOI）1984年邓小平指出：“计算机的普及要从娃娃做起。”教育部和中国科协委托中国计算机学会（CCF）举办了全国青少年计算机程序设计竞赛。从此每年举办一次全国青少年计算机程序设计竞赛。该竞赛是经国家教委批准，中国科协具体领导，由中国计算机学会主办的，是国内包括港澳在内的省级代表队最高水平的大赛。由各省市组织参赛，经各省NOIP选拔产生5名选手（其中一名是女选手），每年由中国计算机学会在计算机普及较好的城市举

26、办一次比赛。奖项有个人一、二、三等奖，女选手第一、二、三名，各省队团体总分名次排队。而自从1989年我国参加第一届国际信息学奥林匹克（简称IOI）以来，全国青少年计算机程序设计竞赛也更名为全国青少年信息学（计算机）奥林匹克（NOI）。NOI期间，举办同步夏令营和NOI网上同步赛，给那些程序设计爱好者和高手提供机会。为增加竞赛的竞争性、对抗性和趣味性以及可视化，NOI组织进行团体对抗赛，团体对抗赛实质上是程序对抗赛，其成绩纳入总分计算。2全国青少年信息学奥林匹克竞赛冬令营全国青少年信息学奥林匹克竞赛冬令营（简称冬令营）自1995年起。每年在寒假期间开展为期8天的培训活动。冬令营包括授课、 讲座、

27、讨论、测试等。参加冬令营的营员分正式营员和非正式营员。获得NOI前20名的选手和指导教师为正式营员，非正式营员限量自愿报名参加。在冬令营授课的是著名大学的资深教授及已获得国际金牌学生的指导教师。IOI的选手是从获NOI前20名选手中选拔出来的，获得前4名的优胜者代表中国参加国际竞赛。选拔科目包括：NOI成绩、冬令营成绩、论文和答辩、平时作业、选拔赛成绩、口试。上述项目加权产生最后成绩。官方网站：3全国青少年信息学奥林匹克联赛（NOIP）全国青少年信息学奥林匹克联赛（NOIP）是由中国计算机学会主办的以省为赛区单位组织实施的全国性竞赛，是全国青少年信息学奥林匹克竞赛（NOI）系列活动的重要组成部

28、分。在举办1995年NOI活动之前，为了扩大普及面，并考虑到多数省、直辖市、自治区已经开展了多年省级竞赛，举办了首届全国青少年信息学（计算机）奥林匹克分区联赛。考虑到不同年级学生的知识层次，也为了鼓励更多的学生积极参与，竞赛设提高组、普及组，并分初、复赛进行，这样可以形成一个梯队，确保每年的竞赛活动有比较广泛扎实的基础。4亚洲和太平洋地区信息学奥林匹克竞赛亚洲和太平洋地区信息学奥赛（APIO）于2007年创建，该竞赛为区域性的网上准同步赛，是亚洲和太平洋地区每年一次的国际性赛事，旨在给青少年提供更多的赛事机会，推动亚太地区的信息学奥林匹克的发展。APIO每年5月举行，由不同的国家轮流主办。每个

29、参赛团参赛选手上限为100名，其中成绩排在前6名的选手作为代表该参赛团的正式选手统计成绩。APIO中国赛区由中国计算机学会组织参赛，获奖比例将参照IOI。5国际信息学奥林匹克竞赛1987年，保加利亚的sendov教授在联合国教科文组织（UNESCO）第24次全体会议上提出了举办IOI的倡议。从此IOI成为五项国际学科奥林匹克竞赛之一，是由联合国教科文组织于1988年创建。首届竞赛于1989年5月在保加利亚的布拉维茨举行，有13个国家的46名选手参赛。我国只有信息学是首届就获得参赛资格的，而且首届竞赛的试题原型是由中国提供的。IOI的宗旨是：宣传信息学这一新兴学科；激发学生对计算机科学和信息技术

30、的兴趣；给学校这一类课程增加动力和新思路；通过竞赛形式对有才华的青少年给予激励，促使其能力得以发展；特别是使世界各国有才华的中学生汇聚一堂，进行科学文化上的交流，并学习主办国优秀的文化。中国参赛队由中国计算机学会组织，代表中国参加国际每年一次的IOI。中国是IOI创始国之一。出国参赛得到中国科协和国家自然科学基金委的资助。自1989年开始，我国在NOI（网上同步赛1999年开始）、NOIP、冬令营、选拔赛的基础上，组织参加国际信息学奥林匹克（IOI）竞赛。中国已成为世界公认的信息学奥林匹克竞赛强国。官方网站：/index.shtml二、全国

31、青少年信息学奥林匹克联赛组织指南1竞赛组别：竞赛分普及组和提高组两个组别，各分初赛和复赛两轮进行。2参赛对象：凡初、高中阶段的学生和同等年龄段中等专业学校的在校学生均可以报名参加。3大纲与命题：联赛大纲由主办单位NOI科学委员会制订并颁布。命题采取开放形式，任何有兴趣者均可志愿提供候选赛题。最终竞赛题目由主办单位 NOI科学委员会确定。4组织形式：由主办单位统一大纲、统一命题、统一制卷、统一评分标准、统一竞赛时间、统一评测。5竞赛形式和时间初赛为笔试，主要测试选手有关计算机方面的基本知识，每年10月份的第三个周六下午2:30-4:30在各赛区进行。复赛为上机编程，主要测试选手算法设计编程能力，

32、每年11月份的第三个周六在各赛区进行：提高组于上午8:30-11:30进行，普及组于下午1:30-4:30进行。6参赛报名及参赛资格：参赛的选手到各省组织单位报名，确认后参加。报名工作由各赛区特派员负责实施。报名截止日期：当年的9月20日。初赛：报名参赛的选手填写好报名表。各赛区特派员将按普及组和提高组（分语言）分别统计出报名人数，于当年的9月20日前用电子邮件或网络方式将NOIP试卷数量申请表上报主办单位。复赛：各赛区根据初赛成绩从高到低依次确定参加复赛的选手，不参加初赛的选手不具有参加复赛的资格。参加复赛的人数不高于参加初赛人数的20%。特派员应于初赛后10天内，按普及组和提高组（分语言）

33、统计出参加复赛的选手和人数以及复赛试卷申请数量，用电子邮件或网络方式上报主办单位。三、全国青少年信息学奥林匹克联赛大纲解读（一）竞赛宗旨由中国计算机学会负责组织的全国青少年信息学奥林匹克联赛（NOIP）是全国信息学奥林匹克竞赛（NOI）系列活动中的一个重要组成部分，旨在向中学生普及计算机基础知识，培养计算机科学和工程领域的后备人才。普及的重点是根据中学生的特点，培养学生学习计算机的兴趣，使得他们对信息技术的一些核心内容有更多的了解，提高他们创造性地运用程序设计知识解决实际问题的能力。对学生的能力培养将注重以下的几个方面：想象力与创造力；对问题的理解和分析能力；数学能力和逻辑思维能力；对客观问题

34、和主观思维的口头和书面表达能力；人文精神：包括与人的沟通能力，团队精神与合作能力，恒心和毅力，审美能力等。（二）竞赛形式和成绩评定NOIP分两个等级组：普及组和提高组。每组竞赛分两轮：初试和复试。初试形式为笔试，侧重考察学生的计算机基础知识和编程的基本能力，并对知识面的广度进行测试。初试为资格测试，获本省初试成绩在本赛区前15%的学生进入复赛。复试形式为上机编程，着重考察学生对问题的分析理解能力，数学抽象能力，编程语言的能力和编程技巧、想象力和创造性等。各省NOIP的等第将在复试的优胜者中产生。比赛中使用的程序设计语言是：初赛：PASCAL或C/C+： 复赛：PASCAL或C/C+。每年复赛结

35、束后，各省必须在指定时间内将本省一等奖候选人的有关情况、源程序和可执行程序报送科学委员会。经复审和评测后，由中国计算机学会报送中国科协和教育部备案。中国计算机学会对各省获NOIP二等奖和三等奖的分数线或比例提出指导性意见，各省可按照成绩确定获奖名单。（三）试题形式每次NOIP的试题分四组：普及组初赛题A1、普及组复赛题A2、提高组初赛题B1和提高组复赛题B2。其中，A1和B1类型基本相同，A2和B2类型基本相同，但题目不完全相同，提高组难度高于普及组。1初赛初赛全部为笔试，满分100分。试题由四部分组成：（1）选择题：共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题（

36、即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案，只有全部选对才得分）。普及组20个都是单选题。（2）问题求解题：共2题，每题5分，共计10分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。考生给出的答案与标准答案相同，则得分；否则不得分。（3）程序阅读理解题：共4题，每题8分，共计32分。题目给出一段程序（不一定有关于程序功能的说明），考生通过阅读理解该段程序给出程序的输出。输出与标准答案一致，则得分；否则不得分。（4）程序完善题：共2题，每题14分，共计28分。题目给出一段关于程序功能的文字说明，然后给

37、出一段程序代码，在代码中略去了若干个语句或语句的一部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对则得分；否则不得分。2复赛复赛的题型和考试形式与NOI类似，全部为上机编程题，但难度比NOI低。题目包括4道题，每题100分，共计400分。每一试题包括：题目、问题描述、输入输出要求、样例描述及相关说明。测试时，测试程序为每道题提供了5-10组测试数据，考生程序每答对一组得1020分，累计分即为该道题的得分。特别说明的是：自2011年起，复赛提高组由一试改为两试，分两天进行。每天竞赛试题由原来的4题改为3题。所有进入复赛的提高组选手均参加一试和二试，选手最

38、终成绩由一试与二试成绩算术相加而得。复赛普及组不变：复赛普及组仍为一试，四个题目。四、试题的知识范围（一）NOIP初赛内容与要求1计算机的基本常识 （1）计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化）； （2）信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）； （3）信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序和存储程序原理、程序的三种基本控制结构）； （4）信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）； （5）信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互

39、连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点）； （6）人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作）； （7）信息技术的新发展、新特点、新应用等。 2计算机的基本操作 （1）Windows和LINUX的基本操作知识； （2）互联网的基本使用常识（网上浏览、搜索和查询等）； （3）常用的工具软件使用（文字编辑、电子邮件收发等）。 3程序设计的基本知识 （1）数据结构 Ø 程序语言中基本数据类型（字符、整数、长整、浮点） Ø 浮点运算中的精度和数值比较 Ø一维数组（串）与线性表 

40、6;记录类型（PASCAL）/ 结构类型（C） （2）程序设计 Ø结构化程序设计的基本概念 Ø阅读理解程序的基本能力 Ø 具有将简单问题抽象成适合计算机解决的模型的基本能力 Ø 具有针对模型设计简单算法的基本能力 Ø 程序流程描述（自然语言/伪码/NS图/其他） Ø 程序设计语言（PASCAL/C/C+）- 2003仍允许BASIC （3）基本算法处理 Ø 初等算法（计数、统计、数学运算等） Ø 排序算法（冒泡法、插入排序、合并排序、快速排序） Ø 查找（顺序查找、二分法） Ø 回溯算法 （二）

41、NOIP复赛内容与要求 在初赛内容的基础上增加以下内容： 1数据结构 （1）指针类型 （2）多维数组 （3）单链表及循环链表 （4）二叉树 （5）文件操作（从文本文件中读入数据，并输出到文本文件中） 2程序设计 （1）算法的实现能力 （2）程序调试基本能力 （3）设计测试数据的基本能力 （4）程序的时间复杂度和空间复杂度的估计 3算法处理 （1）离散数学知识的应用（如排列组合、简单图论、数理逻辑） （2）分治思想 （3）模拟法 （4）贪心法 （5）简单搜索算法（深度优先、广度优先），搜索中的剪枝 （6）动态规划的思想及基本算法 （三）NOI竞赛内容 NOI竞赛的题目以考查选手对算法和编程能力的

42、掌握为主。题目类型有以下三种： 1非交互式程序题 非交互式程序题要求选手提交答案程序的源文件。该程序从一个正文文件中读入数据，并向指定的输出文件中写入计算结果。非交互式程序题的题面包括下列内容： （1）求解问题的描述 （2）输入文件名和输出文件名（可以是标准输入/输出） （3）输入数据格式、输出数据格式以及输入数据范围 （4）对程序使用计算资源的限制以及其它可能的限制 2交互式程序题 交互式程序题要求选手提交答案程序的源文件。该程序通过调用所提供的库函数实现数据的输入和输出。交互式程序题的题面包括下列内容： （1）求解问题的描述 （2）库函数的功能、函数原型以及获取和链接方式 （3）输入数据格

43、式、输出数据格式以及输入数据范围 （4）对程序使用计算资源的限制以及其它可能的限制 3答案提交题 答案提交题不要求选手提交程序的源文件。选手需要按题目要求，根据给定的输入数据文件生成一组输出数据文件。该组数据文件既可以是由选手的程序输出的，也可以是由选手手工构造的。当选手使用自行设计的程序生成题目答案时，其所使用的程序不应提交。答案提交题的题面包括下列内容： （1）求解问题的描述 （2）输入数据格式、输出数据格式 （3）输入数据文件的获取方法 对于交互式程序题和非交互式程序题，对选手程序使用内存大小的限制包括运行代码、程序运行时所需的栈和堆在内的所有工作内存的总和。当题面中没有给出对使用内存的

44、限制时，以选手用机的实际使用限制为准。对选手程序运行时间的限制一般均大于标准答案程序所需最长运行时间的50%以上，以避免测试中的超时判断误差。 五、竞赛允许使用的编程语言NOIP：允许使用Basic、Pascal或C语言。在个别赛区的个别年份允许使用C+，不过这只是极个别的情况。因此准备NOIP竞赛的时候最好别考虑C+。推荐使用Pascal，因为当前市场上分区联赛的相关辅导书籍都使用Pascal描述的。不推荐使用Basic，因为NOI中不允许使用这种语言。 NOI：允许使用C/C+或Pascal语言。 六、算法基础（一）算法概述 1算法定义 用计算机解决问题的过程可以分成三个阶段：分析问题、设

45、计算法和实现算法。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤，它是求解问题类的、机械的、统一的方法，它由有限多个步骤组成，对于问题类中的每个给定的具体问题，机械地执行这些步骤就可以得到问题的解答。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。 2算法特征 一个算法应该具有以下五个方面的重要特征： （1）输入：所谓输入是指从算法在执行时需要从外界取得必要的信息。一个算法有零个或多个输入，以刻画运算对象的初始情况。 （2）确定性：算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性，以保证算法

46、的实际执行结果是精确地符合要求或期望，通常要求实际运行结果是确定的。 （3）有穷性（有限性）：一个算法在执行有限步之后必须结束。也就是说，一个算法，它所包含的计算步骤应是有限的。 （4）输出：算法有一个或多个的输出，即与输入有某个特定关系的量，简单地说就是算法的最终结果。 （5）有效性（可行性）：算法中有待执行的运算和操作必须是相当基本的，换言之，它们都是能够精确地进行的，算法执行者甚至不需要掌握算法的含义即可根据该算法的每一步骤要求进行操作，并最终得出正确的结果。 （二）复杂度 不同的算法可能用不同的时间、空间或效率来完成同样的任务。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主

47、要从时间复杂度和空间复杂度来考虑。 1时间复杂度 （1）时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T（n）。 （2）时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T（n）也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中

48、基本操作重复执行的次数是问题规模n的某个函数，用T（n）表示，若有某个辅助函数f（n），使得当n趋近于无穷大时，T（n）/f（n）的极限值为不等于零的常数，则称f（n）是T（n）的同数量级函数。记作T（n）=O（f（n），称O（f（n） 为算法的渐进时间复杂度，简称时间复杂度。 在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O（1），另外，在时间频度不相同时，时间复杂度有可能相同，如T（n）=n2+3n+4与T（n）=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O（n2）。 按数量级递增排列，常见的时间复杂度有： 常数阶O（1），对数阶O（log2n）（以2为底n的

49、对数，下同），线性阶O（n），线性对数阶O（nlog2n），平方阶O（n2），立方阶O（n3），.，k次方阶O（nk），指数阶O（2n）。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。 2空间复杂度 算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。空间复杂度是指算法在计算机内执行时所需存储空间的度量。 记作：S（n）=O（f（n） 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。 （三）算法描述描述算法的方法有多种，常用的有自然语言、结构化流程图、伪代码和

50、程序设计语言等，其中最普遍的是流程图。1用自然语言表示 自然语言是人们日常所用的语言，如汉语、英语、德语等。使用这些语言不用专门训练，所描述的算法也通俗易懂。但比较冗长，容易出现歧义性。自然语言往往含义不太严格，很多时候需要根据上下文才能准确地判断其正确的含义。此外用自然语言来描述分支或循环的算法，比较麻烦。因此，除了那些很简单的算法外，一般很少用自然语言来描述算法。 2用流程图表示 以特定的图形符号加上说明，表示算法的图，称为流程图或框图。流程图是由一些图框和流程线组成的，其中图框表示各种操作的类型，图框中的文字和符号表示操作的内容，流程线表示操作的先后次序。 流程图主要包括： 圆角矩形表示

51、“开始”与“结束”； 矩形表示行动方案、普通工作环节用； 菱形表示问题判断或判定（审核/审批/评审）环节； 用平行四边形表示输入输出； 箭头代表工作流方向。 美国国家标准化协会ANSI规定了一些常用的流程图符合，已为世界各国程序工作者普遍使用。 1966年，Bohra和Jacopini提出了三种基本结构：顺序结构，选择结构，循环结构作为表示一个良好算法的基本单元。 三种结构共同特点： （1）只有一个入口； （2）只有一个出口； （3）结构内的每一部分都有机会被执行到（不存在死语句）； （4）结构内不存在死循环（永远执行不完的循环）。 1973年美国学者I. Nassi和B. Shneiderm

52、an提出了一种新的流程图形式，完全去掉了带箭头的流程线，称为N-S流程图表示法。 3伪代码表示 伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。它自上而下，每一行（或几行）表示一个基本操作。不用图形符号，书写方便，格式紧凑，也比较好懂，也便于向计算机语言算法（即程序）过渡。 4程序设计语言 按照某种编程语言的规范，用该编程语言编写实现算法。 七、常见算法1算法可以宏泛分为三类： （1）有限的，确定性算法：这类算法在有限的一段时间内终止。它们可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。 （2）有限的，非确定算法：这类算法在有限的时间

53、内终止。然而，对于一个（或一些）给定的数值，算法的结果并不是唯一的或确定的。 （3）无限的算法：是那些由于没有定义终止定义条件，或定义的条件无法由输入的数据满足而不终止运行的算法。通常，无限算法的产生是由于未能确定的定义终止条件。 2算法具体分类 算法可大致分为基本算法（枚举、搜索、深度优先搜索、广度优先搜索、启发式搜索、遗传算法）、数据结构的算法、数论与代数算法、计算几何的算法（凸包）、图论的算法（哈夫曼编码、树的遍历、最短路径、最小生成树、最小树形图）、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法。 （1）枚举：罗列出某些有穷序列集的所有成员，逐一进行尝试，直到

54、找到满足条件的解。 （2）搜索：搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。 （3）深度优先搜索：深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前（子结点）探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。深度优先搜索的实现方式可以采用递归或者栈来实现。 （4）广度优先搜索：类似树的按层遍历，其过程为：首先访问初始点Vi，并将其标记为已访问过，接着访问Vi的所有未被访问过可到达的邻接点Vi1、

55、Vi2Vit，并均标记为已访问过，然后再按照Vi1、Vi2Vit的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。 （5）启发式搜索：启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 （6）遗传算法：遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、

56、突变、自然选择以及杂交等。 遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。 （7）凸包分为两种情况：点集Q的凸包是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。 一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问

57、题了。 （8）递推法：递推算法是一种用若干步可重复的简运算（规律）来描述复杂问题的方法。递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定象的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。 （9）递归法：程序调用自身的编程技巧称为递归。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递

58、归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 注意： 递归就是在过程或函数里调用自身； 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。 （10）穷举法：或称为暴力破解法，是一种针对于密码的破译方法，即将密码进行逐个推算直到找出真正的密码为止。例如一个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试10000次就能找到正确的密码。理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。因此有些人运用计算机来增加效率，有些人辅以字

59、典来缩小密码组合的范围。 （11）贪婪算法: 贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题， 通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这

60、多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通

61、过一系列局部最优的选择即贪婪选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。 （12）分治法：就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 分治法所能解决的问题一般具有以下几个特征： Ø 该问题的规模缩小到一定的程度就可以容易地解决； Ø 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。 Ø

62、 利用该问题分解出的子问题的解可以合并为该问题的解； Ø 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。 （13）动态规划法 :动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问

63、题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。 （14）迭代法: 迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，

64、让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。 （15）分枝界限法: 分枝界限法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一

65、直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。与贪心算法一样，这种方法也是用来为组合优化问题设计求解算法的，所不同的是它在问题的整个可能解空间搜索，所设计出来的算法虽其时间复杂度比贪婪算法高，但它的优点是与穷举法类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过限界，可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工智能中的剪枝），故它比穷举法效率更高。 （16）排序算法: 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。目前主要有插入排序、冒泡排序、选择排序、快

66、速排序、堆排序、归并排序、基数排序、希尔排序等。专题二 数制转换与高精度计算【主要内容】 1. 数制转换：介绍数制的相关概念以及常见的各种数制及其它们之间的转换。 2. 高精度计算：介绍高精度数的各种运算。 【学习重点】 数制的相关概念、常见的各种数制及其它们之间的转换以及高精度数的各种运算。 一、数制转换（一）相关概念1数制 数制是人们利用符号进行计数的一种科学方法。数制也称计数制，是用一组固定的符号和统一的规则来表示数值的方法。 2进制 进制也就是进位制，是人们规定的一种进位方法。对于任何一种进制X进制，就表示某一位置上的数运算时是逢X进一位。 十进制是逢十进一，十六进制是逢十六进一，二进

67、制就是逢二进一。 3数码 数制中表示基本数值大小的不同数字符号。例如，十进制有10个数码：0、1、2、3、4、5、6、7、8、9。 4基数 数制所使用数码的个数。例如，二进制的基数为2；十进制的基数为10。 5位权 位权表示数的符号在不同的位置上时所代表的数的值是不同的。也就是数制中某一位上的1所表示数值的大小（所处位置的价值）。例如，十进制的123，1的位权是100，2的位权是10，3的位权是1。 （二）各种常见的进制 人们通常采用的进制有十进制、二进制、八进制和十六进制等。 1十进制（Decimal） 十进制是人们日常生活中最熟悉的进位计数制。在十进制中，数码共有0，1，2，3，4，5，6

68、，7，8，9这十个符号。计数规则是逢十进一。 2二进制（Binary） 二进制是在计算机系统中采用的进位计数制。二进制数有两个特点：在二进制中，数码有0和1两个符号。计数规则是逢二进一。 为区别于其它进制数，二进制数的书写通常在数的右下方注上基数2，或在后面加上B表示。例如：二进制数10110011可以写成（10110011）2，或写成10110011B。 3八进制数（Octal） 由于二进制数据的基数比较小，所以二进制数据的书写和阅读很不方便，为此，在小型机中引入了八进制。八进制的基数R=8=23，有数码0、1、2、3、4、5、6、7，并且每个数码正好对应三位二进制数，所以八进制能很好地反映二进制。八进制用下标8或数据后面加O表示 例如：二进制数据 （ 11 101 010 . 010 110 100 ）2 ，对应的八进制数据 ( 3 5 2 . 2 6 4 )8或352.264O。 4十二进制（Duodecimal） 十二进制在生活中也是经常用到的，