算法设计与分析习题解答

出版时间：2008-2  出版社：清华大学  作者：王晓东  页数：420  字数：617000  
Tag标签：无  

内容概要

　　本书是清华大学出版社出版的普通高等教育“十一五”国家级规划教材《算法设计与分析（第2版）》（主教材）配套的辅助教材，对《算法设计与分析（第2版）》一书中的全部习题做了详尽的解答。本书的内容是对《算法设计与分析（第2版）》的较深入的扩展，许多在主教材中无法讲述的、较深入的主题通过习题的形式展现出来。为了加强学生灵活运用算法设计策略解决实际问题的能力，本书将主教材中的许多习题改造成算法实现题，要求学生不仅设计出解决具体问题的算法，而且能够上机实现。作者的教学实践反映出这类算法实现题的教学效果非常好。作者还结合国家精品课程建设，进行了教材的立体化开发，包括主教材、辅助教材、实验与设计、电子课件和教学网站建设。
　　本书内容丰富，观点新颖，理论联系实际。不仅可以用作高等学校计算机科学与技术学科各专业本科生和研究生学习计算机算法设计的辅助教材，而且也适合广大工程技术人员和自学读者学习参考。

作者简介

　　王晓东，男，1957年3月出生，福州大学计算机系教授，福建省计算机学会理事长。研究领域是算法设计与算法评价，基于计算机网络和信息安全的大规模问题求解算法与数据结构，信息可视化技术，几何计算，并行和分布式算法设计，计算复杂性理论。先后主持了与算法设计与分析有

书籍目录

第1章　算法引论
　习题1-1　实参交换
　习题1-2　方法头签名
　习题1-3　数组排序判定
　习题1-4　函数的渐近表达式
　习题1-5　O（1）和O（2）的区别
　习题1-7　按渐近阶排列表达式
　习题1-8　算法效率
　习题1-9　硬件效率
　习题1-10　函数渐近阶
　习题1-11　n！的阶
　习题1-12　平均情况下的计算时间复杂性
　算法实现题1-1　统计数字问题
　算法实现题1-2　字典序问题
　算法实现题1-3　最多约数问题
　算法实现题1-4　金币阵列问题
　算法实现题1-5　最大间隙问题
第2章　递归与分治策略
　习题2-1　Hanoi塔问题的非递归算法
　习题2-2　7个二分搜索算法
　习题2-3　改写二分搜索算法
　习题2-4　大整数乘法的O（n1Og（3/2））算法
　习题2-5　5次7//3位整数的乘法
　习题2-6　矩阵乘法
　习题2-7　多项式乘积
　习题2-8　不动点问题的O（1O9n）时间算法．
　习题2-9　主元素问题的线性时间算法
　习题2-10　无序集主元素问题的线性时间算法
　习题2-11　O（1）空间子数组换位算法
　习题2-12　O（1）空间合并算法
　习题2-13　n段合并排序算法
　习题2-14　自然合并排序算法
　习题2-15　最大值和最小值问题的最优算法
　习题2-16　最大值和次大值问题的最优算法
　习题2-17　整数集合排序
　习题2-18　第k小元素问题的计算时间下界”
　习题2-19　非增序快速排序算法
　习题2-20　随机化算法
　习题2-21　随机化快速排序算法
　习题2-22　随机排列算法”
　习题2-23　算法qSort中的尾递归
　习题2-24　用栈模拟递归
　习题2-25　算法se1ect中的元素划分
　习题2-26　O（nlogn）时间快速排序算法
　习题2-27　最接近中位数的k个数
　习题2-28　X和y的中位数
　习题2-29　网络开关设计
　习题2-32　带权中位数问题
　习题2-34　构造Gray码的分治算法
　习题2-35　网球循环赛日程表
　算法实现题2-1　输油管道问题（习题2-3O）
　算法实现题2-2　众数问题（习题2-31）
　算法实现题2-3　邮局选址问题（习题2-32）
　算法实现题2-4　马的Hami1tOn周游路线问题（习题2-33）
　算法实现题2-5　半数集问题
　算法实现题2-6　半数单集问题
　算法实现题2-7　士兵站队问题
　算法实现题2-8　有重复元素的排列问题
　算法实现题2-9　排列的字典序问题
　……
第3章　动态规划
第4章　贪心算法
第5章　回溯法
第6章　分支限界法
第7章　概率算法
第8章　NP完全性理论
第9章　近似算法
第10章　算法优化策略
第11章　在线算法设计
参考文献

章节摘录

版权页：   插图：   算法实现题2-1输油管道问题（习题2-30） 问题描述 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有，2口油井的油田。从每口油井都要有一条输油管道沿最短路径（或南或北）与主管道相连。如果给定n口油井的位置，即它们的x坐标（东西向）和y坐标（南北向），应如何确定主管道的最优位置（即使各油井到主管道之间的输油管道长度总和最小的位置）？证明可在线性时间内确定主管道的最优位置。 编程任务 给定n口油井的位置，编程计算各油井到主管道之间的输油管道最小长度总和。 数据输入 由文件input.txt提供输入数据。文件的第1行是油井数理n.1≤n≤10000。接下来n行是油井的位置，每行两个整数x和y，-10000≤x，y≤10000。 结果输出 程序运行结束时，将计算结果输出到文件Output.txt中。文件的第1行中的数是油井到主管道之间的输油管道最小长度总和。 输入文件示例 输出文件示例 input.txt output.txt 5 6 1 2 2 2 1 3 3-2 3 3 6 分析与解答： 设n口油井的位置分别为Pi=(xi，yi)，1≤i≤n。由于主输油管道是东西向的，因此可用其主轴线的y坐标唯一确定其位置。主管道的最优位置y应使∑d(y，yi)达到最小，其中，d(y，Yi)=|y-yi|。这正是习题2-32中一维邮局问题的特殊情形，即Wi=1/n，1≤i≤n的情形。由带权中位数问题的解答可知，yi（其中1≤i≤n）的中位数挑即为输油管道问题的最优解。用任一线性时间找中位数算法，均可在O(n)时间内解此问题。

编辑推荐

《普通高等教育"十一五"国家级规划教材•21世纪大学本科计算机专业系列教材:算法设计与分析习题解答(第2版)》内容丰富，观点新颖，理论联系实际。不仅可以用作高等学校计算机科学与技术学科各专业本科生和研究生学习计算机算法设计的辅助教材，而且也适合广大工程技术人员和自学读者学习参考。

用户评论 (总计2条)

•   除了物流慢(整整一周)，其它的都还不错。
•   看了感觉还可以。~~