《算法导论》笔记（一）

第一章

练习1.1

Ans：

给学生成绩进行排名需要用到排序；TBD

Ans：

工作量；完成度；……

Ans：

栈：
栈的优势在于可以按照将一个序列原来的顺序保存下来，能很方便地按顺序操作；栈的局限在于无法从中间取出想要的元素，只能按照原始顺序操作

Ans：

相似之处：同样要求每一个节点最多只能经过一次，同时要求点到点的最短路径
不同之处：交通图最短路并没有要求经过每一个十字路口并回到起始十字路口，但是旅行商问题要求经过每一个点，同时还要回到起始点

P.S.：

旅行商问题：给n个点，求从起始点出发经过每一个点一次并回到起始点的最短路径，具体内容见：https://baike.baidu.com/item/%E6%97%85%E8%A1%8C%E5%95%86%E9%97%AE%E9%A2%98/7737042?fr=aladdin

Ans：

要求最佳解：TBD（非现实生活：火箭发射参数必须精确到最佳程度）
要求近似最佳解：买鞋42,42.3,42.5码没有很大的区别，都可以穿

练习1.2

Ans：

需要算法内容的应用如抖音；算法的功能在于根据用户看过视频的标签给用户进行类似视频/广告推送

P.S.:

物联网应用层：分为“数据”与“应用”两部分，具体内容见：https://baike.baidu.com/item/%E5%BA%94%E7%94%A8%E5%B1%82/16412033?fr=aladdin

Ans：

，， （TBD）

Ans：

，

思考题

TBD

*TBD = to be done

第二章

2.1 插入排序（insertion sort）

伪代码：

for j = 2 ... n:
  key = a[j]
  i = j-1
  while i > 0 and a[i] > key:
    a[i+1] = a[i]
    i = i-1
  a[i+1] = key

C++ 语言实现插入排序

#include <bits/stdc++.h>

using namespace std;

int a[105];

int main()
{
        int n; // length of array
        cin >> n;
        for (int i = 1; i <= n; i++) {
                cin >> a[i]; // input array
        }
        for (int i = 2; i <= n; i++) {
                int key = a[i]; // key := the element that should be sort now
                int j = i-1;
                while (j >= 1 && a[j] >= key) {
                        a[j+1] = a[j];
                        j--;
                }
                a[j+1] = key; // after this, elements from 1~i has been sort from smallest to biggest
        }
        for (int i = 1; i <= n; i++) {
                cout << a[i] << " "; // output the array to check if the process is right
        }
        cout << endl;
        return 0;
}

插入排序原理：
每次将前面k个元素排好序
对于处理前k+1个元素时，由于前面k个元素已经排好序了，因此可以直接将第k+1个元素不断与前面的元素进行比较，如果小的话就将该元素继续向前插入，如果大的话就停止操作，说明前k+1个元素已经从小到大排好序了