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

算法设计与分析

黄宇 编著（第一版）

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个不同整数排序至少而要多少次比较？请证明你的结论。

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

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个数就是排序后的整数。

代码如下：

#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;
}

测试结果：

34 789 1
Input values are: 34
Input values are: 789
Input values are: 1
Result is: 789 34 1

第二部分 朴素遍历

第三部分 分治策略

第四部分 贪心策略

第五部分 动态规划

第六部分 计算复杂性初步