算法设计与问题求解——编程实践.pdf

高等学校规划教材算法设计与问题求解 编程实践李清勇 编著内 容 简 介本书是北京市精品教材立项项目，是大学生创新实践课程 “算法设计与实践”课程教材。本书以问题求解为目标，以高级程序设计语言C/C+为工具，讨论怎样综合运用算法（包括数据结构）知识去分析问题和解决问题。问题驱动、高级语言程序设计、数据结构以及算法设计与分析知识交叉融合是本书的特点。内容包括问题求解与算法分析概述、基本数据结构、高级数据结构、枚举算法、递归与分治、动态规划、贪心算法、搜索算法、图算法、算法分析的实用公式、在线程序评测系统简介等。教材配套有适合理论教学使用的电子课件以及适合实践教学使用的“在线程序评测系统”。本书适合高等学校计算机、信息与计算科学、信息管理等专业师生使用，也可作为A CM程序设计竞赛培训人员的参考书。未经许可，不得以任何方式复制或抄袭本书之部分或全部内容。版权所有，侵权必究。图书在版编目（C I P）数据算法设计与问题求解：编程实践/李清勇编著北京：电子工业出版社，2 0 1 3 6高等学校规划教材I S B N9 7 8-7-1 2 1-2 0 3 2 7-5算 李 电子计算机 算法设计 高等学校 教材 T P 3 0 1 6中国版本图书馆C I P数据核字（2 0 1 3）第0 9 4 7 5 2号策划编辑：袁 玺责任编辑：章海涛 文字编辑：袁 玺印 刷：装 订：出版发行：电子工业出版社北京市海淀区万寿路1 7 3信箱 邮编 1 0 0 0 3 6开 本：7 8 71 0 9 2 1/1 6 印张：1 5.5 字数：3 9 6 8千字印 次：2 0 1 3年6月第1次印刷定 价：3 5.0 0元凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系，联系及邮购电话：（0 1 0）8 8 2 5 4 8 8 8。质量投诉请发邮件至z l t s p h e i.c o m.c n，盗版侵权举报请发邮件至d b q q p h e i.c o m.c n。服务热线：（0 1 0）8 8 2 5 8 8 8 8。前 言2 0 0 6年3月，美国卡内基-梅隆大学计算机科学系主任周以真（J e a n n e t t eMW i n g）教授在美国计算机权威期刊C o mm u n i c a t i o n so f t h eA CM 上首先提出了计算思维（C o m p u t a t i o n a lT h i n k i n g）的概念。周教授认为：计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。计算思维是每个人的基本技能，不仅仅属于计算机科学家。我们应当使每个学生在培养解析能力时不仅掌握阅读、写作和算术（R e a d i n g，w R i t i n ga n da R i t h m e t i c，3 R），还要学会计算思维。正如印刷出版促进了3 R的普及，计算和计算机也以类似的正反馈促进了计算思维的传播，计算机逐渐成为了当今问题求解的最重要工具。1计算机与问题求解在2 0世纪4 0年代，为了求解军事领域复杂的炮弹弹道计算问题，科学家发明了第一台电子计算机“埃尼阿克”（E l e c t r o n i cN u m e r i c a l I n t e g r a t o rA n dC o m p u t e r，E N I A C）。随着计算机计算能力的增强，计算机被广泛应用到了社会生活的各个领域。大到宇宙探测、基因图谱绘制，小到日常工作、生活娱乐，无不需要计算机的支持。作为“问题求解的一个有力工具”，计算机尽管没有思维，只能机械地执行指令，但它运算速度快、存储容量大、计算精度高。如果能够设计有效的算法和程序，充分利用这些优点，计算机就能成为问题求解的一个利器。运算速度快是计算机最重要的特点之一。很多问题尽管比较复杂，但仍然存在求解的方法，只是这些方法往往计算量比较大，计算过程较为烦琐，人们难以在可以接受的时间内手工求解。【例】用1，2，3，4，5，6，7，8，9这9个数字拼成一个9位数，每个数字使用一次且仅用一次，要求得到的9位数的前3位、中间3位和最后3位构成的3位数的比值为123。例如1 9 2 3 8 4 5 7 6就是一个符合该要求的数，因为1 9 23 8 45 7 6=123。对于这样的问题，很容易想到的一个求解方案是：列举所有可能的9位数1 2 3 4 5 6 7 8 9，9 8 7 6 5 4 3 2 1，并逐个验证是否符合比值要求。理论上，这是一个可行的办法，可是几乎没有人愿意这样做。因为这样的9位数总共有9!=3 6 2 8 8 0个，即使每秒验证一个数（对于人工验证，这已经是很快的速度了），也需要1 0 0多个小时。但是，计算机实现同样的“笨方法”效果就大不一样。考虑用一个数组d保存9位数的各位数字，x，y，z分别代表前3位数、中间3位数和最后3位数，用S T L中的函数n e x t_p e r m u-t a t i o n计算9个数字的下一个排列。当某个排列（即一个9位数）满足比例要求xy z=123时，则输出该9位数。下面是解决此问题的C+代码，在普通的P C上运行该程序，需要的时间还不到0 1秒。3 v o i dN i n e N u m b e r（）i n tx，y，z;i n td9=1，2，3，4，5，6，7，8，9;d o x=d0*1 0 0+d1*1 0+d2;y=d3*1 0 0+d4*1 0+d5;z=d6*1 0 0+d7*1 0+d8;i f（y=x*2&z=x*3）c o u t x yze n d l;w h i l e（n e x t_p e r m u t a t i o n（d，d+9）;/S T L中的函数，得到下一个排列存储容量大是计算机的另一个重要特点。人们很容易记住1 0以内的两个数的乘积，也就是小学数学中的“九九乘法表”。但如果要求人们记住1 0 0以内的任意两个数的乘积，普通人可能会觉得“记忆”不够。但对于计算机来说，这真是“小菜一碟”，一个1 0 01 0 0的二维数组就可以把“百百乘法表”保存下来。人们常说的内存、硬盘、光盘、U盘等都是存储器，可以通俗地理解为计算机的记忆部件。容量的基本单位是字节（B y t e），记为B。其他单位有K B（1 K B=1 0 2 4 B）、MB（1 MB=1 0 2 4 K B）、G B（1 G B=1 0 2 4 MB）等。容量越大，可以存储的数据就越多，其“记忆力”就越强。“百百乘法表”如果用一个1 0 01 0 0的二维i n t型整数（假设一个i n t型整数占2字节）数组保存，它仅仅需要占用2 00 0 0字节（少于2 0 K B）的空间。相比现在计算机动辄数G B的内存容量来说，“百百乘法表”的存储开销微不足道。需要特别指出的是，运算速度快、存储容量大仅仅是计算机硬件系统的两个突出特点。在实际问题求解过程中，只有硬件平台还远远不够，人们需要针对问题设计不同的算法，并把算法转化为计算机可以运行的程序。2计算机问题求解的知识体系计算机问题求解的本质是把特定领域中特定问题的求解过程转换为计算机可以执行的程序。在这个转换过程中，除了必要的专业知识外，问题求解者还需要掌握计算机算法设计方面的知识，主要包括高级程序设计语言、数据结构和算法。这些知识构成了计算机问题求解的核心知识体系。在计算机教学体系中，高级程序设计语言、数据结构、算法是相互承接的课程系列。从计算机问题求解的角度看，这三门课程的知识相互交叉、相互支撑。高级程序设计语言和数据结构是算法设计的基础，高效的算法和数据结构需要用某种高级程序设计语言来实现;一个好程序不仅需要“编程小技巧”，更需要合理的数据结构和高效的算法。程序设计语言是问题求解的基本工具。随着计算机技术的发展，程序设计语言经历了一个从低级程序设计语言到高级程序设计语言的发展历程。机器语言和汇编语言等面向特定的体系结构和指令系统，在计算机发展的早期应用较多。随着形式语言理论、编译技术的发展，与目标机器无关的高级程序设计语言（如C/C+，J a v a等）逐渐成为程序设计的主流。本书约定的程序设计语言是C/C+。需要注意的是，程序设计语言并不等于程序设计，程序设计的4目的是表达程序设计者的思想，按照计算机所能理解的方式描述需要让计算机完成的工作，而程序设计语言只是表达这种思想的工具。程序设计的关键之处在于明确数据在计算机中的表达形式，以及确定如何将输入转化为输出的一系列计算步骤，而这些都需要数据结构和算法理论的指导。数据结构是问题求解的基础要素。数据是信息的载体，无论是待求解问题的输入/输出，还是问题求解过程中产生的中间量;无论是简单的量，比如单个数值，还是复杂的对象，它们在计算机中都以数据的形式进行存储。在问题求解时，为满足数据存储的结构化要求并提高程序执行效率，人们首先面临的问题是怎样合理地组织、存储和加工这些数据。常用的数据结构有线性表、栈、队列、树、二叉树、图、哈希表（散列表）等。数据结构的设计和应用不是一个教条化的生搬硬套过程，同一个问题也许可以运用不同的数据结构求解，而且它们求解的效率往往不尽相同。另外，有些问题可能没有现成的数据结构直接套用，需要人们综合运用基本数据结构组合成新的数据结构。无论是已有数据结构的选择还是新数据结构的设计，人们都需要应用算法设计与分析方面的知识。算法设计是问题求解的关键要素。简单地说，算法可以理解为把将问题输入转化为问题答案的一系列计算步骤。算法必须满足正确性与复杂性要求。首先，算法执行结果必须正确，它能正确无误地把每一个问题实例的正确答案求解出来。其次，算法的复杂度要适中。计算机系统的资源（包括运行时间和存储空间）是有限的，因此算法必须在有限的资源条件下正确地求解问题。同样的问题，某些算法执行结果可能不正确，某些算法执行结果则正确无误。即使执行结果都正确的不同算法，它们的执行效率可能也不尽相同，如有些算法需要几个小时，甚至几天，有些算法却仅仅需要几秒钟或几分钟。算法设计是一个灵活的、创造性的过程，甚至可以认为是一个艺术创造过程。有些算法是现实生活中人们解决问题时所用办法的升华和抽象;有些算法是数学理论和数学模型的体现和具体化。人们需要掌握经典的算法思想及其应用技巧，也要学会怎样针对特定问题设计和创造新算法。3本书的内容和结构本书是一本讲述怎样综合运用算法设计理论和技术进行问题求解的实践教材，主要讲述算法设计原理和方法，对运用算法求解问题时涉及的C/C+程序设计细节，尤其是影响算法准确性和复杂性的编程要点和技巧也进行了详细阐述。数据结构往往是算法设计和实现的基础，特别是一些高级数据结构，其本身就体现了很强的算法思维，因此本书不仅仅单独设立一章讲述数据结构，在讨论具体算法时也会交叉讨论相应的数据结构知识。本书包括7章，组织如下：第1章介绍问题求解和算法的基本概念，然后着重阐述了算法复杂度分析的基本理论和方法。第2章介绍程序设计和数据结构相关内容，程序设计和数据结构是算法设计的重要支撑，本章重点介绍了程序设计的三个盲点，以及常用的基本数据结构及其用法。第3章介绍枚举算法。“大道至简”，枚举算法是一种最朴素最简单的算法思想，但在具有卓越运算速度的计算机系统中，它却是常常被忽视的问题求解利器。本章重点阐述了怎样直接和间接运用枚举算法求解问题。第4章介绍递归和分治算法。“凡治众如治寡，分数是也”，分治策略是分析和解决复杂问5题最常用的策略之一。本章根据分治算法的求解步骤，将分治策略归纳为三类，并结合具体实例阐述每类策略的设计思想、适用范围及实现要点。第5章介绍动态规划算法。动态规划算法是最具有创造性的一种算法，归约、分治等思维方法都在动态规划算法框架中得到了很好的体现。本章重点讨论基于“划分”和“约简”策略的动态规划算法原理和运用技巧。第6章介绍贪心算法。这种类似于“瞎子爬山”的策略，如果运用适当，能够快速地产生最优解。本章给出