作者：王晓东
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
计算机算法设计与分析(第4版)试读：
前言
计算机的普及极大地改变了人们的生活。目前，各行业、各领域都广泛采用了计算机信息技术，并由此产生出开发各种应用软件的需求。为了以最小的成本、最快的速度、最好的质量开发出适合各种应用需求的软件，必须遵循软件工程的原则。设计一个高效的程序不仅需要编程小技巧，更需要合理的数据组织和清晰高效的算法，这正是计算机科学领域数据结构与算法设计所研究的主要内容。
一些著名的计算机科学家在有关计算机科学教育的论述中认为，计算机科学是一种创造性思维活动，其教育必须面向设计。“计算机算法设计与分析”正是一门面向设计，且处于计算机学科核心地位的教育课程。通过对计算机算法系统的学习与研究，理解掌握算法设计的主要方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础，对每一位从事计算机系统结构、系统软件和应用软件研究与开发的科技工作者都是非常重要和必不可少的。
为了适应21世纪我国培养计算机各类人才的需要，本课程结合我国高等学校教育工作的现状，追踪国际计算机科学技术的发展水平，更新了教学内容和教学方法，以算法设计策略为知识单元，系统地介绍计算机算法的设计方法与分析技巧，以期为计算机专业的学生提供一个广泛扎实的计算机算法知识基础。本课程的教学改革实践取得了丰硕的成果，“算法与数据结构”课程被评为国家精品课程。
本书修正了第3版中发现的一些错误，并将各章的习题分为算法分析题和算法实现题两部分，增加了算法实践性内容，以期加强教学实践环节。具体修改如下：
增加了1.3 节NP完全性理论。
删除了理论性较强的3.12节动态规划加速原理、4.8节贪心算法的理论基础、第9章NP完全性理论与近似算法，以适应本科教学的要求。
对各章习题进行了重新编排与调整。配套教辅《计算机算法设计与分析习题解答（第2版）》也同步进行了修订。
全书共分8章。
第1章介绍算法的基本概念，并对算法的计算复杂性和算法的描述做了简要阐述。然后围绕算法设计常用的基本设计策略组织了第2～8章的内容。
第2章介绍递归与分治策略，它是设计有效算法最常用的策略，也是必须掌握的方法。
第3章是动态规划算法，以具体实例详述动态规划算法的设计思想、适用性及算法的设计要点。
第4章介绍贪心算法，它也是一种重要的算法设计策略，它与动态规划算法的设计思想有一定的联系，但其效率更高。按贪心算法设计出的许多算法能导致最优解。其中有许多典型问题和典型算法可供学习和使用。
第5章和第6章分别介绍回溯法和分支限界法。这两章所介绍的算法适合处理难解问题。其解题思想各具特色，值得学习和掌握。
第7章介绍随机化算法，对许多难解问题提供了高效的解决途径，是有很高实用价值的算法设计策略。
第8章介绍实用性很强的线性规划与网络流算法。许多实际应用问题可以转化为线性规划和网络流问题，并可用第8章中的算法有效求解。
在本书各章的论述中，首先介绍一种算法设计策略的基本思想，然后从解决计算机科学和应用中的实际问题入手，由简到繁地描述几个经典的精巧算法。同时对每个算法所需的时间和空间进行分析，使读者既能学到一些常用的精巧算法，又能通过对算法设计策略的反复应用，牢固掌握这些算法设计的基本策略，以期收到融会贯通之效。在为各种算法设计策略选择用于展示其设计思想与技巧的具体应用问题时，本书有意重复选择某些经典问题，使读者能深刻地体会到一个问题可以用多种设计策略求解。同时通过对解同一问题的不同算法的比较，使读者更容易体会到每一种具体算法的设计要点。随着本书内容的逐步展开，读者也将进一步感受到综合应用多种设计策略可以更有效地解决问题。
本书采用面向对象的C++语言作为算法描述手段，在保持C++优点的同时，尽量使算法描述简明、清晰。
为便于学习，我们在章首增加了学习要点提示，在章末配有难易适度的习题，并分为算法分析题和算法实现题两部分，以强化实践环节。为便于教学，本教材配套出版了《计算机算法设计与分析习题解答（第2版）》，并免费提供电子课件，请任课教师登录华信教育资源网http：//www.hxedu.com.cn免费注册下载。
作者还结合国家精品课程建设，建立了“算法设计与分析”教学网站http：//algorithm.fzu.edu.cn和“算法与数据结构”教学网站http：//ds.fzu.edu.cm/fine/index.htm，欢迎广大读者访问教学网站，并提出宝贵意见，作者E-mail：wangxd＠fzu.edu.cn。
在本书编写过程中，得到了全国高等学校计算机专业教学指导委员会的关心和支持。福州大学“211工程”计算机与信息工程重点学科实验室为本书的写作提供了优良的设备和工作环境。傅清祥教授、吴英杰博士、傅仰耿博士和朱达欣副教授参加了本书有关章节的讨论，对本书第4版的内容及各章节的编排提出了许多建设性意见。田俊教授认真审阅了全书。电子工业出版社负责本书编辑出版工作的全体同仁为本书的出版付出了大量辛勤的劳动，他们认真细致、一丝不苟的工作精神保证了本书的出版质量。在此，谨向每一位曾经关心和支持本书编写工作的各方面人士表示衷心的谢意！
由于作者的知识和写作水平有限，书稿虽几经修改，仍难免有缺点和错误。热忱欢迎同行专家和读者批评指正，使本书在使用中不断得到改进，日臻完善。
作者
第1章 算法概述
学习要点
· 理解算法的概念
· 掌握算法在最坏情况、最好情况和平均情况下的计算复杂性概念
· 掌握算法复杂性的渐近性态的数学表述
· 了解NP类问题的基本概念
1.1 算法与程序
对于计算机科学来说，算法（Algorithm）的概念是至关重要的。例如，在一个大型软件系统的开发中，设计出有效的算法将起决定性的作用。通俗地讲，算法是指解决问题的一种方法或一个过程。更严格地讲，算法是由若干条指令组成的有穷序列，且满足下述4条性质。（1）输入：有零个或多个由外部提供的量作为算法的输入。（2）输出：算法产生至少一个量作为输出。（3）确定性：组成算法的每条指令是清晰的，无歧义的。（4）有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
程序（Program）与算法不同。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质（4）。例如操作系统，它是一个在无限循环中执行的程序，因而不是一个算法。然而可把操作系统的各种任务看成是一些单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。
描述算法可以有多种方式，如自然语言方式、表格方式等。在本书中，采用C++语言描述算法。C++语言的优点是类型丰富、语句精炼，具有面向过程和面向对象的双重特点。用C++来描述算法可使整个算法结构紧凑，可读性强。在本书中，有时为了更好地阐明算法的思路，还采用C++与自然语言相结合的方式来描述算法。
1.2 算法复杂性分析
算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需资源越多，该算法的复杂性越高；反之，所需资源越少，该算法的复杂性越低。对计算机资源，最重要的是时间和空间（即存储器）资源。因此，算法的复杂性有时间复杂性和空间复杂性之分。
不言而喻，对于任意给定的问题，设计出复杂性尽可能低的算法是设计算法时追求的一个重要目标。另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是选用算法时遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。
更确切地说，算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要空间资源的量称为空间复杂性。这个量应该集中反映算法的效率，并从运行该算法的实际计算机中抽象出来。换句话说，这个量应该是只依赖于要解的问题的规模、算法的输入和算法本身的函数。如果分别用N，I和A表示算法要解的问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F（N，I，A），其中F（N，I，A）是一个由N，I和A确定的三元函数。如果把时间复杂性和空间复杂性分开，并分别用T和S来表示，应该有T=T（N，I，A）和S=S（N，I，A）。通常，A隐含在复杂性函数名当中，因而将T和S分别简写为T=T（N，I）和S=S（N，I）。
由于时间复杂性与空间复杂性概念类同，计量方法相似，且空间复杂性分析相对简单些，所以本书将主要讨论时间复杂性。现在的问题是如何将复杂性函数具体化，即对于给定的N，I和A，如何导出T（N，I）和S（N，I）的数学表达式，来给出计算T（N，I）和S（N，I）的法则。下面以T（N，I）为例，将复杂性函数具体化。
根据T（N，I）的概念，它应该是算法在一台抽象的计算机上运行所需要的时间。设此抽象的计算机所提供的元运算有k种，它们分别记为O，O，…，O。又设每执行一次这些元运算所需要时间分12k别为t，t，…，t。对于给定的算法A，设经统计，用到元运算O的12ki次数为e，i=1，2，…，k。很清楚，对于每一个i，1≤i≤k，e是N和I的ii函数，即e=e（N，I）。因此有ii
式中，t，i=1，2，…，k，是与N和I无关的常数。i
显然，不可能对规模为N的每一种合法的输入I都去统计e（N，iI），i=1，2，…，k。因此T（N，I）的表达式还要进一步简化，或者说，只能在规模为N的某些或某类有代表性的合法输入中统计相应的e，i=1，2，…，k，评价其时间复杂性。i
本书只考虑三种情况下的时间复杂性，即最坏情况、最好情况和平均情况下的时间复杂性，并分别记为T（N）、T（N）和maxminT（N）。在数学上有avg**
式中，D是规模为N的合法输入的集合；I是D中使T（N，I）NN达到T（N）的合法输入；I～是D中使T（N，I～）达到T（N）maxNmin的合法输入；而P（I）是在算法的应用中出现输入I的概率。
以上三种情况下的时间复杂性从某一个角度反映算法的效率，各有其局限性，也各有各的用处。实践表明，可操作性最好且最有实际价值的是最坏情况下的时间复杂性。
随着经济的发展、社会的进步和科学研究的深入，要求用计算机解决的问题越来越复杂，规模越来越大。对求解这类问题的算法进行复杂性分析具有特别重要的意义，因而要特别关注。在此，要引入复杂性渐近性态的概念。
设T（N）是前面所定义的关于算法A的复杂性函数。一般来说，当N单调增大且趋于∞时，T（N）也将单调增大且趋于∞。对于T（N），如果存在（N），使得当N→∞时有（T（N）-（N））/T（N）→0，那么，就说（N）是T（N）当N→∞时的渐近性态，或称（N）为算法A当N→∞的渐近复杂性，而与T（N）相区别。因为在数学上，（N）是T（N）当N→∞时的渐近表达式。直观上，（N）是T（N）中略去低阶项所留下的主项，所以它无疑比2T（N）来得简单。比如当T（N）＝3N+4NlogN+7时，（N）的2一个答案是3N，因为这时有22
显然，3N比3N+4NlogN+7简单得多。
由于当N→∞时，T（N）渐近于（N），我们有理由用（N）来替代T（N）作为算法A在N→∞时的复杂性的度量。而且由于（N）明显地比T（N）简单，这种替代明显是对复杂性分析的一种简化。进一步考虑到分析算法的复杂性的目的在于比较求解同一问题的两个不同算法的效率。而当要比较的两个算法的渐近复杂性的阶不相同时，只要能确定出各自的阶，就可以判定哪一个算法的效率高。换句话说，这时的渐近复杂性分析只要关心（N）的阶就够了，不必关心包含在（N）中的常数因子。所以，常常又对（N）的分析进一步简化，即假设算法中用到的所有不同的元运算各执行一次所需要的时间都是一个单位时间。
上面给出了简化算法复杂性分析的方法和步骤，即只要考察当问题的规模充分大时，算法复杂性在渐近意义下的阶。与此简化的复杂性分析相配套，需要引入以下渐近意义下的记号O，Ω，θ和o。
以下设f（N）和g（N）是定义在正数集上的正函数。
如果存在正的常数C和自然数N，使得当N≥N时有f（N）≤00Cg（N），则称函数f（N）当N充分大时上有界，且g（N）是它的一个上界，记为f（N）=O（g（N））。这时还说f（N）的阶不高于g（N）的阶。
举几个例子：（1）因为对所有的N≥1有3N≤4N，所以有3N=O（N）；（2）因为当N≥1时有N+1024≤1025N，所以有N+1024=O（N）；22（3）因为当N≥10时有2N+11N-10≤3N，所以有222N+11N-10=O（N）；2323（4）因为对所有N≥1有N≤N，所以有N=O（N）；32（5）作为一个反例，N≠O（N）。因为若不然，则存在正的常32数C和自然数N，使得当N≥N时有N≤CN，即N≤C。显然，当取N0032＝max｛N，+1}时这个不等式不成立，所以N≠O（N）。0
按照符号O的定义，容易证明它有如下运算规则：（1）O（f）+O（g）=O（max（f，g））；（2）O（f）+O（g）=O（f+g）；（3）O（f）O（g）=O（fg）；（4）如果g（N）=O（f（N）），则O（f）+O（g）=O（f）；（5）O（Cf（N））=O（f（N）），其中C是一个正的常数；（6）f=O（f）。
规则（1）的证明：设F（N）=O（f）。根据符号O的定义，存在正常数C和自然数N，使得对所有的N≥N，有F（N）≤Cf（N）。1111
类似地，设G（N）=O（g），则存在正的常数C和自然数N，22使得对所有的N≥N，有G（N）≤Cg（N）。22
令C=max｛C，C｝，N=max｛N，N｝，h（N）312312=max｛f，g｝，则对所有的N≥N，有3
类似地，有
因而
其余规则的证明类似，留给读者作为练习。
应该指出，根据符号O的定义，用它评估算法的复杂性，得到的只是当规模充分大时的一个上界。这个上界的阶越低，则评估就越精确，结果就越有价值。
关于符号Ω，文献里有两种不同的定义。本书只采用其中的一种，定义如下：如果存在正的常数C和自然数N，使得当N≥N时有f（N）00≥Cg（N），则称函数f（N）当N充分大时下有界；且g（N）是它的一个下界，记为f（N）=Ω（g（N））。这时还说f（N）的阶不低于g（N）的阶。Ω的这个定义的优点是与O的定义对称，缺点是当f（N）对自然数的不同无穷子集有不同的表达式，且有不同的阶时，不能很好地刻画出f（N）的下界。比如当
时，按上述定义，只能得到f（N）=Ω（1），这是一个平凡的下界，对算法分析没有什么价值。然而，考虑到上述定义有与符号O定义的对称性，又考虑到本书介绍的算法都没出现上例中那种情况，所以本书还是选用它。
同样要指出，用Ω评估算法的复杂性，得到的只是该复杂性的一个下界。这个下界的阶越高，则评估就越精确，结果就越有价值。再则，这里的Ω只对问题的一个算法而言。如果它是对一个问题的所有算法或某类算法而言的，即对于一个问题和任意给定的充分大的规模N，下界在该问题的所有算法或某类算法的复杂性中取，那么它将更有意义。这时得到的相应下界，称为问题的下界或某类算法的下界。它常常与符号O配合以证明某问题的一个特定算法是该问题的最优算法或该问题的某算法类中的最优算法。
定义f（N）=θ（g，（N））当且仅当f（N）=O（g（N））且f（N）=Ω（g（N））。这时，我们说f（N）与g（N）同阶。
最后，如果对于任意给定的ε＞0，都存在正整数N，使得当N≥0N时有f（N）/g（N）＜ε，则称函数f（N）当N充分大时的阶比0g（N）低，记为f（N）=o（g（N））。2
例如：4NlogN+7=o（3N+4NlogN+7）。
1.3 NP完全性理论
在计算机算法理论中，最深刻的问题之一是“从计算的观点来看，要解决的问题的内在复杂性如何?”它是“易”计算的还是“难”计算的?如果知道了一个问题的计算时间下界，就知道了对于该问题能设计出多有效的算法。从而可以较正确地评价已对该问题提出的各种算法的效率，并进而确定对已有算法还有多少改进的余地。在许多情况下，要确定一个问题的内在计算复杂性是很困难的。已创造出的各种分析问题计算复杂性的方法和工具，可以较准确地确定许多问题的计算复杂性。
问题的计算复杂性可以通过解决该问题所需计算量的多少来度量。如何区分一个问题是“易”还是“难”呢?人们通常将可在多项式时间内解决的问题看作是“易”解问题，而将需要指数函数时间解决的问题看作是“难”问题。这里所说的多项式时间和指数函数时间是针对问题的规模而言的，即解决问题所需的时间是问题规模的多项式函数或指数函数。对于实际遇到的许多问题，人们至今无法确切了解其内在的计算复杂性。因此只能用分类的方法将计算复杂性大致相同的问题归类进行研究。而对于能够进行较彻底分析的问题则尽可能准确地确定其计算复杂性，从而获得对它的深刻理解。
本书中的许多算法都是多项式时间算法，即对规模为n的输入，k算法在最坏情况下的计算时间为O（n），k为一个常数。是否所有的问题都在多项式时间内可解呢?回答是否定的。例如，存在一些不可解问题，如著名的“图灵停机问题”。任何计算机不论耗费多少时间也不能解该问题。此外，还有一些问题，虽然可以用计算机求解，但k是对任意常数k，它们都不能在O（n）的时间内得到解答。
一般地说，将可由多项式时间算法求解的问题看作是易解的问题，而将需要超多项式时间才能求解的问题看作是难解的问题。有许多问题，从表面上看似乎并不比排序或图的搜索等问题更困难，然而至今人们还没有找到解决这些问题的多项式时间算法，也没有人能够证明这些问题需要超多项式时间下界。也就是说，这类问题的计算复杂性至今未知。为了研究这类问题的计算复杂性，人们提出了非确定性图灵机计算模型。在该计算模型下，许多问题就可以在多项式时间内求解。
本书中讨论的许多问题是以最优化问题形式出现的，如旅行售货员问题、0-1背包问题和最大团问题等。然而对每一个最优化问题，都有一个与之对应的判定问题。第5章中要讨论的旅行售货员问题是一个典型的最优化问题。
最优化形式的旅行售货员问题可用图论语言形式描述如下。
设G=（V，E）是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题要在图G中找出费用最小的周游路线。
与之对应的判定形式的旅行售货员问题可描述如下。
对于给定的带权图G=（V，E）和一个正数d。判定形式的旅行售货员问题要求判定图G中是否存在总费用不超过d的周游路线。
容易看出，在一般情况下，判定问题比相应的最优化问题多一个输入参数d。直观上看，判定问题要比相应的最优化问题容易求解。从一个最优化问题的多项式时间算法容易得到与之相应的判定问题的多项式时间算法。
所有可以在多项式时间内求解的判定问题构成P类问题。
在通常情况下，解一个问题要比验证问题的一个解困难得多，特别在有时间限制的条件下更是如此。P类问题是确定性计算模型下的易解问题类，而NP类问题是非确定性计算模型下的易验证问题类。
为了说明什么是NP类问题，需要引入非确定性算法的概念。非确定性算法将问题求解分为猜测和验证两个阶段。算法的猜测阶段是非确定性的，它给出问题解的一个猜测。算法的验证阶段是确定性的，它验证猜测阶段给出的解的正确性。设算法A是解一个判定问题Q的非确定性算法。如果算法A的验证阶段可以在多项式时间内完成，则称算法A是一个多项式时间非确定性算法。同时也称问题Q是非确定性多项式时间可解的。
所有非确定性多项式时间可解的判定问题构成NP类问题。这里的NP就是非确定性多项式Nondeterministic Polynomial的缩写。例如对于判定形式的旅行售货员问题，容易在多项式时间内验证其解的正确性，因此旅行售货员问题属于NP类。
从P类和NP类问题的定义容易看出，P⊆NP。反之，大多数的计算机科学家认为，NP类中包含了不属于P类的问题，即P≠NP，但这个问题至今没有获得明确的解答。也许使大多数计算机科学家相信P≠NP的最令人信服的理由是，存在一类NP完全问题，即NPC类问题。这类问题有一种令人惊奇的性质，即如果一个NP完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内求解，即P＝NP。尽管已进行多年研究，目前还没有一个NP完全问题有多项式时间算法。
获得“第一个NP完全问题”称号的是布尔表达式的可满足性问题。这就是著名的Cook定理：布尔表达式的可满足性问题SAT是NP完全的。
Cook定理的重要性是明显的，它给出了第一个NP完全问题。这使得对于任何问题Q，只要能证明Q∈NP，而且可以在多项式时间内将SAT变换为问题Q，便有Q∈NPC。所以，人们很快就证明了许多其他问题的NP完全性。这些NP完全问题都是直接或间接地以SAT的NP完全性为基础而得到证明的。由此逐渐生长出一棵以SAT为树根的NP完全问题树。其中，每个结点代表一个NP完全问题，该问题可在多项式时间内变换为它的任一儿子结点表示的问题。实际上，由树的连通性及多项式在复合变换下的封闭性可知，NP完全问题树中任一结点表示的问题可以在多项式时间内变换为它的任一后裔结点表示的问题。目前这棵NP完全问题树上已有几千个结点，并且还在继续生长。
下面介绍这棵NP完全树中的几个典型的NP完全问题。
1.合取范式的可满足性问题CNF-SAT
给定一个合取范式α，判定它是否可满足。
如果一个布尔表达式是一些因子和之积，则称它为合取范式，简称CNF（Conjunctive Normal Form）。这里的因子是变量x或。例如，就是一个合取范式，而xx+x就不是合取范式。123
2.三元合取范式的可满足性问题3-SAT
给定一个三元合取范式α，判定它是否可满足。
3.团问题CLIQUE
给定一个无向图G=（V，E）和一个正整数k，判定图G是否包含一个k团，即是否存在，V′V，|V′|=k，且对任意u，w∈V′，有（u，w）∈E。
4.顶点覆盖问题VERTEX-COVER
给定一个无向图G=（V，E）和一个正整数k，判定是否存在V′V，|V′|=k，使得对于任意（u，v）∈E有u∈V′或v∈V′。如果存在这样的V′，就称V′为图G的一个大小为k的顶点覆盖。
5.子集和问题SUBSET-SUM
给定整数集合S和一个整数t，判定是否存在S的一个子集S′S，使得S′中整数的和为t。
例如，若S={1，4，16，64，256，1040，1041，1093，1284，1344}且t=3754，则子集S′={1，16，64，256，1040，1093，1284}是它的一个解。
6.哈密顿回路问题HAM-CYCLE
给定无向图G=（V，E），判定其是否含有一条哈密顿回路。
7.旅行售货员问题TSP
给定一个无向完全图G=（V，E）及定义在V×V上的一个费用函数c和一个整数k，判定G是否存在经过V中各顶点恰好一次的回路，使得该回路的费用不超过k。
算法分析题1
1-1 求下列函数的渐近表达式：22n3n
3n+10n；n/10+2；21+1/n；logn；10log3
1-2 试论O（1）和O（2）的区别。
1-3 按照渐近阶从低到高的顺序排列以下表达式：2n2/3
4n，logn，3，20n，2，n
又n！应该排在哪一位?
1-4（1）假设某算法在输入规模为n时的计算时间为T（n）=3×n2。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题?2（2）若上述算法的计算时间改进为T（n）=n，其余条件不变，则在新机器上用t秒时间能解输入规模为多大的问题?（3）若上述算法的计算时间进一步改进为T（n）=8，其余条件不变，那么在新机器上用t秒时间能解输入规模为多大的问题?
1-5 硬件厂商XYZ公司宣称他们最新研制的微处理器运行速度为2其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n，3n和n！的各算法，若用ABC公司的计算机在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题?
1-6 对于下列各组函数f（n）和g（n），确定f（n）=O（g（n））或f（n）=Ω（g（n））或f（n）=θ（g（n）），并简述理由。n
1-7 证明n！=o（n）。
1-8 下面的算法段用于确定n的初始值。试分析该算法段所需计算时间的上界和下界。
1-9 证明：如果一个算法在平均情况下的计算时间复杂性为θ（f（n）），则该算法在最坏情况下所需的计算时间为Ω（f（n））。
算法实现题1
1-1统计数字问题
★问题描述：一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是06或006等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2，…，9。9
★算法设计：给定表示书的总页码的十进制整数n（1≤n≤10），计算书的全部页码中分别用到多少次数字0，1，2，…，9。
★数据输入：输入数据由文件名为input.txt的文本文件提供。每个文件只有1行，给出表示书的总页码的整数n。
★结果输出：将计算结果输出到文件output.txt。输出文件共有10行，在第k行输出页码中用到数字k-1的次数，k=1，2，…，10。
1-2字典序问题
★问题描述：在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A由26个小写英文字母组成，即A={a，b，…，z}。该字母表产生的升序字符串是指字符串中字母从左到右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现1次。例如，a，b，ab，bc，xyz等字符串都是升序字符串。现在对字母表A产生的所有长度不超过6的升序字符串按照字典序排列并编码如下。
对于任意长度不超过6的升序字符串，迅速计算出它在上述字典中的编码。
★算法设计：对于给定的长度不超过6的升序字符串，计算它在上述字典中的编码。
★数据输入：输入数据由文件名为input.txt的文本文件提供。文件的第1行是一个正整数k，表示接下来共有k行。在接下来的k行中，每行给出一个字符串。
★结果输出：将计算结果输出到文件output.txt。文件共有k行，每行对应于一个字符串的编码。
1-3最多约数问题
★问题描述：正整数x的约数是能整除x的正整数。正整数x的约数个数记为div（x）。例如，1，2，5，10都是正整数10的约数，且div（10）=4。设a和b是2个正整数，a≤b，找出a和b之间约数个数最多的数x。
★算法设计：对于给定的2个正整数a≤b，计算a和b之间约数个数最多的数。
★数据输入：输入数据由文件名为input.txt的文本文件提供。文件的第1行有2个正整数a和b。
★结果输出：若找到的a和b之间约数个数最多的数是x，则将div（x）输出到文件output.txt。
1-4金币阵列问题
★问题描述：有m×n（m≤100，n≤100）枚金币在桌面上排成一个m行n列的金币阵列。每一枚金币或正面朝上，或背面朝上。用数字表示金币状态，0表示金币正面朝上，1表示金币背面朝上。
金币阵列游戏的规则是：（1）每次可将任一行金币翻过来放在原来的位置上；（2）每次可任选2列，交换这2列金币的位置。
★算法设计：给定金币阵列的初始状态和目标状态，计算按金币游戏规则，将金币阵列从初始状态变换到目标状态所需的最少变换次数。
★数据输入：由文件input.txt给出输入数据。文件中有多组数据。文件的第1行有1个正整数k，表示有k组数据。每组数据的第1行有2个正整数m和n。以下的m行是金币阵列的初始状态，每行有n个数字表示该行金币的状态，0表示正面朝上，1表示背面朝上。接着的m行是金币阵列的目标状态。
★结果输出：将计算出的最少变换次数按照输入数据的次序输出到文件output.txt。相应数据无解时输出-1。
试读结束[说明：试读内容隐藏了图片]