算法设计与分析课后习题参考答案

封面

算法设计与分析

黄宇 编著(第一版)

2020年8月25日开始整理此参考答案时已经出版了第二版。

说明

说明备注
整理日期2020.8.25
整理人幽弥狂
文件版本2020.8.25
联系方式1768478912@qq.com

1、黄宇老师在知乎上面说了,第一版和第二版他都没有做参考答案,也不打算做参考答案。并且黄宇老师在B站有配套的视频。

2、本人为了考研复习需要、学习内容并制作此参考答案,本着开源精神分享给各位。

3、本参考答案代码使用的是C语言,使用VSCode C插件,编译器版本为9.3.0。

4、如果有任何疑问或者问题可以随时联系我。

第一部分 计算模型

第1章 抽象的算法设计与分析

1.1 (3个数排序)输入3个各不相同的整数:

  1. 请设计一个算法将输入的3个整数排序。
  2. 在最坏情况下、平均情况下你的算法分别需要进行多少次比较?(假设所有
    可能的输入等概率出现。)
  3. 在最坏情况下将3个不同整数排序至少而要多少次比较?请证明你的结论。

1)输入3个整数a/b/c,按从大到小排序。将其放在数组里排序

1
2
3
4
5
6
for i :=0 to 2 do:
for j := i+1 to 3 do:
if(a[i] < a[j]) do:
temp = a[i];
a[i]=a[j];
a[j]=temp;

执行完毕之后,数组的第1、2、3个数就是排序后的整数。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>

int main(){
int a[3];
for(int i=0;i<3;i++){
std::cin>>a[i];
std::cout<<"Input values are: "<<a[i]<<std::endl;
}

for(int i=0;i<2;i++){
for(int j=i+1;j<3;j++){
if(a[i]<a[j]){
int temp = a[i];
a[i]=a[j];
a[j]=temp;
}
}
}

std::cout<<"Result is: ";
for(int i=0;i<3;i++){
std::cout<<a[i]<<" ";
}
std::cout<<std::endl;

return 0;
}

测试结果:

1
2
3
4
5
34 789 1
Input values are: 34
Input values are: 789
Input values are: 1
Result is: 789 34 1

第二部分 朴素遍历

第三部分 分治策略

第四部分 贪心策略

第五部分 动态规划

第六部分 计算复杂性初步