以下为《《算法设计与分析》习题答案》的无排版文字预览，完整内容请下载
第1章 习题答案
使用计算机求解问题的基本步骤包括哪些？
答案：
1.问题分析
2．数学模型建立
3．算法设计与选择
4．算法表示
5．算法分析
6．算法实现
7．程序测试及调试
8．结果整理文档编制
什么是事前分析估算法？
答案：
一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，算法的时间效率是问题规模的函数。假如，随着问题规模n的增长，算法执行，时间的增长率和函数f(n)的增长率相同，则可记作：
T(n)＝O(f(n))
称T(n)为算法的渐近时间复杂度(asymptotic time complexity)，简称时间复杂度。o是数量级的符号。这就是事前分析估算法。
请思考：提高算法质量的一些原则性建议有哪些？
答案：
1)保证正确性、可靠性、稳健性、可读性
(1)当心那些在视觉上不易分辨的操作符发生书写错误。
(2)为了保证算法实现的正确性，算法中的变淿（指针、数组）在被引用前。一定要有确切的含义，或者是被赋过值，或者是作为形式参数经模块接口得到传递的信息。
(3)要注意算法中的表达式，它们有可能在计算时发生上溢或下溢，或作为数组的下标值出现越界的情况……不要留到算法实现时再考虑相关的问题。
(4)写算法时就要考虑，各种可能出错的情况，并设计处理错误的相关算法（这一点在许多数据结构课本中做得非常好！大家要学习借鉴）。
(5)编写算法时区别问题的循环条件和停止条件，不要误用。
(6)注意算法中循环体或条件体的位置，不要误把循环体内的操作写在循环体外或者出现相反的错误。有的初学者在使用“缩进格式”表示了操作的嵌套关系后，忽略了语句块的符号“{}”，这将为算法实现留下隐患。
2)提高效率
(1)以提高算法的全局效率为主，提高局部效率为辅。
(2)在优化算法的效率时，应当先找出限制效率的“瓶颈”，不要在无关紧要之处优化。
(3)多数情况下，时间效率和空间效率可能是对立的，此时应当分析哪个更重要，做出适当的折中。例如可以多花费一些内存来提高算法的时间性能。
(4)可以考虑先选取合适的数据结构，再优化算法。
(5)递归算法结构清晰简洁，它能使一个蕴含递归关系且结构复杂的算法简洁精练，增加可读性。但递归过程的实现决定了递归算法的效率往往很低，费时和费内存空间。在解决问题时，如果能使用递推法解决的，应考虑用递推法，其效率更高些。
(6)注意多用数学知识，可以大大提高算法效率。
(7)另外，还有一些细节上的问题也想引起大家注意，如乘、除运算的效率比加、减法运算低。
请举例说明一些现代常用算法。
答案：
压缩算法、加密算法、并行算法、数值算法、统计分析算法、网络搜索引擎算法等等。
第2章 习题答案
什么是递推法？
答案：
递推( recursion)算法是迭代算法的最基本的表现形式。一般来讲，一种简单的递推方式，是从小规模的问题推解出大规模问题的一种方法，也称其为“正推”。
什么是倒推法？
答案：
所谓倒推法(inverted recursion)是对某些特殊问题所采用的违反通常习惯的，从后向前推解问题的方法。
应用枚举解决问题，需要找出哪两个基本条件？
答案：
(1) 找出枚举范围：分析问题所涉及的各种情况。
(2) 找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。
查找最大值。
给定N个整数，查找这N个数中的最大值。
输入：
输入数据有多组，每组2行，第一行为M（1≤M≤1 OOO），第二行有M个整数．
输出：
输出每组数据第二行这M个数的最大值
输入样例
3
100 80 90
10
1 2 3 4 5 6 7 8 9 10
输出样例
100
10
答案：
分析：直接枚举这M个数，从中找出最大的数，然后输出即可。
#include
#define N 10010
#define oo ***00
int f[N];
int main()
{
int m;
while(scanf(“%d”,&m)!=EOF)
{
int max=-00;
for(int i=0;imax)
max=f[i];
}
printf(“%d\n”,max);
}
}
第3章 习题答案
分治算法设计的基本思想是什么？
答案：
(1) 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同
的子问题；
(2) 解决：若子问题规模较小而容易被解决则直接解，否则再继续分解为更
小的子问题，直到容易解决；
(3) 合并：将已求解的各个子问题的解，逐步合并为原问题的解。
分治算法的基本框架是什么？
答案：
分治法的一般的算法设计模式如下：
Divide-and-Conquer(int n) /n为问题规模/
{ if （n≤n0） /n0 为可解子问题的规模/
{ 解子问题；
return(子问题的解)；}
for （i=1 ;ix)
{
if (t>=m-1) return false;
t++;
s=cost[i];
}
else
s+=cost[i];
}
return true;
}
int binary(int max,int sum) //二分部分
{
int mid,left=max,right=sum;
while (left=0;
}
int Bsearch(int a,int b){
if(!N) return b;
int mid=(a+b)/2;
int ans=0;
while(aans) ans=mid;
a=mid+1;
mid=(a+b)/2;
}
else {
b=mid-1;
mid=(a+b)/2;
}
}
return ans;
}
int main() {
scanf("%d%d%d",&L,&N,&M);
for(int i=0;i
以上为《《算法设计与分析》习题答案》的无排版文字预览，完整内容请下载
《算法设计与分析》习题答案由用户“DBXBBSBS”分享发布，转载请注明出处