3. 简单的基础算法

本章介绍算法学习入门阶段必须掌握的基础算法和经典算法，是复杂算法的基础构件。这些算法虽然基础，但它们都蕴含着算法设计的巧思和智慧，同时也是算法竞赛考试的必考点。本章分为6个部分，每个部分讲解数个经典算法，包括以下内容：

1. 简单数值算法

2. 简单在线统计

3. 简单字符串处理

4. 递归与二分

5. 基础排序算法

6. 基础组合算法与模拟算法

• 3.1. 简单数值算法
  • 3.1.1. 最大公因数与最小公倍数
  • 3.1.2. 和质数相关的基础算法
  • 3.1.3. 回文数专题
  • 3.1.4. 回文质数（USACO1.5；洛谷P1217）
  • 3.1.5. 有理小数的精确表示
  • 3.1.6. 整数快速幂算法（洛谷P1226）
• 3.2. 简单在线统计
  • 3.2.1. 单调区间在线统计
  • 3.2.2. 单调区间问题的应用：两个NOIP提高组复赛题
  • 3.2.3. 最大区间和问题（洛谷P1115）
  • 3.2.4. 前缀和
  • 3.2.5. 差分法（洛谷P3397）
  • 3.2.6. 尺取法（洛谷P1147）
• 3.3. 简单字符串处理
  • 3.3.1. 字符串处理基础知识(I)
  • 3.3.2. 字符串处理基础知识(II)
  • 3.3.3. 字符串处理基础知识(III)
  • 3.3.4. 子串搜索及KMP算法
  • 3.3.5. 回文字符串
  • 3.3.6. C++ string简介
  • 3.3.7. 初识有限自动机：字符串转整数
• 3.4. 递归与二分
  • 3.4.1. 递归法介绍
  • 3.4.2. 经典递归问题：Hanoi塔游戏
  • 3.4.3. Fibonacci数列
  • 3.4.4. 递归与递推例题：数的计算（洛谷P1028）
  • 3.4.5. 二分法基础及二分查找
  • 3.4.6. 二分迭代法求方程根
  • 3.4.7. 一元三次方程求解（洛谷P1024）
  • 3.4.8. 二分法例题：跳石头（洛谷P2678）
  • 3.4.9. 二分法例题：切绳子（洛谷P1577）
  • 3.4.10. 中位数问题
• 3.5. 基础排序算法
  • 3.5.1. 两种简单比较排序方法
  • 3.5.2. 插入排序
  • 3.5.3. 归并排序
  • 3.5.4. 快速排序
  • 3.5.5. 非比较型排序算法
  • 3.5.6. C++算法库排序函数
  • 3.5.7. 复杂规则的排序技巧
  • 3.5.8. 简单建索引算法
• 3.6. 基础组合算法与模拟算法
  • 3.6.1. 排列与组合：数学的概念
  • 3.6.2. 排列组合打表与杨辉三角形
  • 3.6.3. 排列的生成算法(I)
  • 3.6.4. 排列的生成算法(II)
  • 3.6.5. 组合生成算法
  • 3.6.6. 复杂排序技巧：排座椅（洛谷P1056）
  • 3.6.7. 数组环形访问：玩具谜题（洛谷P1563）
  • 3.6.8. 字符串处理：字符串的展开（洛谷P1098）
  • 3.6.9. 查表的技巧：生活大爆炸版石头剪刀布（洛谷P1328）
  • 3.6.10. 查表的技巧：迎春舞会之数字舞蹈（洛谷P1538）