私以为寒假学习需要被记录，但是貌似除了做题又不知道该写点什么？

算法杂谈

单词反转

将 "Hello World" 反转为 "olleH dlroW" ，可以通过每次读入时将字母放入栈中，读到空格或换行时再取出来实现。

stack<char> stk;
char ch;

while (1) {
    ch = getchar();
    if (ch == ' ' || ch == '\n' || ch == EOF) {
        while (!stk.empty()) {
            cout << stk.top();
            stk.pop();
        }
        if (ch == '\n' || ch == EOF) break;
        cout << endl;
    } else {
        stk.push(ch);
    }
}

乒乓球产生冠军

题意：有 n 名选手进行乒乓球比赛，每场比赛两人对决，胜者继续比赛，败者淘汰。每场比赛的胜负由两名选手的实力值决定，实力值高者获胜。现给出 n 名选手的实力值，求最终冠军的实力值。

这题可以用图的思想来思考，抑或是一点脑筋急转弯，比如将选手抽象为结点，如果存在环那么必然不可能产生冠军。最终结论是，必须有一个人没输过，不然不可能有冠军。所以，用两个集合分别记录胜者和输者，最后胜者集合中去掉输者集合剩下的即为冠军。如果胜者集数量等于输者集数量，则说明没有冠军产生。

算法题中的排列组合

全排列

求一个数组的全排列，基础是回溯法，时间复杂度可以确定是 $O(n!)$ 。

int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};

int n = sizeof(arr) / sizeof(arr[0]);

int perm(int begin, int end) {
    if (begin >= end) {
        // 排列完成后的操作
        for (int i = 0; i < n; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
        return 1;
    }
    int count = 0;
    for (int i = begin; i < end; i++) {
        swap(arr[begin], arr[i]);
        count += perm(begin + 1, end);
        swap(arr[begin], arr[i]);
    }
    return count;
}

哦对了，你当然也可以使用 std::next_permutation() 函数来解决这个问题。

组合

这个点比较有意思。组合数与二项式系数息息相关，而二项式选或不选的思想又和二进制同根同源。假设待选集合为 $P$ ， $|P|=n$ ，则从中选出 $k$ 个元素的组合数为 $C_n^k$ 。可以用二进制位来表示每个元素是否被选中，1 表示选中，0 表示不选中。这样，从 $0$ 到 $2^n-1$ 的所有二进制数都可以表示所有可能的组合。

int arr[] = {1, 2, 3, 4}; // 我们将集合存在数组中
int n = sizeof(arr) / sizeof(arr[0]);

void print_subset(int n) {
    for (int i = 0; i < (1 << n); i++) { // 遍历从 0 到 2^n - 1
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) { // 检查第 j 位是否为 1
                cout << arr[j] << " "; // 这一次组合中该元素被选中
            }
        }
    }
}

如果我们要求特定大小的组合，比如从集合中选出 $k$ 个元素，可以在内层循环中统计1的个数，只有当计数等于 $k$ 时才输出该组合。

如何统计呢？比如我们有数字 $k$ ， 当我们进行 $k \& (k - 1)$ 的操作，就可以将 $k$ 的二进制表示中最低位的1变为0。重复这个操作直到 $k$ 变为0，就可以统计出1的个数。

int arr[] = {1, 2, 3, 4}; // 我们将集合存在数组中
int n = sizeof(arr) / sizeof(arr[0]);

void print_subset(int n, int k) {
    for (int i = 0; i < (1 << n); i++) { // 遍历从 0 到 2^n - 1
        int count = 0;
        int temp = i;
        while (temp) {
            temp = temp & (temp - 1); // 清除最低位的1
            count++;
        }
        if (count != k) continue; // 只处理包含 k 个元素的组合
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) { // 检查第 j 位是否为 1
                cout << arr[j] << " "; // 这一次组合中该元素被选中
            }
        }
    }
}

操作系统学习

《操作系统导论》（OSTEP）这本书，将OS分为三个内容讲解，虚拟化、并发性和持久性。虚拟化和并发都还算挺直观的，无非就是进程、上下文调度、多线程编程那些东西。

持久性很有意思，讲的是文件系统方面的东西。为什么要叫持久性呢？因为众所周知，RAM是易失性的，一旦断电里面的数据都无法保存，需要保存到磁盘上。磁盘就涉及到文件系统的设计，这其中十分复杂，跟计组课程的部分内容都挂钩，有待学习。

系统设计哲学带来的思考

UNIX的哲学十分有名。KISS准则，即Keep It Simple, Stupid，强调系统设计应尽量简单，避免复杂性带来的问题。其中的pipe就是很典型的例子，保证了每个工具都只负责一小部分内容，通过管道将多个工具连接起来完成复杂任务。

这样的哲学让人十分欣赏，或者说在现在我们很少看到新事物是如此的了。最典型的例子就是AI，深度学习从原理上讲就是一个黑箱，我们永远无法知道其中的哪一层在完成什么任务，只能通过数学（大部分是统计学）来验证其正确性。抑或说它没有正确与否，只有正确率高低之分。

在小红书看到有人吐槽这件事，帖子认为AI的技术永远都是暴力，缺乏设计的美感。下面不少人喷他，认为这就是未来的趋势，算力的增加必然带来系统复杂性的增加，人们无法保证一件事物百分之百的准确，只能通过统计学来对其进行约束。（不得不说看起来像是行业相关从业者的破防）

我的观点似乎也很明确了。我欣赏具有设计、能够掌控的工程。AI跟传统计算机行业的本质已经差的非常多了，我更趋向它处于一个数学与计算机的中间地带，同时也难以理解为什么会有喜欢编程的人去喜欢AI，毕竟编程本身就是将自己的创造控制在自己手中，而不是交给一个黑箱来完成。

对于AI行业，即便去年的发展速度达到了让人瞠目结舌的地步，但是我依旧不看好（硬要说我是因为快要被抢饭碗急了也无所谓）。现在的变现模式依旧过于单一，且训练成本十分夸张，从内存条价格起飞就可以看得出来。如果哪天AI胜利了，或许我会认为计算机输给了数学、输给了物理，但这百分之百是计算机科学的可惜。