九、常用基础算法

绿色：需要掌握了解；红色：需要会写会用或很重要。

本章节主要是写一些基础算法，一般运用在模拟类型的题目。

图形输出

此类题目都是模拟输出图形，可以1）观察其规律而后按行列循环输出，或者2）空间换时间创建二维数组给值后输出。一般情况下使用方法2）的代码容易编写，但空间复杂度略高（数据规模小时放心用）。

常见题型有：杨辉三角形及其变体、打印沙漏、矩阵输入输出等。

暴力枚举（下称爆破）

在章节三、C++11标准库准备知识中，有提及判断算法是否会超时的办法，即设计的算法执行运算的次数不能超过10^8。因此，当判断运算次数不会超过10^8且没有优化的需求时，大胆爆破。

例如：

①N是绝对值小于1e4的整数时，设计的时间复杂度O(N²)的算法（10^8<=10^8）；

②N是绝对值小于5e2的整数时，设计的时间复杂度O(N³)的算法（1.25*10^8≈10^8，实际有点风险）。

个别情况需要读者酌情考虑是否使用暴力枚举，在此不多赘述。

打表

打表是常见的空间换时间行为，即把已经算过的值存起来便于下次使用，在递归的迭代写法和动态规划算法中都可能运用到。本质是一种便于查询使用和减少计算、降低总体时间复杂度的方法。例如分解2-N的质因数时，不需要对于每个N都从2~sqrt(N)循环分解，可以先计算出2到最大范围的平方根的数的质数表，便于计算。

进制转换

①十进制转为R进制（除基数取余数法的do-while形式）

②R进制转十进制

③R1进制转R2进制（R1进制转十进制，再十进制转R2进制即可，代码就上面俩函数搁一起）

注：若转换得到的数的位数超过最大整型类型long long能容纳的范围，即大数转换（本质是大数的乘除法算法）。

二分查找

1.标准库的二分查找函数：lower_bound、upper_bound、equal_range、binary_search。

2.自己实现binary_search（升序序列查找x的位置）：

lower_bound（非递减序列查找第一个大于等于x的位置）实现：