（已有15条评价）基本信息
编辑推荐
作者编著的《实用算法的分析与程序设计》一书曾经在全国信息学奥林匹克竞赛产生了广泛和深远的影响。本书是作者在该书基础上十年磨一剑、精心编写而成的，反映了近年来程序设计教育和竞赛培训活动出现的新趋势。全书不仅从教学的角度详细讲解算法的理论，而且从竞赛的角度对经典习题进行详细解析，重在培养学生灵活运用算法的能力。
本书是一部优秀的算法参考书，更是各层次程序设计竞赛培训不可错过的辅导书。
本书特色：
采用结构清晰、移植性强且贴近自然语言表述的类程序设计语言。
各章节之间有着紧密的内在联系，但是彼此又相对独立。
例题多采用一题多解、多向求解的方法，且各章均有与其内容相匹配的练习题。
开辟专门网站（http：／／admis.fudan.edu.cn／publications.htm），为读者提供大量的经典例题和测试数据。
内容简介
作译者
王建德，著名的信息学奥林匹克竞赛金牌教练，国务院特殊津贴专家，中学特级教师。他所辅导的学生在国际奥林匹克信息学竞赛（IOI）中获7金、2银、2铜的优异成绩。先后出版了22本关于程序设计和算法的学术专著。其中《实用算法的分析与程序设计》广受好评，长期以来是国内各类程序设计竞赛的必备教程。
目录
第1章 绪论
1.1 算法的基本定义
1.2 算法的空间复杂度
1.2.1 压缩存储技术
1.2.2 原地工作
1.3 算法的时间复杂度
1.3.1 基本运算
1.3.2 输入规模
1.3.3 输入情况
1.3.4 时间复杂度的阶
1.4 优化时间效率的方法
1.4.1 编程实现算法时注意细节优化
1.4.2 寻找解题思路时尽可能考虑最优性
1.5 实际生活中常见的算法问题
第2章 排序、顺序统计与解题的基本策略
2.1 计数排序与贪心策略
2.1.1 计数排序
2.1.2 贪心策略
2.2 “二分”思想与快速排序
2.2.1 分类和分治思想
1.1 算法的基本定义
1.2 算法的空间复杂度
1.2.1 压缩存储技术
1.2.2 原地工作
1.3 算法的时间复杂度
1.3.1 基本运算
1.3.2 输入规模
1.3.3 输入情况
1.3.4 时间复杂度的阶
1.4 优化时间效率的方法
1.4.1 编程实现算法时注意细节优化
1.4.2 寻找解题思路时尽可能考虑最优性
1.5 实际生活中常见的算法问题
第2章 排序、顺序统计与解题的基本策略
2.1 计数排序与贪心策略
2.1.1 计数排序
2.1.2 贪心策略
2.2 “二分”思想与快速排序
2.2.1 分类和分治思想
前言
十年前，我们为全国奥林匹克信息学活动编著了一本教材《实用算法的分析与程序设计》，虽然，该书早已在市场上售罄，但是它在编程解题能力的形成方面对许多读者产生了深远的影响。这些影响并没有随着岁月的流逝而淡漠。如果你上网“google”相关信息，屏幕上就会出现许多对该书赞美和留恋的贴子，而且各种形式的同名电子图书不计其数。确实，该书涉及的算法有极大的实用价值，在当时历史条件下属于相当新颖和先进的。这正是受读者青睐的一个重要原因。近几年来，不少出版社主动找上门来，希望我们能够顺应读者要求修订再版该书。这件事一直拖延至今，缘由是在如何修订再版的问题上，我们不想做简单的重复或细枝末节上的修改，而是想对该书来一个“更新换代”，力图用更好的方式回馈读者的期盼。十年来，随着算法讨论的深入和各类竞赛活动的推波助澜，涌现出许多新的算法思想。例如，在繁杂的数据中寻找和利用有价值的序，使问题获得简化；对无序的运算对象进行二分搜索；在满足单调性条件的最优性问题上使用参数搜索；通过Dinic算法分阶段、分层次地改进网络流图中的流量，计算最大流；利用四边形不等式原理推出最优决策的单调性，从而改善动态规划的效率，等等。与算法相关的经典例题也层出不穷。《实用算法的分析与程序设计》的新版本应该与时俱进，将这些新知识、新成果吸纳进来，并且以深入浅出、贴近实际的形式展现给读者。.
为了使选用本书的教师容易教，学生容易学，软硬件研发人员查阅时容易懂，本书在表述上采取了如下措施。
(1) 全书以某一方面的算法为基本构件，各章节既互相联系又相对独立，便于教师按照不同培养目标组织教学，方便读者根据需要选择学习内容。
(2) 对每个算法的原理进行必要的分析和证明，定理证明大多采用初等数学的分析方法，公式推导尽可能做到浅显和详细。通过“程序伪代码”说明其工作过程，并给出了运行时间的详细分析。对其中一些复杂算法附加了图示，使其过程更加具体、直观和形象。每个算法都有具体的应用例证来帮助理解。
(3) 对于一些例题，我们尽量采用“一题多解”或“多向求解”，并且尽量结合算法分析讲解一些常用的思维方式和解题策略，拓宽读者的思路，使其学会如何应用算法知识解题，如何选择有效算法。每章末尾提供一些习题，这些习题与该章讲授的内容顺序相匹配。为了使读者有更多的实践机会，我们开辟了一个专门的网http://admis.fudan.edu.cn/publications.htm，为读者提供了大量的经典例题和测试数据。
(4) 为了使程序样例不受单一语言的局限，不让某种特定语言的特殊性掩盖算法的本质内容，本书中采用了一种结构清晰、移植性强且贴近自然语言表述的类程序设计语言。只要你具备Pascal、C、true.bascal等任一种语言的基础，就可以比较轻松地读懂其语义。本书之所以未给出可直接编译运行的程序代码，除了考虑到语言的通用性外，还有一个重要的原因，就是想给读者留出动手编程的空间，避免无意义的“依葫芦画瓢”。
根据知识难度和“因材施教”的原则，本书既可以作为大专院校计算机专业算法类课程的教材，亦可作为大中学校计算机竞赛活动的培训教材，还可供计算机软硬件研发人员参考。建议教师组织教学或读者自学本书时，注意以下3个方面的问题。
(1) 培养良好的认知结构。初学时不必强求记住所有名词，在遇到难以理解的概念时也不必强求立即学会。可以和周围的人讨论，也可以先做一个标记接着往下读，在学习一个阶段后再回过头来思考当初的问题，这样可能会“茅塞顿开”。实际上，书中介绍的每一个算法都值得初学者多读几遍，这样既有助于记忆又可以获得更深入的理解。在深入学习算法的过程中，要注重相关算法理论的研究，通性通法，并通过不断地应用得以强化，使得相关理论和通性通法形成一个纵横交错、脉络分明、结构合理的知识网络。同时注意把一些常用的解题技巧和变换方法放在记忆库里，把同类问题和同类方法“存储在一起”，使知识条理化和系统化。..
(2) 按照“双轨复式”的方式学习算法。所谓“双轨”是指学习内容上沿两条线：一是知识结构，二是经典试题。在学习每一个知识点的同时，积累相关经典试题的解析经验，进行系统的、集中的分类解题训练。解一道试题，从某些侧面窥悉相关算法的基本特征。解同类算法的一组试题，通晓该算法知识的整体结构以及与其他知识点之间的联系。所谓“复式”是指某些内容特别重要的或较复杂的算法知识，不能指望经过一两次做题就能融汇贯通、熟练掌握，必须根据量力而行的原则，针对自己的认知水平和智力发展水平把同一内容分成深度与广度不同的若干片断，一步步地螺旋式上升，最后达到较好掌握的目的。注意把握节奏，一个阶段一个中心，问题过难过易都不能出现在一段较长的时间里，过难会丧失信心，过易则难以激发热情，这就需要读者从读书和做题过程中积极体验，认真反思，获取反馈，合理调整。
(3) 在学习算法理论的同时要多解题，从书本知识和编程实践中寻找再发现与再创造的契机。既要注意运算结果的正确性，也要注意知识产生和应用的过程性（概念和法则被概括的过程、数据关系被抽象的过程，以及解题思路逐步展开的过程）。要细化书本知识，如同电视屏幕中体育大赛的慢镜头式的分解，真正使自己学有所得，学有所悟。要多角度地思考问题。同一个问题，可选择的算法可能不止一种。不管所要完成的任务是大是小，最好在完成之后再设法寻找另一种方法完成它，后一种方法可能是更好的方法。特别是在使用某方法却没有成功时，不要半途而废，不妨换一种思路，可能会出现“东方不亮西方亮”的效果。相信读者大都有数据结构和基础算法的学习经历，有熟悉语言功能和编程操作的有利条件，应该充分利用这些第一手经验加深对算法概念的理解，用实践经验促进理论学习。“纸上得来终觉浅，绝知此事要躬行。”建议读者在基本理解算法的基础上，不妨亲手做一做书中的试题，通过上机获得再认识和再提高。从长远来看，无论是参与竞赛，还是学习算法课程，或者从事编程工作，读者会发现面临的问题对象千奇百怪，数据模型千姿百态，问题求解的算法千变万化，究竟采用哪一种算法，设计哪一类数据结构，选择哪一种语句形式，确定哪一种测试手段或优化方法，都要求读者从实际出发，因地因时制宜。只有不断通过实践，才能渐入本书的程序分析所描述的那种佳境，并有所发现、发明和创造。“阵而后战，兵法之常，运用之妙，存乎一心也。”
感谢上海市复旦大学附属中学李天翼、华东师范大学第二附属中学寿国威等同学。他们在我们的指导下，花费两年多的时间读懂了算法原理，同时用简洁易识的程序代码实现了算法。所有程序通过了数据测试，其中一些程序还经过多次修改，精益求精。他们为本书的顺利修订再版付出了辛勤的劳动，做出了不可或缺的贡献。
由于时间和水平所限，书中难免存在不妥和错误之处，欢迎同仁或读者赐正。如果在阅读中发现问题，请通过书信或电子邮件告诉我们，以便及时整理成勘误表放http://admis.fudan. edu.cn/publications.htm上，供广大读者查询更正。我们更期望读者对本书提出建设性意见，以便修订再版时改进。读者可通过以下方式与我联系。...
通信地址：上海市邯郸路220号复旦大学计算机科学与工程系 吴永辉 邮编200433
电子邮箱：yhwu@fudan.edu.cn
王建德 吴永辉
2008年1月于上海
为了使选用本书的教师容易教，学生容易学，软硬件研发人员查阅时容易懂，本书在表述上采取了如下措施。
(1) 全书以某一方面的算法为基本构件，各章节既互相联系又相对独立，便于教师按照不同培养目标组织教学，方便读者根据需要选择学习内容。
(2) 对每个算法的原理进行必要的分析和证明，定理证明大多采用初等数学的分析方法，公式推导尽可能做到浅显和详细。通过“程序伪代码”说明其工作过程，并给出了运行时间的详细分析。对其中一些复杂算法附加了图示，使其过程更加具体、直观和形象。每个算法都有具体的应用例证来帮助理解。
(3) 对于一些例题，我们尽量采用“一题多解”或“多向求解”，并且尽量结合算法分析讲解一些常用的思维方式和解题策略，拓宽读者的思路，使其学会如何应用算法知识解题，如何选择有效算法。每章末尾提供一些习题，这些习题与该章讲授的内容顺序相匹配。为了使读者有更多的实践机会，我们开辟了一个专门的网http://admis.fudan.edu.cn/publications.htm，为读者提供了大量的经典例题和测试数据。
(4) 为了使程序样例不受单一语言的局限，不让某种特定语言的特殊性掩盖算法的本质内容，本书中采用了一种结构清晰、移植性强且贴近自然语言表述的类程序设计语言。只要你具备Pascal、C、true.bascal等任一种语言的基础，就可以比较轻松地读懂其语义。本书之所以未给出可直接编译运行的程序代码，除了考虑到语言的通用性外，还有一个重要的原因，就是想给读者留出动手编程的空间，避免无意义的“依葫芦画瓢”。
根据知识难度和“因材施教”的原则，本书既可以作为大专院校计算机专业算法类课程的教材，亦可作为大中学校计算机竞赛活动的培训教材，还可供计算机软硬件研发人员参考。建议教师组织教学或读者自学本书时，注意以下3个方面的问题。
(1) 培养良好的认知结构。初学时不必强求记住所有名词，在遇到难以理解的概念时也不必强求立即学会。可以和周围的人讨论，也可以先做一个标记接着往下读，在学习一个阶段后再回过头来思考当初的问题，这样可能会“茅塞顿开”。实际上，书中介绍的每一个算法都值得初学者多读几遍，这样既有助于记忆又可以获得更深入的理解。在深入学习算法的过程中，要注重相关算法理论的研究，通性通法，并通过不断地应用得以强化，使得相关理论和通性通法形成一个纵横交错、脉络分明、结构合理的知识网络。同时注意把一些常用的解题技巧和变换方法放在记忆库里，把同类问题和同类方法“存储在一起”，使知识条理化和系统化。..
(2) 按照“双轨复式”的方式学习算法。所谓“双轨”是指学习内容上沿两条线：一是知识结构，二是经典试题。在学习每一个知识点的同时，积累相关经典试题的解析经验，进行系统的、集中的分类解题训练。解一道试题，从某些侧面窥悉相关算法的基本特征。解同类算法的一组试题，通晓该算法知识的整体结构以及与其他知识点之间的联系。所谓“复式”是指某些内容特别重要的或较复杂的算法知识，不能指望经过一两次做题就能融汇贯通、熟练掌握，必须根据量力而行的原则，针对自己的认知水平和智力发展水平把同一内容分成深度与广度不同的若干片断，一步步地螺旋式上升，最后达到较好掌握的目的。注意把握节奏，一个阶段一个中心，问题过难过易都不能出现在一段较长的时间里，过难会丧失信心，过易则难以激发热情，这就需要读者从读书和做题过程中积极体验，认真反思，获取反馈，合理调整。
(3) 在学习算法理论的同时要多解题，从书本知识和编程实践中寻找再发现与再创造的契机。既要注意运算结果的正确性，也要注意知识产生和应用的过程性（概念和法则被概括的过程、数据关系被抽象的过程，以及解题思路逐步展开的过程）。要细化书本知识，如同电视屏幕中体育大赛的慢镜头式的分解，真正使自己学有所得，学有所悟。要多角度地思考问题。同一个问题，可选择的算法可能不止一种。不管所要完成的任务是大是小，最好在完成之后再设法寻找另一种方法完成它，后一种方法可能是更好的方法。特别是在使用某方法却没有成功时，不要半途而废，不妨换一种思路，可能会出现“东方不亮西方亮”的效果。相信读者大都有数据结构和基础算法的学习经历，有熟悉语言功能和编程操作的有利条件，应该充分利用这些第一手经验加深对算法概念的理解，用实践经验促进理论学习。“纸上得来终觉浅，绝知此事要躬行。”建议读者在基本理解算法的基础上，不妨亲手做一做书中的试题，通过上机获得再认识和再提高。从长远来看，无论是参与竞赛，还是学习算法课程，或者从事编程工作，读者会发现面临的问题对象千奇百怪，数据模型千姿百态，问题求解的算法千变万化，究竟采用哪一种算法，设计哪一类数据结构，选择哪一种语句形式，确定哪一种测试手段或优化方法，都要求读者从实际出发，因地因时制宜。只有不断通过实践，才能渐入本书的程序分析所描述的那种佳境，并有所发现、发明和创造。“阵而后战，兵法之常，运用之妙，存乎一心也。”
感谢上海市复旦大学附属中学李天翼、华东师范大学第二附属中学寿国威等同学。他们在我们的指导下，花费两年多的时间读懂了算法原理，同时用简洁易识的程序代码实现了算法。所有程序通过了数据测试，其中一些程序还经过多次修改，精益求精。他们为本书的顺利修订再版付出了辛勤的劳动，做出了不可或缺的贡献。
由于时间和水平所限，书中难免存在不妥和错误之处，欢迎同仁或读者赐正。如果在阅读中发现问题，请通过书信或电子邮件告诉我们，以便及时整理成勘误表放http://admis.fudan. edu.cn/publications.htm上，供广大读者查询更正。我们更期望读者对本书提出建设性意见，以便修订再版时改进。读者可通过以下方式与我联系。...
通信地址：上海市邯郸路220号复旦大学计算机科学与工程系 吴永辉 邮编200433
电子邮箱：yhwu@fudan.edu.cn
王建德 吴永辉
2008年1月于上海
书摘
第1章绪论
什么是算法？为什么要对算法进行研究？相对于其他信息技术来说，算法的作用是什么？在实际生活中，算法有什么应用价值？衡量一个算法好坏的标准是什么？本章将围绕这些问题展开讨论。
1.1算法的基本定义
简单来说，所谓算法（algorithm）就是明确的计算过程，它取一个或一组值作为输入，并生成一个或一组值作为输出。亦即，算法就是一系列的计算步骤，用来将输入数据转换成输出结果，
如图1.1所示。
我们还可以将算法看作是一种工具，用来解决可以抽象出计算模型的问题。在表述该问题时，必须用严谨的语言规定所需的输入／输出关系。与之对应的算法则描述了一个特定的计算过程，用于实现这一输入／输出关系，如下所示。
输入：由n个数构成的一个序列（a1，a2，…an）。
输出：输出一个重排的序列（a1`，a2`，…an`）。，使得a1`≤a2`≤…≤an`。
需要指出的是，问题的表述方式是多样化的，并不一定像上面例子这么抽象呆板，例如，许多试题就采用了生动趣味的故事形式。而这里所说的语言严谨，是针对抽象计算模型而言。也就是说求解的目标是什么，给出了哪些已知信息、显式条件或隐含条件，最后应该用什么样的数据形式表达计算结果，必须描述清楚，切不能模棱两可或者产生歧义。同样，与问题对应的计算过程可以用自然语言、程序设计语言甚至硬件设计等形式来表达。不论采用哪种形式，解决问题的每一个步骤都必须准确定义，这是由于我们是和计算机打交道，稍有含糊则风马牛不相及。自然语言传递的信息，从语意上来看，可能会有不明之处，但我们处理它们时可根据上下文信息或平时习惯等来推理并准确地接受它，而计算机却不能。尤其是编程时，要用程序设计的范式语言精
确定义每一个步骤，千万不要误以为自己懂了计算机也会懂。
我们衡量一个算法好坏的标准主要有两个：正确性和时效性。
（1）算法的正确性。如果一个算法使其每一个输入实例都能在输出正确的结果后停止，则称它是正确的。
……
什么是算法？为什么要对算法进行研究？相对于其他信息技术来说，算法的作用是什么？在实际生活中，算法有什么应用价值？衡量一个算法好坏的标准是什么？本章将围绕这些问题展开讨论。
1.1算法的基本定义
简单来说，所谓算法（algorithm）就是明确的计算过程，它取一个或一组值作为输入，并生成一个或一组值作为输出。亦即，算法就是一系列的计算步骤，用来将输入数据转换成输出结果，
如图1.1所示。
我们还可以将算法看作是一种工具，用来解决可以抽象出计算模型的问题。在表述该问题时，必须用严谨的语言规定所需的输入／输出关系。与之对应的算法则描述了一个特定的计算过程，用于实现这一输入／输出关系，如下所示。
输入：由n个数构成的一个序列（a1，a2，…an）。
输出：输出一个重排的序列（a1`，a2`，…an`）。，使得a1`≤a2`≤…≤an`。
需要指出的是，问题的表述方式是多样化的，并不一定像上面例子这么抽象呆板，例如，许多试题就采用了生动趣味的故事形式。而这里所说的语言严谨，是针对抽象计算模型而言。也就是说求解的目标是什么，给出了哪些已知信息、显式条件或隐含条件，最后应该用什么样的数据形式表达计算结果，必须描述清楚，切不能模棱两可或者产生歧义。同样，与问题对应的计算过程可以用自然语言、程序设计语言甚至硬件设计等形式来表达。不论采用哪种形式，解决问题的每一个步骤都必须准确定义，这是由于我们是和计算机打交道，稍有含糊则风马牛不相及。自然语言传递的信息，从语意上来看，可能会有不明之处，但我们处理它们时可根据上下文信息或平时习惯等来推理并准确地接受它，而计算机却不能。尤其是编程时，要用程序设计的范式语言精
确定义每一个步骤，千万不要误以为自己懂了计算机也会懂。
我们衡量一个算法好坏的标准主要有两个：正确性和时效性。
（1）算法的正确性。如果一个算法使其每一个输入实例都能在输出正确的结果后停止，则称它是正确的。
……
