常见算法¶
Warning
该文章仍未经过正式校对
Note
本文作者：username
在掌握了算法复杂度和 STL 的基础知识后，我们来学习几种最基础但非常重要的算法思想。这些算法虽然简单，但在解决实际问题时却非常实用。
打表法¶
打表指的是预先计算出问题所有可能的结果，然后根据需要直接查表得出结果的方法。在日常生活中我们经常看到打表法的影子，例如速算 20 以内乘法的时候我们往往是预先已经记住了"11 × 11 = 121"等结果，而不是每一次都重新计算一遍。
打表严格说来不能算是一个"算法"，因为实际上该方法并没有提供一个解决问题的手段，它只是把计算题做成了填空题。
打表法的特点¶
优势：打表法的时间复杂度非常低，结合哈希表等数据结构，时间复杂度往往可以做到 \(O(1)\)。
缺点：它的空间复杂度往往很大，且实际上在大多数情况下因为可能的解太多了而并不实用，或者计算任务并非人力所能及1。
适用场景：打表往往只在问题规模非常小、问题的解数量非常有限、题目对时间的要求非常高的场景下使用。我们也可以把打表法当作一种"最后的手段"，当我们实在想不出其他更好的算法时，可以考虑打表法。
例题 3.1：阶乘计算¶
题目
给定一个整数 \(n\)，计算 1 到 \(n\) 的阶乘（即 \(1 \times 2 \times 3 \times \cdots \times n\)）。请编写程序，计算并输出结果。
输入：一行，一个整数 \(n\)（\(1 \leq n \leq 20\)）。
输出：一行，一个整数，表示 1 到 \(n\) 的阶乘。
解答¶
理论而言我们可以打表。由于题目中 \(n\) 的范围是 1 到 20，我们可以预先计算出 1 到 20 的阶乘，然后将结果存储在一个数组中。这样，在程序运行时，我们只需要根据输入的 \(n\) 直接查表即可，时间复杂度为 \(O(1)\)。
当然，由于 20 的阶乘是一个非常大的数，已经超出了 int 的范围，因此我们需要使用 long long 来存储结果。
代码疑似有些过于简单了，留作练习。
其他打表方式¶
除了这种朴素的打表，我们还可以使用其他方式来打表，例如：
- 利用程序来辅助打表（如素数表、斐波那契数列等）
- 使用数学方法来推导出结果（如组合数、排列数等）
这些方法往往可以大大减少正常做题的工作量。
模拟算法¶
模拟算法是最简单的算法之一。该算法的含义是通过模拟人类解决问题的实际过程来完成最终的计算任务。该类算法适用于解决问题的步骤非常明确的场景，也是后续许多算法的基础。不严格地说，所有的算法实际上都是模拟算法。
例题 3.2：素数筛法¶
题目
素数在数学中是一个非常重要的概念，它指的是只能被 1 和它本身整除的自然数。素数在密码学、数据加密等领域有着广泛的应用。一般我们可以使用筛法找到素数：在一系列整数中，先找到最小的素数（2），然后将它的倍数都去掉；然后再找到下一个最小的素数（3），再将它的倍数都去掉；如此反复，直到所有的数都被处理完。
请编写一个程序，这个程序接受一些整数，然后输出这些整数是不是素数。
输入：\(m+1\) 行，第一行是一个整数 \(m\)，表示接下来有 \(m\) 个整数需要判断；接下来的 \(m\) 行，每行一个整数 \(n\)。\(n\) 的数值在 0 到 1000 之间。
输出：\(m\) 行，每行一个字符串，表示对应的整数是不是素数。如果是素数，输出"YES"，否则输出"NO"，如果输入的是 1，输出"NA"。
解答¶
该问题的解决步骤非常明确，我们可以直接模拟这个过程。具体来说，我们可以先预处理出 1000 以内的所有素数，然后对于每个输入的整数，直接判断它是否在素数列表中即可。
上述题目给出了一个处理数的方法"筛法"，因此解决问题的步骤非常明确，适合使用模拟算法。
我们知道，数组的索引天然是自然数，非常适宜做这种标记，在筛完之后只需要按索引查询即可；想到"按索引查询"，立刻想到顺序表 vector。于是，我们得以模拟过程，得到如下代码：
vector<int> primes(1001, 1); // 初始化一个大小为 1001 的数组，初始值全为 1
primes[0] = primes[1] = 0; // 0 和 1 不是素数
for (int i = 2; i * i <= 1000; ++i) { // 遍历每个数
if (primes[i]) { // 如果是素数
for (int j = i * i; j <= 1000; j += i) { // 将它的倍数标记为非素数
primes[j] = 0;
}
}
}
这样，我们就得到了一个标记了 1000 以内所有素数的数组。接下来，我们只需要读取输入的整数，然后直接查询这个数组即可。查询部分代码留作练习。
例题 3.3：数学表达式化简¶
题目
给定一个 \(n\)，试着求下列表达式的值：
提示：若 \(i\) 和 \(j\) 取值无关，则有 \(\sum_i \sum_j f(i)g(j) = (\sum_i f(i))(\sum_j g(j))\)
输入：一行，一个整数 \(n\)。
输出：一行，一个整数，表示结果。
解答¶
分析上述题目，如果用双重循环枚举 \(i\) 和 \(j\)，时间复杂度是 \(O(n^2)\)。我们已经知道，\(n\) 的最大值是 998244353，这个数量级的平方显然是无法接受的。我们需要对题目进行分析，推导出一个更高效的计算方法。
另一方面，整数 int 的范围是 \(-2^{31}\) 到 \(2^{31} - 1\)，大约是 -21 亿到 21 亿，而题目中要求的结果显然远远超过了这个范围，因此我们需要使用更大范围的整数类型 long long，该数据类型的范围大约是 -9 万亿到 9 万亿，题目中的结果应该在这个范围内。
所以要求解这个问题，我们可以先将表达式进行展开。展开的过程略，总之最终结果是 \(7n^2(n + 1)^2(2n + 1)\)。直接输出这个结果即可。
代码过于简单，留作练习。
模拟算法的特点¶
有时候，题目并没有直接给出解决问题的步骤，但是我们可以通过分析问题，推导出一个明确的解决步骤，这时也可以使用模拟算法。还有的时候，题目给出的步骤并不高效，我们需要对其进行优化，使其在时间和空间上更加高效。
练习题¶
练习
小 A 正在做一道数学题，需要计算从 1 到 \(n\) 的所有整数的"数字和"。例如，当 \(n=12\) 时，1 到 12 的数字依次为
它们的数字和为
由于 \(n\) 可能很大，小 A 希望你用程序来模拟这个累加过程。
输入：一行，一个正整数 \(n\)（\(1 \leq n \leq 10^6\)）。
输出：一行，一个整数，表示 1 到 \(n\) 所有数字的数字和。
枚举算法¶
枚举算法是通过列举所有可能的解来找到问题的答案。该类算法适用于问题规模较小，或者需要找到所有可能解的场景。因此，枚举算法也叫"暴力"算法。但是由于枚举算法的时间复杂度通常非常高，因此我们往往把它当作一种最后的手段。另外，在枚举的时候，也要尽可能对枚举过程进行优化，来减少枚举的次数。
例题 3.4：百鸡问题¶
题目
公鸡每只 5 元，母鸡每只 3 元，小鸡三只 1 元，100 元钱买 100 只鸡，请问公鸡、母鸡、小鸡各买多少只刚好凑足 100 元钱？请编写程序计算所有可能的购买方案。
输入：无。
输出：每行三个整数，分别表示公鸡、母鸡、小鸡的数量。按公鸡数量从小到大排序输出。
解答¶
该问题实际上可以抽象为以下方程组：
其中，\(x\) 表示公鸡的数量，\(y\) 表示母鸡的数量，\(z\) 表示小鸡的数量。
一个简单的思路是写一个双重循环，枚举公鸡和母鸡的数量，然后计算出小鸡的数量，最后判断是否满足条件。显然，上述题目中公鸡和母鸡的数量都不会超过 20，因此枚举的时间复杂度 \(O(n^2)\) 是可以接受的。
优化枚举¶
当然，如果我们能通过分析，推导出一个更高效的枚举方法，那就更好了。实际上我们发现上述方程组中的 \(z\) 系数是个分数，着实恼人。我们可以将方程组两边同时乘以 3，得到：
这样，我们就可以通过消元法，消去 \(z\) 并进一步化简，得到：
现在，我们只需要枚举 \(x\)，然后计算出 \(y\)，最后计算出 \(z\)，并判断它们是否为非负整数即可。这样，我们的枚举就从双重循环变成了单重循环，时间复杂度从 \(O(n^2)\) 降到了 \(O(n)\)。
更进一步地，把 \(y\) 移到等式右边，我们发现 \(7x\) 必须等于 \(100 - 4y\)，也就是说 \(100 - 4y\) 必须是 7 的倍数，因此我们可以直接以 4 为步长枚举 \(x\)，这样就可以进一步减少枚举的次数。
代码实现如下：
for (int x = 0; x <= 25; x += 4) { // 枚举公鸡数量
int y = (100 - 7 * x) / 4; // 计算母鸡数量
int z = 100 - x - y; // 计算小鸡数量
if (y >= 0 && z >= 0 && (100 - 7 * x) % 4 == 0) { // 判断是否为非负整数
cout << x << " " << y << " " << z << endl; // 输出结果
}
}
练习题¶
练习
给定一个长度为 \(n\) 的正整数序列 \(a_1, a_2, \ldots, a_n\)，请找出其中和为偶数的所有二元组 \((i, j)\) 的数量，其中 \(1 \leq i < j \leq n\)。
输入：第一行一个整数 \(n\) (\(2 \leq n \leq 2000\))。第二行 \(n\) 个空格分隔的正整数 \(a_i\) (\(1 \leq a_i \leq 10^9\))。
输出：一行，一个整数，表示满足条件的二元组个数。
贪心算法¶
贪心算法是一种在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。该类算法适用于问题可以分解为若干子问题，且每个子问题的局部最优解能构成全局最优解的场景。需要注意的是，该算法并不是总能得到最优解，因此我们在使用的时候应当证明其正确性。
例题 3.5：理发师问题¶
题目
有一个理发师要为一群顾客理发。每个顾客都有一个理发时间，理发师希望通过合理安排顾客的理发顺序，使得所有顾客的平均等待时间最小。请编写程序，计算最小的平均等待时间。
输入：第一行一个整数 \(n\)，表示顾客的数量；第二行 \(n\) 个空格分隔的整数，表示每个顾客的理发时间。
输出：一行，一个整数，表示最小的平均等待时间（向下取整）。
解答¶
该问题可以通过贪心算法来解决。我们可以将顾客按照理发时间从小到大排序，然后依次为每个顾客理发。这样，理发时间较短的顾客会先被理发，从而减少了后续顾客的等待时间。
正确性证明¶
上述算法的证明非常简单。不妨设有 \(n\) 个顾客，其理发时间分别为 \(t_1, t_2, \ldots, t_n\)。对于排在第 \(i\) 个顾客，他的等待时间为前面所有顾客的理发时间之和，即：
因此，所有顾客的总等待时间为：
我们可以交换求和顺序，得到：
上述乘积求最小值看起来非常困难。但是我们只需要利用排序不等式：顺序和大于乱序和大于反序和。也就是说，我们只需要将 \(t_j\) 按从小到大排序，就能使得总等待时间最小。
代码实现¶
代码实现如下：
vector<int> times(n); // 输入的理发时间
sort(times.begin(), times.end()); // 按理发时间从小到大排序
int total_wait = 0; // 总等待时间
for (int time : times) {
total_wait += time * (n - 1); // 剩余顾客的总等待时间
n--; // 剩余顾客数量减少
}
int average_wait = total_wait / n; // 计算平均等待时间
练习题¶
练习
你在考试，该考试动态收卷。有 \(n\) 个题目，第 \(i\) 个题目需要耗时 \(t_i\) 分钟，必须在第 \(d_i\) 分钟之前完成（\(t_i \leq d_i\)）。你一次只能做 1 个题，且中途不能中断。你最多可以做完多少题目？
输入：第一行一个整数 \(n\) (\(1 \leq n \leq 10^5\))。接下来 \(n\) 行，每行两个整数 \(t_i, d_i\) (\(1 \leq t_i \leq d_i \leq 10^9\))。
输出：一行，一个整数，表示最多能完成的题目数量。
总结¶
本章介绍了四种基本的算法思想：
- 打表法：预先计算所有结果，直接查表。适用于问题规模小、解数量有限的场景。
- 模拟算法：按照问题描述的步骤逐步模拟执行。是最直观的算法思想。
- 枚举算法：列举所有可能的解，找到满足条件的答案。虽然简单但效率较低，需要尽可能优化。
- 贪心算法：每一步都做出局部最优选择，希望得到全局最优解。需要证明正确性。
这些算法思想虽然简单，但在实际问题中非常实用。特别是要注意：
- 打表法要考虑空间复杂度
- 模拟算法要确保理解问题的本质
- 枚举算法要尽可能优化，减少枚举次数
- 贪心算法要证明局部最优能推导出全局最优
掌握这些基础算法思想后，我们就可以解决更多实际问题了。在后续章节中，我们将学习更多高级的算法和数据结构。
-
当然，如果你能做到拉马努金"有人托梦给我"然后直接出答案的水平，那就另当别论了。 ↩