作者：王晓东
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
计算机算法设计与分析习题解答(第2版)试读：
前言
一些著名的计算机科学家在有关计算机科学教育的论述中认为，计算机科学是一种创造性思维活动，其教育必须面向设计。计算机算法设计与分析正是一门面向设计，且处于计算机学科核心地位的教育课程。通过对计算机算法系统的学习与研究，理解和掌握算法设计的主要方法，培养对算法的计算复杂性进行正确分析的能力，为独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础，对从事计算机系统结构、系统软件和应用软件研究与开发的科技工作者是非常重要和必不可少的。
电子工业出版社出版的《计算机算法设计与分析（第4版）》是普通高等教育“十一五”国家级规划教材，它是根据教育部高教司主持评审的《中国计算机科学与技术学科教程2002》以及ACM和IEEE/CS CC2001组织编写的教材，在内容选材、深度把握、系统性和可用性方面进行了精心设计，力图适合高校本科生教学对学时数和知识结构的要求。本书是与《计算机算法设计与分析（第4版）》配套的辅助教材，对该书中的习题做了解答或给出了解题思路提示。
算法设计与分析是计算学科的9个主科目之一，而且在整个学科知识体系中具有学科核心的重要地位，它充分体现了计算机科学方法论的理论、抽象和设计3个过程，知识面较宽，且有一定的深度；算法设计与分析课程需要反复再现计算机科学中用到的大问题的复杂性、效率、抽象的层次、重用、折中等带有普遍性的概念。根据作者多年的教学经验，算法设计与分析课程教学有以下3个特点，这使许多学生感到学习相当困难。（1）按照《中国计算机科学与技术学科教程2002》以及ACM和IEEE/CS CC2001的要求，算法设计与分析课程教学包括的知识点多，内容十分丰富，学习量大。（2）课程内容理论性很强，对学生的抽象思维能力和逻辑推理能力要求较高。（3）课程内容还有很强的实践性，要求学生灵活运用所学到的算法设计策略解决实际问题。
教材中的课后习题能在很大程度上解决上面所说的困难。《计算机算法设计与分析（第4版）》所配备的习题正是为此目的而设计的。教材出版后，许多读者纷纷要求给出习题解答和提示。为了让使用《计算机算法设计与分析（第4版）》作为教材的师生在广度和深度的各个层面更深刻地理解理论、抽象和设计这3个过程以及重复出现的12个基本概念（绑定、大问题的复杂性、概念和形式模型、一致性和完备性、演化、效率、抽象层次、按空间排序、按时间排序、重用、安全性、折中的结论），作者根据多年的教学经验编写了这本辅助教材，旨在让使用该书的教师更容易教，学生更容易学。为了便于对照阅读，本书的章序与《计算机算法设计与分析（第4版）》保持一致，且一一对应。
本书的内容是对教材《计算机算法设计与分析（第4版）》的扩展，一些在教材中无法讲述的较深入的主题通过习题的形式展现出来。为了提高学生灵活运用算法设计策略解决实际问题的能力，本书将原教材中的许多习题改造成算法实现题，要求学生不仅设计出解决具体问题的算法，而且能上机实现。其中很多题目使用了多种不同解法，体现了算法的灵活性和适用性。根据作者多年的教学实践，这类算法实现题的教学效果非常好。
本书内容丰富，理论联系实际，可作为高等学校计算机科学与技术、软件工程、信息安全、信息与计算科学等专业本科生和研究生学习计算机算法设计的辅助教材，也是工程技术人员和自学者的参考书。
作者还结合国家精品课程建设，进行了教材的立体化开发，包括主教材、习题解答、电子课件和教学网站等资源。作者的教学网站网址是：http：//www.algorithm.fzu.edu.cn，作者的E-mail地址是：wangxd＠fzu.edu.cn。欢迎广大读者访问教学网站并提出宝贵意见。
本书提供的教学资源包含各章算法实现题的题目、测试数据和答案。共有12个子目录，包括：ch1，ch2，…，ch8，midexam1，midexam2，finalexam1，finalexam2。每章的每个算法实现题都对应一个子目录，其中的test子目录中是测试数据，answer子目录中是相应的答案。midexam1和midexam2目录中是两套期中试卷。finalexam1和finalexam2目录中是两套期终试卷。本书主教材提供电子课件，需要者可登录华信教育资源网http：//www.hxedu.com.cn免费注册下载。算法设计的实现平台是Microsoft Visual Studio 6.0或Microsoft Visual Studio.NET。采用面向对象的C++语言作为算法描述手段。
在本书编写过程中，福州大学“211工程”计算机与信息工程重点学科实验室提供了优良的设备与工作环境。电子工业出版社负责本书编辑出版工作的全体同仁为本书的出版付出了大量辛勤劳动，他们认真细致，一丝不苟的工作精神保证了本书的出版质量。在此，谨向每位曾经关心和支持本书编写工作的各方面人士表示衷心的谢意！
作者
第1章 算法概述
算法分析题1
1-1 函数的渐近表达式
求下列函数的渐近表达式：22n3n
3n+10n；n/10+2；21+1/n；logn；10log3。
分析与解答：223
3n+10n=O（n）； logn=O（logn）；2nnn
n/10+2=O（2）； 10log3=O（n）。
21+1/n=O（1）；
1-2 O（1）和O（2）的区别
试论O（1）和O（2）的区别。
分析与解答：根据符号O的定义易知O（1）=O（2）。用O（1）或O（2）表示同一个函数时，差别仅在于其中的常数因子。
1-3 按渐近阶排列表达式
2n按照渐近阶从低到高的顺序排列以下表达式：4n，logn，3，2/320n，2，n。又n！应该排在哪一位?
分析与解答：按渐近阶从低到高，函数排列顺序如下：2，logn，2/32nn，20n，4n，3，n！。
1-4 算法效率
n（1）假设某算法在输入规模为n时的计算时间为T（n）=3×2。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题?2（2）若上述算法的计算时间改进为T（n）=n，其余条件不变，则在新机器上用t秒时间能解输入规模为多大的问题?（3）若上述算法的计算时间进一步改进为T（n）=8，其余条件不变，那么在新机器上用t秒时间能解输入规模为多大的问题?分析与解答：（1）设新机器用同一算法在t秒内能解输入规模为n1的问题。因nn1此有：t=3×2=3×2/64，解得n1=n+6。22（2）n1=64n⇒n1=8n。（3）由于T（n）=常数，因此算法可解任意规模的问题。
1-5 硬件效率
硬件厂商XYZ公司宣称他们最新研制的微处理器运行速度为其竞23争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n，n和n！的各算法，若用ABC公司的计算机在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题?
分析与解答：33
n′=100n n′=100n⇒n′==4.64n22
n′=100n⇒n′=10n n′！=100n！⇒n′＜n+log100=n+6.64
1-6 函数渐近阶
对于下列各组函数f（n）和g（n），确定f（n）=O（g（n））或f（n）=Ω（g（n））或f（n）=θ（g（n）），并简述理由。2（1）f（n）=logn；g（n）=logn+5 （5）f（n）=10； g（n）=log1022（2）f（n）=logn； g（n）= （6）f（n）=logn；g（n）=logn2n（3）f（n）=n； g（n）=logn （7）f（n）=2； g（n）2=100nn（4）f（n）=nlogn+n；g（n）=logn （8）f（n）=2； g（n）n=3
分析与解答：2（1）logn=θ（logn+5） （5）10=θ（log10）22（2）logn=O） （6）logn=Ω（logn）2n2（3）n=Ω（logn） （7）2=Ω（100n）nn（4）nlogn+n=Ω（logn） （8）2=O（3）
1-7 n！的阶
n证明：n！=o（n）。
分析与解答：Stirling’s approximation：
1-8 3n+1问题
下面的算法段用于确定n的初始值。试分析该算法段所需计算时间的上界和下界。
分析与解答：该算法表述的是著名的3n+1问题。在最坏情况下，该算法的计算时间下界显然为Ω（logn）。
算法的计算时间上界至今未知。算法是否在有限时间内结束，至13今还是一个悬而未决的问题。日本学者米田信夫曾对10内的所有自然数验证上述算法均在有限步结束。人们猜测，对所有自然数，上述算法均在有限步结束，但无法给出理论证明，因此也无法分析上述算法的计算时间上界。这个猜测就成为著名的3n+1猜想，也称为Collatz猜想。
1-9 平均情况下的计算时间复杂性
证明：如果一个算法在平均情况下的计算时间复杂性为θ（f（n）），则该算法在最坏情况下所需的计算时间为Ω（f（n））。
分析与解答：
因此，T（N）=Ω（T（N））=Ω（θ（f（n）））maxavg=Ω（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。
分析与解答：考察由0，1，2，…，9组成的所有n位数。从n个0nn到n个9共有10个n位数。在这10个n位数中，0，1，2，…，9每个数字使用次数相同，设为f（n）。f（n）满足如下递归式：n-1
由此可知，f（n）=n10。
据此，可从高位向低位进行统计，再减去多余的0的个数即可。
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行，每行对应于一个字符串的编码。
分析与解答：考察一般情况下长度不超过k的升序字符串。
设以第i个字符打头的长度不超过k的升序字符串个数为f（i，k），长度不超过k的升序字符串总个数为g（k），则g（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中。
分析与解答：设正整数x的质因子分解为
则
div（x）=（N+1）（N+1）…（N+1）12k
搜索区间［a，b］中数的质因子分解。
primes产生质数。
search搜索最多约数。
实现算法的主函数如下。
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。
分析与解答：枚举初始状态每一列变换为目标状态第1列的情况。算法描述如下。
其中，trans1模拟行翻转变换，trans2模拟列交换变换。
1-5 最大间隙问题
★问题描述：最大间隙问题：给定n个实数x，x，…，x，求这12nn个数在实轴上相邻2个数之间的最大差值。假设对任何实数的下取整函数耗时O（1），设计解最大间隙问题的线性时间算法。
★算法设计：对于给定的n个实数x，x，…，x，计算它们的最12n大间隙。
★数据输入：输入数据由文件名为input.txt的文本文件提供。文件的第1行有1个正整数n。接下来的1行中有n个实数x，x，…，12x。n
★结果输出：将找到的最大间隙输出到文件output.txt中。
分析与解答：用鸽舍原理设计最大间隙问题的线性时间算法如下。
其中，mini和maxi分别计算数组中最小元素和最大元素的下标。
由于下取整函数耗时O（1），故循环体内的运算耗时O（1）。因此，整个算法耗时O（n）。即算法maxgap是求最大间隙问题的线性时间算法。注意到在代数判定树计算模型下，Ω（nlogn）是最大间隙问题的一个计算时间下界。这意味着在代数判定树的计算模型下，最大间隙问题是不可能有线性时间算法的。在此题中假设下取整函数耗时O（1），实际上这可以看作是在代数判定树模型中，将下取整运算作为基本运算增加到原有的基本运算集中，从而使代数判定树计算模型的计算能力得到增强。因而可以在线性时间内解最大间隙问题。
第2章 递归与分治策略
算法分析题2
2-1 Hanoi塔问题的非递归算法
证明Hanoi塔问题的递归算法与非递归算法实际上是一回事。
分析与解答：Hanoi塔问题的递归算法：
主教材中所述非递归算法的目的塔座不确定。当n为奇数时，目的塔座是B，按顺时针方向移动；而当n为偶数时，目的塔座为C，按反时针方向移动。为确定起见，规定目的塔座为B。Hanoi塔问题的非递归算法可描述如下。
试读结束[说明：试读内容隐藏了图片]