第1章 初等数论

1.1 基本概念与性质

1.1.1 整除

定义：设a、b为整数，且b≠0，若存在整数k使得a=b×k，则称b整除a（或a能被b整除），记作b|a。

重要性质：

1. 若a|b且b|c，则a|c（传递性）
2. 若a|b且a|c，则对任意整数m、n，有a|(m×b+n×c)
3. 若a|b且b|a，则a=±b

1.1.2 素数与合数

素数（质数）：大于1的整数，若除了1和自身外没有其他正约数，则称为素数；

• 2是唯一的偶素数
• 重要：1既不是素数也不是合数

算术基本定理：任何大于1的整数都能分解为素数的乘积

1.1.3 最大公约数与最小公倍数

• 最大公约数（GCD）：同时整除a和b的最大正整数，记作gcd(a,b)
  • **重要性质：**gcd(a,b) = gcd(b, a mod b) ← 辗转相除法理论基础
  • 互质：若gcd(a,b)=1，则称a和b互质
• 最小公倍数（LCM）：同时是a和b的倍数的最小正整数
  • **重要公式：**a×b = gcd(a,b)×lcm(a,b)

1.2 核心算法与实现

1.2.1 辗转相除法（欧几里得算法）

原理：辗转相除法通过反复用较小的数除较大的数，直到余数为0，此时的除数即为最大公约数；

迭代版本：

/*
 * 使用辗转相除法（欧几里得算法）计算两个整数的最大公约数
 * 算法原理：gcd(a,b) = gcd(b, a mod b)
 * 通过反复用较小数除较大数，直到余数为0，此时的除数即为最大公约数
 * @param a 第一个整数（非负）
 * @param b 第二个整数（非负）
 * @return a和b的最大公约数
*/
int gcd(int a, int b) {
    // 循环直到余数为0
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;       
        // 示例跟踪（以gcd(48,18)为例）：
        // 第1轮：a=48, b=18 → temp=18, b=48%18=12, a=18
        // 第2轮：a=18, b=12 → temp=12, b=18%12=6, a=12  
        // 第3轮：a=12, b=6  → temp=6,  b=12%6=0,  a=6
        // 第4轮：b=0，循环结束，返回a=6
    }
    // 当b=0时，a就是最大公约数
    return a;
}

递归版本：

// 递归版本辗转相除法
int gcdRecursive(int a, int b) {
    if (b == 0) return a;          // 基准情况：余数为0，返回a
    return gcdRecursive(b, a % b); // 递归调用：gcd(a,b) = gcd(b, a%b)
}

1.2.2 最小公倍数计算

原理：利用公式 ( \text{lcm}(a, b) = (a \times b)/\text{gcd}(a, b) )，注意先乘后除可能导致溢出，建议调整计算顺序。

int lcm(int a, int b) {
    return a / gcd(a, b) * b;  // 先除后乘，避免溢出
}

1.2.3 素数判定（试除法）

判断一个数 n 是否为素数，只需检查其能否被 2 到 (\sqrt{n}) 之间的任意整数整除。

bool isPrime(int n) {
   	//特殊情况
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;//偶数一定不是素数
  	
    for (int i = 3; i * i <= n; i += 2) {// 只检查奇数
        if (n % i == 0) return false;
    }
    return true;
}

1.2.4 埃氏筛法

算法原理： 埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种高效筛选素数的经典算法。其核心思想是从小到大遍历所有数字，对于每个素数，标记它的所有倍数为合数，这样剩下的未被标记的数字就是素数。

算法步骤：

1. 创建一个长度为n+1的布尔数组，初始全部标记为true（素数）
2. 0和1不是素数，直接标记为false
3. 从2开始遍历到√n：
   • 如果当前数字p是素数（未被标记为false）
   • 从p²开始，将所有p的倍数标记为合数（false）

为什么从p²开始标记？ 因为比p²小的p的倍数（如2p, 3p, ..., (p-1)p）已经被更小的素数标记过了。

时间复杂度： O(n log log n)

代码实现：

bool isPrime[100100];
void sieveOfEratosthenes(int n) {
  
  	memset(isPrime,true,sizeof(isPrime));
  
    isPrime[0] = isPrime[1] = false; // 0和1不是素数
    
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) { // 如果i是素数
            // 从p²开始，标记p的所有倍数为合数
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

1.2.5 线性筛法（欧拉筛法）

算法原理： 线性筛法（又称欧拉筛法）是一种比埃氏筛法更高效的素数筛选算法，时间复杂度为 O(n)。其核心思想是确保每个合数只被其最小质因数筛除一次，避免了重复标记，从而提升了效率。

关键改进：

• 埃氏筛法中，合数可能被多个质数重复标记（如6会被2和3都标记）
• 线性筛法中，每个合数只被其最小质因数标记一次

算法步骤：

1. 维护一个素数列表 primes，用于存储已找到的素数
2. 创建标记数组 isComposite，记录每个数是否为合数
3. 遍历整数 i 从 2 到 n：
   • 如果 i 未被标记为合数，则 i 是素数，加入素数列表
   • 遍历素数列表中的每个素数 p：
     • 如果 i × p > n，停止循环（超出范围）
     • 标记 i × p 为合数（此时 p 是 i × p 的最小质因数）
     • 关键步骤：如果 i 能被 p 整除，停止当前循环（避免后续素数重复标记）

为什么需要提前终止？ 当 i 能被 p 整除时，说明 p 是 i 的最小质因数。如果不终止循环，后续的素数 p' 会标记 i × p'，但此时 i × p' 的最小质因数应该是 p 而不是 p'，这会导致重复标记。

时间复杂度： O(n)

int x=0;
bool primes[100001000];
int isComposite[100001000];
void f(int n){
	//1、数组初始化
	memset(primes,true,sizeof(primes));
	primes[1]=0;
	for(int i=2;i<=n;i++){
		//2.判断当前数字是不是质数
		if(primes[i]) isComposite[x++]=i;
		//3.当前数字与数组里面的质数相结合
		for(int j=0;j<x && isComposite[j]*i<=n ;j++){
			//4.排除合数
			primes[i*isComposite[j]]=false;
			//5.判断当前数字能否整除当前质数
			if(i%isComposite[j]==0) break; 
		} 
	} 
}

优势：

1. 相比埃氏筛法，线性筛法不会重复标记合数（如 6 在埃氏筛中会被 2 和 3 分别标记，而线性筛中仅被最小质因数 2 标记），因此效率更高，尤其适合大规模数据（如 n=10^7 及以上）。
2. 可同时记录每个数的最小质因数，便于后续分解质因数等操作。

1.2.6 分解质因数

**原理：**将一个正整数分解为若干素数的乘积（算术基本定理）。

1. 步骤1：理解质因数分解

   • 质因数分解是将一个正整数分解为若干个质数相乘的形式

   • 例如：12 = 2 × 2 × 3

2. 步骤2：确定算法思路

   • 从最小的质数2开始，尝试将输入的数n进行分解

   • 对每个可能的因数i（从2到√n），如果n能被i整除，则i是一个质因数

   • 重复将n除以i，直到n不能被i整除

   • 如果最后n>1，说明剩下的n本身也是一个质因数

#include<bits/stdc++.h>
using namespace std;

int arr[100100];  // 存储质因数的数组
int x = 0;        // 记录质因数的个数

int main(){
    int n;
    cin >> n;      // 输入要分解的正整数
    
    // 从2开始遍历到sqrt(n)，寻找质因数
    for(int i = 2; i * i <= n; i++){
        // 当n能被i整除时，i就是n的一个质因数
        while(n % i == 0){
            arr[x++] = i;  // 将质因数i存入数组
            n /= i;        // 更新n的值，去除已找到的质因数
        }
    }
    
    // 如果最后n不等于1，说明剩下的n本身也是一个质因数
    if(n != 1) {
        arr[x++] = n;
    }
    
    // 输出所有的质因数
    for(int i = 0; i < x; i++){
        cout << arr[i] << ' ';
    }
    
    return 0;
}

1.3 同余与模运算

1.3.1 同余的定义

定义：若整数a和b除以m的余数相同，则称a与b模m同余，记作 a ≡ b (mod m)，即 m | (a - b)。 样例： 假设我们取模数 m = 5，考虑两个整数 a = 7 和 b = 12。

• 计算余数：
  • 7 ÷ 5 = 1 余 2
  • 12 ÷ 5 = 2 余 2
• 由于余数相同（都是2），因此 7 ≡ 12 (mod 5)。
• 验证 m | (a - b)：
  • a - b = 7 - 12 = -5
    • 5 | (-5)（因为 -5 ÷ 5 = -1，整除成立）。

这个例子表明，7和12在模5下是同余的，因为它们除以5的余数相同，且它们的差能被5整除。

1.3.2 模运算的性质

基本性质：

• 加法：(a + b) mod m = [(a mod m) + (b mod m)] mod m
• 减法：(a - b) mod m = [(a mod m) - (b mod m) + m] mod m （加m避免负数）
• 乘法：(a × b) mod m = [(a mod m) × (b mod m)] mod m
• 幂运算：(a^b) mod m = 可通过快速幂算法高效计算

快速幂（模幂运算）：

1. 核心思想

   快速幂算法通过指数二进制分解和幂次平方的方法，将幂运算的时间复杂度从O(n)优化到O(log n)。

2. 数学原理

   对于计算 a^b，我们可以将指数b表示为二进制形式：

   ​ b = bₖ × 2ᵏ + bₖ₋₁ × 2ᵏ⁻¹ + ... + b₁ × 2¹ + b₀ × 2⁰ 那么：

   ​ a^b = a^(bₖ×2ᵏ + bₖ₋₁×2ᵏ⁻¹ + ... + b₀×2⁰)= a^(bₖ×2ᵏ) × a^(bₖ₋₁×2ᵏ⁻¹) × ... × a^(b₀×2⁰)

3. 算法优势

• 时间复杂度：O(log b)
• 空间复杂度：O(1)
• 特别适合大数幂运算和模幂运算

/**
 * 快速幂算法计算 a^b
 * @param ds 底数 (base)
 * @param zs 指数 (exponent)
 * @return a^b 的结果
 */
long long f(long long ds, long long zs) {
    long long res = 1;        // 初始化结果为1（任何数的0次方为1）
    
    // 当指数大于0时继续循环
    while (zs > 0) {
        // 如果当前指数是奇数，将当前底数乘入结果
        // 这对应二进制表示中当前位为1的情况
        if (zs % 2 == 1) {
            res = res * ds;   // 将当前底数乘入最终结果
        }
        
        // 底数平方，为处理下一个二进制位做准备
        // 这相当于将指数除以2（右移一位）
        ds = ds * ds;
        
        // 指数除以2（向下取整），相当于右移一位
        zs = zs / 2;
    }
    
    return res;  // 返回最终结果
}

1.3.3 同余方程简介

最简单的同余方程为 ax ≡ b (mod m)：

• 有解条件：gcd(a,m) | b
• 唯一解条件：当gcd(a,m)=1时，方程有唯一解 x ≡ a^(-1) × b (mod m)

---

1.4 常用数论定理

1.4.1 算术基本定理

​ 任何大于1的整数n都可以唯一分解为有限个素数的乘积；

1.4.2 唯一分解定理

定理表述：

对于任意整数 n > 1，存在唯一的素数序列 p₁ < p₂ < ... < pₖ 和正整数序列 k₁, k₂, ..., kₖ，使得：

$$n = p_1^{k_1} \times p_2^{k_2} \times \cdots \times p_m^{k_m} $$

这种分解称为 n的标准素因数分解式。

重要应用场景：

1. 最大公约数与最小公倍数计算

若a和b的素因数分解式为：

$$a = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k} $$$$b = p_1^{b_1} \times p_2^{b_2} \times \cdots \times p_k^{b_k} $$

则：

$$\text{gcd}(a,b) = p_1^{\min(a_1,b_1)} \times p_2^{\min(a_2,b_2)} \times \cdots \times p_k^{\min(a_k,b_k)} $$$$\text{lcm}(a,b) = p_1^{\max(a_1,b_1)} \times p_2^{\max(a_2,b_2)} \times \cdots \times p_k^{\max(a_k,b_k)} $$

2. 判断数的性质

• 完全平方数判定：检查素因数分解式中所有指数是否为偶数

3. 因数个数计算

若n的素因数分解式为

$$n = p_1^{k_1} \times p_2^{k_2} \times \cdots \times p_m^{k_m} $$

则n的正因数个数为：

$$d(n) = (k_1 + 1) \times (k_2 + 1) \times \cdots \times (k_m + 1) $$

4. 分数化简

​ 对分数a/b，通过分解素因数，消去共同素因数的最小指数部分，得到最简分数。

示例：

• 对于 a = 12 = 2² × 3¹，b = 18 = 2¹ × 3²：

  • gcd(12,18) = 2¹ × 3¹ = 6

  • lcm(12,18) = 2² × 3² = 36

  • 12的因数个数 = (2+1) × (1+1) = 6（因数为1,2,3,4,6,12）

1.4.3 欧拉定理

1. 定理表述：

   若 a 与 m 互质（即 gcd(a, m) = 1），则：

   $$a^{\phi(m)} \equiv 1 \pmod{m}$$

2. 符号说明：

   • a：与模数 m 互质的整数
   • m：模数（正整数）
   • φ(m)：欧拉函数，表示 1~m 中与 m 互质的整数个数
   • ≡：同余符号
   • mod m：模 m 运算

3. 欧拉函数 φ(m) 的计算：

   • 如果 m 是素数，则 φ(m) = m - 1
   • 如果 m = pᵏ（p 是素数），则 φ(m) = pᵏ - pᵏ⁻¹
   • 如果 m = m₁ × m₂，且 gcd(m₁, m₂) = 1，则 φ(m) = φ(m₁) × φ(m₂)

4. 示例：

   计算 7¹² mod 15：

   • gcd(7, 15) = 1，满足欧拉定理条件
   • φ(15) = φ(3)×φ(5) = 2×4 = 8
   • 7⁸ ≡ 1 (mod 15)
   • 7¹² = 7⁸⁺⁴ = 7⁸ × 7⁴ ≡ 1 × 7⁴ (mod 15)
   • 7² = 49 ≡ 4 (mod 15)
   • 7⁴ = (7²)² ≡ 4² = 16 ≡ 1 (mod 15)

1.4.4 费马小定理

1. 定理表述

   若 p 为素数，且 a 不被 p 整除（即 p ∤ a），则：

   $$a^{p-1} \equiv 1 \pmod{p}$$

2. 与欧拉定理的关系

   费马小定理是欧拉定理的特例：

   • 当 m 为素数 p 时，φ(p) = p - 1
   • 因此欧拉定理变为：aᵖ⁻¹ ≡ 1 (mod p)

3. 示例

   计算 2¹⁰ mod 11：

   • 11 是素数，且 11 ∤ 2
   • 根据费马小定理：2¹⁰ ≡ 1 (mod 11)
   • 验证：2¹⁰ = 1024，1024 ÷ 11 = 93 余 1

4. 应用

   • 素数测试：如果一个数不满足费马小定理，则它一定是合数
   • 模逆元计算：在模素数 p 下，a 的逆元是 aᵖ⁻²
   • 密码学：RSA 加密算法的基础

---

1.5 注意事项

1. 数据溢出

   • 数论计算常涉及大数乘法或幂运算
   • 必须使用long long等类型避免溢出
   • 即使a和b为int型，a×b的结果也可能超过int范围

2. 边界处理

   • 注意特殊值（0、1、2）的处理
   • 0不能作为除数
   • 1不是素数

3. 效率选择

   • 素数判定和筛选需根据数据规模选择算法
   • 小规模用试除法
   • 大规模用筛法

4. 模运算符号处理

   • C++中负数的模运算结果为负数（如-5％3＝-2）

   • 需调整为正数：加模后再模

   • 正确写法：(a % m + m) % m

第 2 章 数组模拟高精度计算

​ 在 C 和 C++语言中，基本数据类型（如 int、long long）能表示的整数范围有限（例如 int 型通常最大为 2147483647），当需要处理超出此范围的大整数（如几百位甚至几千位的整数）时，就需要借助数组来模拟高精度计算。数组模拟高精度计算的核心思想是用数组的每个元素存储大整数的一位数字，通过模拟人工计算的方式实现加、减、乘、除等运算。

2.1 高精度计算的基本概念

2.1.1 大整数的存储

由于大整数的位数远超基本数据类型的表示范围，因此需要用数组来存储： 存储方式：通常将大整数的每一位数字存储在数组的一个元素中，且为了方便计算（如进位、借位），低位数字存储在数组的低位索引处（即数组下标越小，对应大整数的位越靠右）。

例如，大整数12345在数组中的存储形式为：

• arr[0] = 5（个位）

• arr[1] = 4（十位）

• arr[2] = 3（百位）

• arr[3] = 2（千位）

• arr[4] = 1（万位）

​ 数组长度为5（表示5位数字）。 输入与转换：大整数通常以字符串形式输入，需要将字符串中的每个字符转换为对应的数字后，按上述存储方式存入数组。

// 示例：字符串"12345"转换为数组的过程
string s = "12345";
int arr[1000];
int len = s.size();
for (int i = 0; i < len; i++) {
    arr[i] = s[len - 1 - i] - '0'; // 逆序存储
}

2.1.2 高精度计算的特点

• 运算规则：完全模拟人工计算过程，包括进位（加法、乘法）和借位（减法）；
• 数组长度：运算结果的位数可能比原数多（如999+1=1000，位数增加1），因此数组需要预留足够的空间；
• 符号处理：对于负数参与的运算，通常先处理符号，再对绝对值进行相应运算；

2.2 高精度加法

高精度加法适用于两个非负大整数相加，核心是模拟竖式加法，处理进位。

2.2.1 算法步骤

• 初始化：创建结果数组，长度为两个加数的最大位数加 1（预留进位空间）。
• **逐位相加：**从数组的第0位（最低位）开始，将两个加数对应位的数字与进位相加，得到当前位的和。
• 处理进位：当前位的和除以10的高为新的进位，余数为结果数组当前位的数字。
• **处理最高位进位：**若所有位相加后仍有进位，需将进位存入结果数组的最高位。
• **确定结果长度：**根据结果数组的有效位数（去除前导零）确定最终长度。

2.2.2 代码示例

#include <bits/stdc++.h>
using namespace std;

int main() {
    // ① 使用string字符串保存输入的大整数
    string s1, s2;
    cin >> s1 >> s2;
    
    // ② 将字符串s1、s2的每个字符转换为对应的整数，倒序保存在两个int数组中
    int a[1005] = {0}, b[1005] = {0}, c[1005] = {0};
    int la = s1.size(), lb = s2.size();
    
    for(int i = 0; i < la; i++)
        a[la - i - 1] = s1[i] - '0';
    for(int i = 0; i < lb; i++)
        b[lb - i - 1] = s2[i] - '0';
    
    // ③ 进行计算，利用数组c保存计算结果
    int lc = max(la, lb);
    for(int i = 0; i < lc; i++) {
        c[i] += a[i] + b[i];
        if(c[i] >= 10) {
            c[i + 1] = 1;
            c[i] -= 10;
        }
    }
    
    // ④ 判断最高位进位
    if(c[lc] > 0) lc++;
    
    // ⑤ 倒序输出
    for(int i = lc - 1; i >= 0; i--)
        cout << c[i];
    
    return 0;
}

2.3 高精度减法

高精度减法适用于两个非负大整数相减（需确保被减数大于或等于减数），核心是模拟竖式减法，处理借位。

2.3.1 算法步骤

• **比较大小：**先判断被减数是否大于或等于减数，若不是，需交换两数并记录结果符号为负（此处仅讨论被减数大于等于减数的情况）;
• **初始化：**创建结果数组，长度为被减数的位数;
• **逐位相减：**从数组的第0位（最低位）开始，用被减数对应位的数字减去减数对应位的数字，若被减数当前位于减数当前位置，需向高位借位（借1当10）;
• **处理借位：**借位后，被减数高位数字减1，当前位数字加10后再减;
• **去除前导零：**结果数组可能存在前导零（如1000-999=1，结果数组前三位为0），需去除前导零后确定结果长度。

2.3.2 代码示例

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 1. 使用string字符串保存输入的大整数
    string s1, s2;
    cin >> s1 >> s2;
    
    // 2. 寻找更大的那个数字，如果s2>s1,交换数据，并展示一个负号
    bool negative = false;
    if(s2.size() > s1.size() || (s2.size() == s1.size() && s2 > s1)) {
        swap(s1, s2);
        negative = true;
    }
    
    // 3. 将字符串s1、s2的每个字符转换为对应的整数，倒序保存在两个int数组中
    int a[1005] = {0}, b[1005] = {0}, c[1005] = {0};
    int la = s1.size(), lb = s2.size();
    
    for(int i = 0; i < la; i++)
        a[la - i - 1] = s1[i] - '0';
    for(int i = 0; i < lb; i++)
        b[lb - i - 1] = s2[i] - '0';
    
    // 4. 进行减法计算
    int lc = la; // 结果长度初始化为较大数的长度
    for(int i = 0; i < lc; i++) {
        if(a[i] < b[i]) {
            a[i] += 10;
            a[i + 1]--;
        }
        c[i] = a[i] - b[i];
    }
    
    // 5. 去除数组前方多余的0，但是至少保留一个数字
    while(lc > 1 && c[lc - 1] == 0) {
        lc--;
    }
    
    // 6. 展示结果
    if(negative) {
        cout << "-";
    }
    for(int i = lc - 1; i >= 0; i--) {
        cout << c[i];
    }
    
    return 0;
}

2.4 高精度乘法

高精度乘法适用于一个非负大整数与一个较小整数（或另一个大整数）相乘。此处介绍大整数乘以小整数的情况（大整数乘大整数原理类似，但复杂度更高）。

2.4.1 算法步骤

• **初始化：**创建结果数组，长度为被乘数的位数加小整数的位数（预留进位空间）。
• **逐位相乘：**从被乘数的最低位（数组第0位）开始，用被乘数当前位的数字乘以小整数，再加上进位，得到当前位的积。
• **处理进位：**当前位的积除以10的商为新的进位，余数为结果数组当前位的数字。
• **处理最高位进位：**所有位相乘后，若仍有进位，需将进位逐位存入结果数组的高位。
• **去除前导零：**确定结果的有效位数。

2.4.2 代码示例

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 1. 使用string字符串保存输入的大整数
    string s1, s2;
    cin >> s1 >> s2;
    
    // 2. 将字符串s1、s2的每个字符转换为对应的整数，倒序保存在两个int数组中
    int a[1005] = {0}, b[1005] = {0}, c[2005] = {0}; // 乘积的最大长度是la+lb
    int la = s1.size(), lb = s2.size();
    
    for(int i = 0; i < la; i++)
        a[la - i - 1] = s1[i] - '0';
    for(int i = 0; i < lb; i++)
        b[lb - i - 1] = s2[i] - '0';
    
    // 3. 进行计算，利用数组c保存计算结果
    for(int i = 0; i < la; i++) {
        for(int j = 0; j < lb; j++) {
            c[i + j] += a[i] * b[j]; // 累加到对应位置
            c[i + j + 1] += c[i + j] / 10; // 处理进位
            c[i + j] %= 10; // 保留个位数
        }
    }
    
    // 4. 确定结果长度，去除前导零
    int lc = la + lb; // 乘积的最大可能长度
    while(lc > 1 && c[lc - 1] == 0) {
        lc--;
    }
    
    // 5. 倒序输出
    for(int i = lc - 1; i >= 0; i--) {
        cout << c[i];
    }
    
    return 0;
}

2.4.3 大整数乘大整数

大整数乘大整数的原理是将其中一个数的每一位与另一个数的每一位相乘，再将所有部分积相加（考虑位权），步骤如下：

• 用数组a存储第一个大整数，数组b存储第二个大整数。
• 结果数组res的长度为lenA + lenB。
• 对于a[i]（第i位）和b[j]（第j位），其乘积对res[i+j]的贡献为a[i] * b[j]，累加后处理进位。

2.5 高精度除法

高精度除法适用于一个非负大整数（被除数）除以一个非负整数（除数，除数不为0），得到商和余数。核心是模拟人工竖式除法的过程，逐位求出商的每一位数字。

2.5.1 算法步骤

• 初始化：
  • 将被除数以字符串形式输入，转换为数组存储（逆序存储，即数组下标0对应被除数的最低位）。
  • 定义商数组和余数变量，商数组的长度与被除数数组长度相同（最多相差1位）。
• 逐位计算商：
  • 从被除数的最高位（数组的最后一位）开始，将当前位数字与上一步的余数乘以10相加，得到当前的被除数部分。
  • 用当前被除数部分除以除数，得到的商即为商数组当前位的数字，余数更新为当前被除数部分除以除数的余数。
  • 依次处理被除数的每一位，直到所有位都处理完毕。
• 去除商的前导零：
  • 商数组可能存在前导零（如被除数小于除数时，商为0），需要去除前导零以得到正确的商。
• 结果转换：
  • 将商数组转换为字符串形式，作为最终的商；余数即为除法运算的余数。

2.5.2 代码示例

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;

// 比较两个数的大小，a >= b 返回true
bool compare(int a[], int b[], int la, int lb) {
    if(la != lb) return la > lb;
    for(int i = la - 1; i >= 0; i--) {
        if(a[i] != b[i]) return a[i] > b[i];
    }
    return true;
}

// 高精度减法，用于除法中的减法操作
void subtract(int a[], int b[], int &la, int lb) {
    for(int i = 0; i < la; i++) {
        if(a[i] < b[i]) {
            a[i] += 10;
            a[i + 1]--;
        }
        a[i] -= b[i];
    }
    
    // 更新a的长度
    while(la > 1 && a[la - 1] == 0) {
        la--;
    }
}

int main() {
    // 1. 使用string字符串保存输入的大整数
    string s1, s2;
    cin >> s1 >> s2;
    
    // 特殊情况处理：除数为0
    if(s2 == "0") {
        cout << "Error: Division by zero" << endl;
        return 0;
    }
    
    // 2. 将字符串转换为整数数组并倒序存储
    int a[1005] = {0}, b[1005] = {0}, c[1005] = {0};
    int la = s1.size(), lb = s2.size();
    
    for(int i = 0; i < la; i++)
        a[la - i - 1] = s1[i] - '0';
    for(int i = 0; i < lb; i++)
        b[lb - i - 1] = s2[i] - '0';
    
    // 3. 高精度除法计算
    int lc = max(la - lb + 1, 1); // 商的最大可能长度
    
    // 将被除数复制到临时数组
    int temp[1005] = {0};
    memcpy(temp, a, sizeof(temp));
    int ltemp = la;
    
    for(int i = lc - 1; i >= 0; i--) {
        // 将除数b左移i位
        int shifted_b[1005] = {0};
        for(int j = 0; j < lb; j++) {
            shifted_b[j + i] = b[j];
        }
        int lshifted = lb + i;
        
        // 试商
        while(compare(temp, shifted_b, ltemp, lshifted)) {
            c[i]++; // 商加1
            subtract(temp, shifted_b, ltemp, lshifted); // 被除数减去除数
        }
    }
    
    // 4. 去除商的前导零
    while(lc > 1 && c[lc - 1] == 0) {
        lc--;
    }
    
    // 5. 输出商
    for(int i = lc - 1; i >= 0; i--) {
        cout << c[i];
    }
    
    return 0;
}

2.5.3 大整数除以大整数

大整数除以大整数的原理更为复杂，基本思路是通过多次减法来逼近商：

1. 比较被除数和除数的大小
2. 确定商的最高位：估算被除数包含多少个除数
3. 用被除数减去除数与该数字的乘积，得到新的被除数
4. 重复步骤2-3，依次求出商的每一位数字

这种方法实现难度较大，需要结合高精度减法和高精度乘法。

2.6 高精度计算的注意事项

• 数组大小：需根据题目中最大可能的数字位数定义数组大小，避免越界
• 前导零处理：减法、乘法和除法的结果可能存在前导零，必须去除（除非结果本身为0）
• 特殊情况：处理0参与的运算，简化计算步骤
• 效率优化：对于超长数字，可采用分段存储减少运算次数

第3章 动态数组

​ 动态数组（Dynamic Array）是一种在程序运行时可以灵活调整大小的数组结构，它克服了静态数组（编译时确定大小）的局限性，能够根据实际需求动态分配和释放内存。动态数组是处理不确定规模数据的重要工具。

3.1 动态数组的基本概念

3.1.1 定义

​ 动态数组是指在程序运行期间通过内存分配函数（如C语言的malloc、realloc、C++的new、delete[]）创建的数组，其大小可以在运行时根据需要进行调整（扩容或缩容），无需在编译时预先确定。

3.1.2 与静态数组的对比

特性	静态数组	动态数组
大小确定时机	编译时	运行时
内存分配方式	栈内存（局部变量）或全局内存	堆内存
大小调整	不可调整，大小固定	可通过重新分配内存调整
内存释放	自动释放（局部变量在作用域结束时）	需手动释放，否则内存泄漏
适用场景	数据规模已知且固定	数据规模未知或动态变化

例如：

• 静态数组：int arr[10];（大小固定为10）
• 动态数组：int* arr = new int[n];（n为运行时确定的变量）

3.1.3 核心优势

• 灵活性：可根据实际数据量分配内存，避免内存浪费或容量不足
• 扩展性：支持在程序运行时动态扩容，适应数据量增长
• 内存利用率：仅在需要时分配内存，减少闲置内存占用

3.3 C++中的动态数组操作

C++既支持C语言的动态内存函数，还提供了更安全的new和delete[]运算符，以及标准库容器std::vector。

3.3.1 使用new和delete[]

创建动态数组：

int n = 5;
int* arr = new int[n];      // 分配n个int的内存（未初始化）
// 或初始化为0: int* arr = new int[n]();

释放内存：

delete[] arr;        // 释放动态数组（必须使用delete[]，而非delete）
arr = nullptr;       // 避免野指针

异常处理：

int* arr = new (std::nothrow) int[n]; // 失败时返回NULL
if (arr == nullptr) {
    // 错误处理
}

重要提醒：必须用delete[]释放new[]创建的数组，否则会导致未定义行为。

3.3.2 使用vector（推荐）

vector是C++标准库提供的动态数组容器，自动管理内存，是实际应用中的首选。

基本用法：

#include<bits/stdc++.h>
using namespace std;

int main(){
		
	// 创建初始大小为n的vector（元素类型为int，初始值为0）
	int n = 5;
	vector<int> arr(n, 0); // 第二个参数为初始值（可选）
	
	// 动态添加元素（自动扩容）
	arr.push_back(10); // 在末尾添加元素10
	arr.push_back(20);
	
	// 访问元素
	int first = arr[0];        // 下标访问（无越界检查）
	int last = arr.at(2);      // at()方法（有越界检查，抛出out_of_range异常）
	
	// 获取大小和容量
	int size = arr.size();     // 实际元素个数
	int capacity = arr.capacity(); // 当前分配的内存可容纳的元素个数
	return 0;
}

调整大小和容量：

arr.resize(8);     // 调整元素个数为8（新增元素默认初始化为0）
arr.reserve(10);   // 预留至少10个元素的容量（不改变元素个数）
arr.clear();       // 清空元素（不释放内存）

// 释放多余内存（仅保留必要容量）
vector<int>(arr).swap(arr);

vector的优势：

• 自动内存管理：避免内存泄漏和野指针；
• 丰富接口：提供push_back、pop_back、resize等便捷操作；
• 迭代器支持：便于遍历和算法操作（如sort）；

3.4 动态数组的扩容策略

动态数组扩容时，需要重新分配更大的内存，复制原数据到新内存，再释放原内存。

常见扩容策略：

策略类型	工作原理	优点	缺点
固定大小增长	每次扩容增加固定数量元素（如每次+10）	内存分配次数少	可能导致较多内存浪费
倍数增长	每次扩容为当前容量的固定倍数（如1.5倍或2倍）	平衡内存浪费和复制开销，均摊时间复杂度O(1)	短期内可能有一定内存闲置

示例分析：容量为n的数组按2倍扩容时，新容量为2n，复制n个元素到新内存。通过均摊分析，每次插入操作的时间复杂度为O(1)。

3.5 常见问题与注意事项

3.5.1 内存泄漏

问题：动态数组使用完毕后未释放内存 避免方法：

• 确保free或delete[]与分配函数配对使用
• C++中优先使用vector

3.5.2 野指针

问题：指针指向的内存被释放后，继续使用该指针 避免方法：释放内存后立即将指针设为NULL（C）或nullptr（C++）

3.5.3 越界访问

问题：下标超出有效范围（0到size-1） 避免方法：

• 访问前检查下标合法性
• C++中使用vector.at()进行带检查的访问

3.5.4 扩容后的指针失效

问题：使用realloc或手动扩容后，原指针可能失效 避免方法：扩容后及时更新指针变量，使用新指针访问数组

3.5.5 类型匹配

注意事项：

• C语言中malloc返回void*，需强制类型转换
• C++中new自动返回对应类型指针，无需转换

3.6 多维动态数组

3.6.1 C++中的二维动态数组（使用vector）

方法1：直接初始化（推荐初学者）

#include<bits/stdc++.h>
using namespace std;

int main(){
  //创建rows行，每行都是一个包含cols个0的vector
	int rows = 3, cols = 4;
	vector< vector<int> > matrix(rows, vector<int>(cols, 0));
  // 访问元素
	matrix[1][2] = 5; // 第二行第三列赋值为5（索引从0开始）
	return 0;
}

方法2：先声明后调整大小

#include<bits/stdc++.h>
using namespace std;

int main(){
  vector<vector<int>> matrix;
  matrix.resize(rows);           // 先设置行数
  for(int i = 0; i < rows; i++) {
      matrix[i].resize(cols, 0); // 再设置每行的列数
  }
	return 0;
}

方法3：逐行添加

#include<bits/stdc++.h>
using namespace std;

int main(){
  vector<vector<int>> matrix;
  for(int i = 0; i < rows; i++) {
      matrix.push_back(vector<int>(cols, 0));
  }
	return 0;
}

####方法4：固定行数的动态数组(推荐)

#include<bits/stdc++.h>
using namespace std;
int main(){
	// 创建固定100行的二维数组，每行是动态的vector
	int ROW_COUNT = 100;
	vector<int> arr[ROW_COUNT];
	
	// 初始化每行
	for(int i = 0; i < ROW_COUNT; i++) {
	    arr[i] = vector<int>(cols, 0);  // 每行初始化为cols列，值为0
	}
	
	// 或者逐行动态调整
	arr[0].resize(50);      // 第一行调整为50列
	arr[1].push_back(10);   // 第二行添加一个元素10
	arr[2].clear();         // 第三行清空
	
	// 访问元素
	arr[5][3] = 25;         // 第六行第四列赋值为25
	return 0;
}

本章重点总结

操作类型	C++实现（推荐）	关键注意事项
创建数组	new[]或std::vector	检查分配是否成功
调整大小	vector::resize()	更新指针，处理数据复制
释放内存	delete[]或自动管理	避免内存泄漏和野指针
访问元素	下标操作或at()方法	防止越界访问

第4章 线性表和链表

​ 线性表是计算机科学中最基本、最常用的数据结构之一，它是由n个具有相同特性的数据元素组成的有限序列。线性表的核心特征是元素之间存在一对一的线性关系，即除第一个和最后一个元素外，每个元素有且仅有一个直接前驱和一个直接后继。

4.1 线性表的基本概念

4.1.1 定义

线性表（Linear List）是由 n (n≥0) 个数据元素（a₁, a₂, ⋯, an）组成的有界序列，其中：

• n为线性表的长度，n=0时称为空表；
• 数据元素可以是基本数据类型（如int、char），也可以是结构体、对象等复杂类型，但所有元素必须具有相同类型；
• 元素之间的位置关系是线性的：a₁是第一个元素，a_n是最后一个元素；aᵢ(2≤i≤n-1)的直接前驱是aᵢ₋₁，直接后继是aᵢ₊₁

4.1.2 基本操作

线性表的基本操作是实现对元素的增、删、改、查等操作：

操作类型	功能描述
初始化	创建一个空的线性表
判空	判断线性表是否为空（长度为0）
求长度	返回线性表中元素的个数
获取元素	返回指定位置（下标）的元素
查找元素	查找指定元素在表中的位置（首次出现）
插入元素	在指定位置插入一个新元素，表长度加1
删除元素	删除指定位置的元素，表长度减1
清空表	删除表中所有元素，使其变为空表

这些操作的具体实现方式取决于线性表的存储结构。

4.2 顺序表（顺序存储结构）

顺序表是线性表的顺序存储结构，它用一组地址连续的存储单元依次存储线性表中的元素，使得逻辑上相邻的元素在物理位置上也相邻。

4.2.1 存储结构

在C/C++中，顺序表通常用数组实现，同时需要记录当前元素个数（长度）和数组的最大容量：

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;  // 定义顺序表的最大容量

// 定义元素类型
typedef int ElemType;

// 顺序表结构体定义
struct SeqList {
    ElemType data[MAX_SIZE];  // 静态数组，存储数据元素
    int length;               // 当前顺序表的实际长度
};

4.2.2 基本操作实现

初始化：

/**
 * 初始化顺序表
 * @param L 顺序表（引用传递）
 * 功能：创建一个空的顺序表
 */
void initList(SeqList &L) {
    L.length = 0;  // 将长度设为0，表示空表
    cout << "顺序表初始化完成，当前长度：" << L.length << endl;
}

插入元素（在第i个位置插入元素e，1 ≤ i ≤ length+1）：

/**
 * 在顺序表第i个位置插入元素e
 * @param L 顺序表
 * @param i 插入位置（1 ≤ i ≤ length+1）
 * @param e 要插入的元素
 * @return 插入成功返回true，失败返回false
 */
bool insertList(SeqList &L, int i, ElemType e) {
    // 步骤1：参数合法性检查
    if (i < 1 || i > L.length + 1) {
        cout << "错误：插入位置" << i << "不合法！有效范围：1~" << L.length + 1 << endl;
        return false; // 位置无效
    }
    
    // 步骤2：空间检查
    if (L.length >= MAX_SIZE) {
        cout << "错误：顺序表已满，无法插入新元素！" << endl;
        return false; // 表已满
    }
    
    // 步骤3：移动元素（关键步骤）
    // 从最后一个元素开始，到第i个元素，依次向后移动一位
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];  // 后移操作
    }
    
    // 步骤4：插入新元素
    L.data[i - 1] = e;  // 在腾出的位置插入新元素
    
    // 步骤5：更新长度
    L.length++;
    cout << "在位置" << i << "插入元素：" << e << "，当前长度：" << L.length << endl;
    
    return true;
}

删除元素（删除第i个位置的元素，1 ≤ i ≤ length）：

/**
 * 删除顺序表第i个位置的元素
 * @param L 顺序表
 * @param i 删除位置（1 ≤ i ≤ length）
 * @param e 保存被删除的元素值
 * @return 删除成功返回true，失败返回false
 */
bool deleteList(SeqList &L, int i, ElemType &e) {
    // 步骤1：参数合法性检查
    if (i < 1 || i > L.length) {
        cout << "错误：删除位置" << i << "不合法！有效范围：1~" << L.length << endl;
        return false; // 位置无效
    }
    
    // 步骤2：保存被删除元素
    e = L.data[i - 1];  // 数组下标从0开始
    
    // 步骤3：移动元素（关键步骤）
    // 从第i+1个元素开始，到最后一个元素，依次向前移动
    for (int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];  // 前移操作
    }
    
    // 步骤4：更新长度
    L.length--;
    cout << "删除位置" << i << "的元素：" << e << "，当前长度：" << L.length << endl;
    
    return true;
}

查找元素：

/**
 * 在顺序表中查找元素e的位置
 * @param L 顺序表
 * @param e 要查找的元素
 * @return 找到返回位置(1-based)，未找到返回-1
 */
int locateElem(SeqList L, ElemType e) {
    // 遍历整个顺序表
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            cout << "找到元素" << e << "，位于位置" << i+1 << endl;
            return i + 1;  // 返回位置（1-based）
        }
    }
    
    cout << "未找到元素" << e << endl;
    return -1;  // 未找到
}

其他常用操作:

// 判断顺序表是否为空
bool isEmpty(SeqList L) {
    return L.length == 0;
}

// 获取顺序表当前长度
int getLength(SeqList L) {
    return L.length;
}

// 获取第i个元素的值
bool getElem(SeqList L, int i, ElemType &e) {
    if (i < 1 || i > L.length) {
        return false;
    }
    e = L.data[i - 1];
    return true;
}

// 遍历输出顺序表
void printList(SeqList L) {
    if (isEmpty(L)) {
        cout << "顺序表为空！" << endl;
        return;
    }
    
    cout << "顺序表内容（长度=" << L.length << "）：";
    for (int i = 0; i < L.length; i++) {
        cout << L.data[i] << " ";
    }
    cout << endl;
}

4.2.3 特点

优点：

• 可以通过数组下标直接访问元素，随机访问效率高（时间复杂度O(1)）
• 存储密度高，无需额外存储指针信息

缺点：

• 插入和删除操作需要移动大量元素，时间复杂度为O(n)
• 容量固定（静态数组），扩容困难
• 可能存在内存浪费（预留容量未使用）或溢出风险

4.2.4 适用场景

适用于元素个数固定或变化不大，且需要频繁随机访问的场景（如存储学生信息并按学号查询）。

4.3 链表（链式存储结构）

链表是线性表的链式存储结构，它不需要连续的存储单元，而是通过指针（或引用）将分散的节点连接成一个序列。

4.3.1 单链表

单链表是最简单的链表形式，每个节点只有一个指针域，指向其后继节点。

存储结构：

// 定义元素类型为int，便于后续修改元素类型
// 使用typedef可以方便地更改元素类型，比如改为float、char等
typedef int ElemType;

/**
 * 单链表节点结构体定义
 * 每个节点包含数据域和指针域两部分
 */
typedef struct LNode {
    ElemType data;        // 数据域：存储节点的实际数据
    struct LNode *next;   // 指针域：指向下一个节点的指针
                          // 使用struct LNode *而不是LNode *，因为typedef尚未完成
} LNode, *LinkList;       // 同时定义两种类型：
                          // LNode - 节点类型
                          // LinkList - 指向节点的指针类型（通常用作头指针）

基本操作实现：

初始化：

void initList(LinkList &L) {
    L = nullptr; // 空表，头指针为nullptr
}

头插法创建链表（新元素插入到表头）：

void createListHead(LinkList &L, int n) {
    L = new LNode;
    L->next = nullptr; // 建立头节点
    
    for (int i = 0; i < n; i++) {
        LNode *p = new LNode; // 创建新节点
        cin >> p->data;       // 输入数据
        p->next = L->next;    // 新节点指向头节点的后继
        L->next = p;          // 头节点指向新节点
    }
}

尾插法创建链表（新元素插入到表尾）：

void createListTail(LinkList &L, int n) {
    L = new LNode;
    L->next = nullptr;
    LNode *r = L; // 尾指针，始终指向最后一个节点
    
    for (int i = 0; i < n; i++) {
        LNode *p = new LNode;
        cin >> p->data;
        p->next = nullptr;
        r->next = p; // 尾节点指向新节点
        r = p;       // 尾指针后移
    }
}

插入元素（在第i个位置插入元素e）：

bool insertList(LinkList &L, int i, ElemType e) {
    LNode *p = L;
    int j = 0;
    
    // 找到第i-1个节点
    while (p != nullptr && j < i - 1) {
        p = p->next;
        j++;
    }
    
    if (p == nullptr || j > i - 1) return false; // 位置无效
    
    LNode *s = new LNode;
    s->data = e;
    s->next = p->next; // 新节点指向p的后继
    p->next = s;       // p指向新节点
    return true;
}

删除元素（删除第i个位置的元素）：

bool deleteList(LinkList &L, int i, ElemType &e) {
    LNode *p = L;
    int j = 0;
    
    // 找到第i-1个节点
    while (p != nullptr && j < i - 1) {
        p = p->next;
        j++;
    }
    
    if (p == nullptr || p->next == nullptr) return false; // 位置无效
    
    LNode *q = p->next; // q指向被删除节点
    e = q->data;        // 保存数据
    p->next = q->next;  // 断开链接
    delete q;           // 释放内存
    return true;
}

查找元素（按值查找）：

LNode* locateElem(LinkList L, ElemType e) {
    LNode *p = L->next; // 从第一个元素节点开始
    
    while (p != nullptr && p->data != e) {
        p = p->next;
    }
    return p; // 找到返回节点指针，否则返回nullptr
}

4.3.2 双链表

双链表每个节点包含两个指针域，分别指向其前驱节点和后继节点。

存储结构：

typedef struct DNode {
    ElemType data;
    struct DNode *prior; // 指向前驱节点
    struct DNode *next;  // 指向后继节点
} DNode, *DLinkList;

特点：

• 可以双向遍历，访问前驱节点的时间复杂度为O(1)
• 插入和删除操作需要同时修改两个指针域（前驱和后继），逻辑稍复杂

4.3.3 循环链表

循环链表的最后一个节点的指针域不指向nullptr，而是指向头节点（单循环链表）或第一个元素节点，形成一个环。

存储结构：

struct Node {
    int data;   // 数据域：存储节点数据
    Node* next; // 指针域：指向后继节点，最后一个节点的next指向头节点
};

特点：

• 从表中任意节点出发，均可遍历整个链表
• 适合解决约瑟夫环等环形问题

4.3.4 链表的特点

优点：

• 插入和删除操作无需移动元素，只需修改指针，时间复杂度为O(1)（已知前驱节点时）
• 动态分配内存，无需预先确定容量，不存在溢出问题

缺点：

• 不能随机访问，查找元素需从头遍历，时间复杂度为O(n)
• 每个节点需额外存储指针域，存储密度低
• 对内存管理要求高，易出现内存泄漏或野指针问题

4.3.5 适用场景

适用于元素个数频繁变化，且不需要频繁随机访问的场景（如链表式队列、栈，或动态维护的任务列表）。

4.4 顺序表与链表的对比

特性	顺序表	链表
存储方式	连续存储单元	非连续存储单元，通过指针连接
随机访问	支持 (O(1))	不支持 (O(n))
插入/删除	需移动元素 (O(n))	只需修改指针 (O(1)，已知前驱时)
空间分配	静态（固定容量）或动态（扩容成本高）	动态分配（按需分配）
存储密度	高（无额外开销）	低（需存储指针）
内存碎片	可能产生（动态扩容后原空间未用）	可能产生（频繁分配/释放）
实现复杂度	简单	较复杂（指针操作）

4.5 三种链表的对比

特性	单链表	双链表	循环链表（以单循环为例）
节点结构	数据域+1个后继指针（next）	数据域+前驱指针（prior）+后继指针（next）	数据域+1个后继指针（next）
尾节点指向	NULL		头节点（形成闭环）
遍历终止条件	指针指向NULL		指针回到头节点
访问前驱节点	需从头遍历（O(n)）	直接通过prior指针访问（O(1)）	需从头遍历（O(n)）
访问后继节点	直接通过next指针访问（O(1)）
插入操作	需找到前驱节点（O(n)）	直接操作前驱和后继指针（O(1)）	需找到前驱节点（O(n)）
删除操作
内存占用	较小（仅一个指针）	较大（两个指针）	较小（仅一个指针）
优点	结构简单，内存开销小	可双向遍历，插入删除效率高	从任意节点可遍历全表，适合环形数据结构
缺点	不能双向遍历，访问前驱节点效率低	结构较复杂，内存开销大	遍历需注意终止条件，否则易死循环
适用场景	简单的线性数据存储，如单方向数据处理	需要频繁双向遍历，插入删除的场景，如浏览器历史记录	环形问题场景，如约瑟夫问题、循环队列

4.6 线性表的应用

线性表是许多复杂数据结构的基础，其应用广泛：

• 数组：本质是顺序表，用于存储同类型数据，支持快速随机访问
• 栈和队列：可基于顺序表（数组）或链表实现，分别遵循"后进先出"和"先进先出"规则
• 多项式表示：用链表存储多项式的项（系数和指数），便于进行多项式相加、相乘等操作
• 通讯录管理：用顺序表或链表存储联系人信息，实现添加、删除、查询等功能

本章重点总结

学习建议：

1. 理解顺序表和链表的根本区别及各自适用场景
2. 掌握单链表的基本操作实现，特别是插入和删除的逻辑
3. 熟悉三种链表的特点和选择依据
4. 通过实际编程练习加深对指针操作的理解

核心要点：

• 顺序表适合随机访问，链表适合频繁插入删除
• 链表操作要注意指针的正确修改和内存管理
• 根据具体需求选择合适的线性表实现方式

第5章 递归算法详解

5.1 递归算法的基本概念

5.1.1 递归的定义与本质

​ 递归（Recursion） 是一种在计算机科学和数学中广泛使用的问题解决方法，其核心思想是：一个函数直接或间接地调用自身，通过将复杂问题分解为与原问题相似但规模更小的子问题来求解。

递归的核心特征：

• 自我调用：函数在执行过程中调用自身
• 问题分解：将原问题分解为规模更小的相似子问题
• 渐进求解：从大规模问题逐步分解到可直接求解的基本情况

5.1.2 递归的核心思想解析

1. 问题相似性原理

// 阶乘函数的递归实现
int factorial(int n) {
    if (n == 0) {
        return 1; // 基本情况
    } else {
        // 关键洞察：n! 与 (n-1)! 具有相同的计算逻辑
        return n * factorial(n - 1); 
    }
}

**说明：**计算n!的问题与计算(n-1)!的问题在结构上完全相似，只是输入规模不同

2. 规模递减机制 递归必须确保每次调用时问题规模都在减小，这是避免无限递归的关键：

• 阶乘：n → n-1 → n-2 → ... → 0
• 斐波那契：n → n-1 和 n-2 → 更小的子问题
• 二分查找：搜索范围每次减半

3. 终止条件的重要性 没有适当终止条件的递归将导致栈溢出错误：

// 错误的递归：缺少基本情况
int infiniteRecursion(int n) {
    return n * infiniteRecursion(n - 1); // 永远无法终止！
}

5.2 递归算法的三要素详解

5.2.1 基本情况（Base Case）

基本情况的定义：递归过程中可以直接求解而无需继续递归的最小问题实例。

常见的基本情况模式：

// 阶乘的基本情况
if (n == 0) return 1;

// 斐波那契的基本情况  
if (n == 0) return 0;
if (n == 1) return 1;

// 汉诺塔的基本情况
if (n == 1) {
    cout << "Move disk 1 from " << from << " to " << to << endl;
    return;
}

// 链表递归的基本情况（遍历到末尾）
if (head == nullptr) return;

设计基本原则：

• 必须至少有一个基本情况
• 基本情况应该是最简单、可直接求解的情形
• 确保递归调用最终能够达到基本情况

5.2.2 递归关系（Recursive Relation）

递归关系的本质：定义如何通过子问题的解来构造原问题的解。

数学表达式示例：

factorial(n) = n × factorial(n-1)
fib(n) = fib(n-1) + fib(n-2)
sum(arr, n) = arr[n] + sum(arr, n-1)

代码实现模式：

// 组合子问题结果的常见方式
return current_value + recursive_call(smaller_problem);    // 累加型
return recursive_call(left_part) + recursive_call(right_part); // 分治型
return max(current, recursive_call(remaining));            // 比较型

5.2.3 规模递减（Decreasing Size）

规模递减的验证方法：

int factorial(int n) {
    if (n == 0) return 1;
    // 参数从n变为n-1，规模严格递减
    return n * factorial(n - 1); // n-1 < n，确保收敛
}

确保收敛的关键：

1. 单调递减：每次递归调用的参数必须严格小于当前参数
2. 有下界：递减过程必须有明确的终止点
3. 有限步骤：从初始规模到基本情况必须在有限步骤内完成

5.3 递归算法的完整结构与实现模式

5.3.1 标准递归模板

返回类型 递归函数名(参数列表) {
    // 1. 基本情况检查
    if (满足基本情况条件) {
        return 基本情况解或执行基本操作;
    }
    
    // 2. 问题分解（可能有多种方式）
    子问题1 = 递归函数名(缩小规模的参数1);
    子问题2 = 递归函数名(缩小规模的参数2);
    // ...
    
    // 3. 结果组合
    return 组合子问题结果的逻辑;
}

5.3.2 多种递归模式示例

1. 线性递归模式

// 单路径递归：链表求和
int listSum(Node* head) {
    if (head == nullptr) return 0;           // 基本情况
    return head->value + listSum(head->next); // 递归关系
}

2. 分支递归模式

// 多路径递归：斐波那契数列
int fib(int n) {
    if (n <= 1) return n;                    // 基本情况
    return fib(n-1) + fib(n-2);              // 两个递归分支
}

3. 分治递归模式

// 二分查找的递归实现
int binarySearch(int arr[], int left, int right, int target) {
    if (left > right) return -1;             // 基本情况：未找到
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) return mid;      // 基本情况：找到目标
    
    if (arr[mid] > target) {
        return binarySearch(arr, left, mid-1, target);  // 左半部分
    } else {
        return binarySearch(arr, mid+1, right, target); // 右半部分
    }
}

5.4 递归执行过程深度解析

5.4.1 函数调用栈的工作原理

栈帧（Stack Frame）的组成：

• 函数参数
• 局部变量
• 返回地址
• 调用者的上下文信息

factorial(3)的详细执行过程：

调用栈演变过程：
1. factorial(3)入栈
   │ n=3, 需要计算3*factorial(2)
   └── 2. factorial(2)入栈
        │ n=2, 需要计算2*factorial(1)
        └── 3. factorial(1)入栈
             │ n=1, 需要计算1*factorial(0)
             └── 4. factorial(0)入栈
                  │ n=0, 基本情况，返回1
                  └── 返回1

出栈过程：
4. factorial(0)返回1，出栈
3. factorial(1)收到1，计算1*1=1，返回1，出栈  
2. factorial(2)收到1，计算2*1=2，返回2，出栈
1. factorial(3)收到2，计算3*2=6，返回6，出栈

5.4.2 递归树的可视化理解

斐波那契fib(4)的递归树：

        fib(4)
        /    \
    fib(3)   fib(2)
    /    \    /    \
fib(2) fib(1) fib(1) fib(0)
/    \
fib(1) fib(0)

关键观察：

• 递归深度：从根节点到最深叶节点的路径长度
• 重复计算：fib(2)被计算了2次，fib(1)被计算了3次
• 时间复杂度：与递归树节点总数相关

5.5 典型递归算法深度剖析

5.5.1 斐波那契数列递归实现

/**
 * 计算第n个斐波那契数
 * 时间复杂度：O(2^n) - 指数级
 * 空间复杂度：O(n) - 递归深度
 */
int fib(int n) {
    // 两个基本情况
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    // 递归关系：当前项等于前两项之和
    return fib(n - 1) + fib(n - 2);
}

性能问题分析：

• 重复计算严重：fib(2)被多次重复计算
• 指数级增长：计算fib(40)需要约2^40次操作
• 栈深度限制：大规模计算可能导致栈溢出

5.5.2 汉诺塔问题完整解析

问题描述：

• 有3根柱子（A、B、C）和n个大小不同的盘子
• 初始时所有盘子按大小顺序堆叠在A柱（大盘在底）
• 目标：将所有盘子移动到C柱，保持原有顺序
• 约束：每次只能移动一个盘子，且大盘不能放在小盘上

递归解决方案：

/**
 * 汉诺塔问题递归解法
 * @param n 盘子数量
 * @param from 起始柱子
 * @param aux  辅助柱子  
 * @param to   目标柱子
 */
void hanoi(int n, char from, char aux, char to) {
    // 基本情况：只有一个盘子时直接移动
    if (n == 1) {
        cout << "Move disk 1 from " << from << " to " << to << endl;
        return;
    }
    
    // 递归步骤1：将n-1个盘子从from移到aux（以to为辅助）
    hanoi(n - 1, from, to, aux);
    
    // 递归步骤2：将第n个盘子从from移到to
    cout << "Move disk " << n << " from " << from << " to " << to << endl;
    
    // 递归步骤3：将n-1个盘子从aux移到to（以from为辅助）
    hanoi(n - 1, aux, from, to);
}

汉诺塔的数学性质：

• 移动次数：T(n) = 2^n - 1
• 时间复杂度：O(2^n)
• 空间复杂度：O(n) - 递归深度

5.6 递归算法复杂度系统分析

5.6.1 时间复杂度分析方法

1. 递归方程法 建立递归关系式并求解：

阶乘递归：

T(n) = T(n-1) + O(1)
T(0) = O(1)
解：T(n) = O(n)

斐波那契递归：

T(n) = T(n-1) + T(n-2) + O(1)
T(0) = O(1), T(1) = O(1)  
近似解：T(n) = O(2^n)

二分查找递归：

T(n) = T(n/2) + O(1)
T(1) = O(1)
解：T(n) = O(log n)

2. 递归树法 通过绘制递归树计算总操作数：

归并排序示例：

递归树：
         [n]
        /    \
    [n/2]    [n/2]
    /    \    /    \
[n/4] [n/4] [n/4] [n/4]
...（共log n层）

每层工作量：O(n)
总工作量：O(n log n)

5.6.2 空间复杂度详细分析

递归空间组成：

1. 栈空间：递归调用产生的栈帧
2. 堆空间：动态分配的内存（如记忆化数组）

常见递归空间复杂度：

算法类型	空间复杂度	说明
尾递归	O(1)	可优化为迭代
线性递归	O(n)	单路径递归深度
平衡分治	O(log n)	如二分查找
非平衡递归	O(n)	如斐波那契

5.7 递归与递推的全面对比

5.7.1 实现哲学对比

递归（自顶向下）：

// 思维模式：问题分解
int fibRecursive(int n) {
    if (n <= 1) return n;
    // 关注"如何分解问题"
    return fibRecursive(n-1) + fibRecursive(n-2);
}

递推（自底向上）：

// 思维模式：逐步构造  
int fibIterative(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int next = a + b;  // 关注"如何从小问题构建大问题"
        a = b;
        b = next;
    }
    return b;
}

5.7.2 详细性能对比表

特性	递归算法	递推算法
实现方式	函数自调用，问题分解	循环迭代，逐步构建
思维模式	自顶向下，分治思想	自底向上，动态规划
代码可读性	高，接近数学定义	较低，需要状态管理
调试难度	较难，调用栈复杂	较易，线性执行
时间效率	可能有重复计算，函数调用开销	无重复计算，直接计算
空间效率	O(递归深度)，栈空间开销	通常O(1)或O(n)辅助空间
适用场景	树遍历、分治、回溯问题	数值计算、序列生成

5.7.3 斐波那契数列实现对比

递归版本（简洁但低效）：

int fibRecursive(int n) {
    if (n <= 1) return n;
    return fibRecursive(n - 1) + fibRecursive(n - 2);
    // 问题：大量重复计算，时间复杂度O(2^n)
}

递推版本（高效但复杂）：

int fibIterative(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, result;
    for (int i = 2; i <= n; i++) {
        result = a + b;  // 计算当前项
        a = b;           // 更新前两项
        b = result;
    }
    return result;  // 时间复杂度O(n)，空间O(1)
}

5.8 递归算法优化技术详解

5.8.1 尾递归优化

尾递归的定义：递归调用是函数体中的最后一个操作，且返回值直接是该递归调用的结果。

普通递归 vs 尾递归：

// 普通递归：返回前需要执行乘法运算
int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1); // 不是尾递归！
}

// 尾递归版本：累积结果作为参数传递
int factorialTail(int n, int acc = 1) {
    if (n == 0) return acc;
    return factorialTail(n - 1, n * acc); // 尾递归！
}

尾递归的编译器优化：

// 编译器可能将尾递归优化为循环：
int factorialOptimized(int n) {
    int acc = 1;
    while (n > 0) {
        acc = n * acc;
        n = n - 1;
    }
    return acc;
}

尾递归适用条件：

1. 递归调用是函数的最后操作
2. 递归调用的返回值直接作为函数返回值
3. 没有后续计算需要用到递归调用的结果

5.8.2 记忆化优化技术

记忆化原理：存储已计算的子问题结果，避免重复计算。

斐波那契记忆化实现：

#include <vector>
#include <iostream>
using namespace std;

class Fibonacci {
private:
    vector<int> memo;  // 记忆化数组
    
public:
    int fibMemo(int n) {
        // 基本情况
        if (n <= 1) return n;
        
        // 检查是否已经计算过
        if (memo[n] != -1) {
            return memo[n];
        }
        
        // 计算并存储结果
        memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
        return memo[n];
    }
    
    int fib(int n) {
        memo.resize(n + 1, -1);  // 初始化为-1表示未计算
        return fibMemo(n);
    }
};

// 使用示例
int main() {
    Fibonacci f;
    cout << "fib(40) = " << f.fib(40) << endl;  // 快速计算！
    return 0;
}

记忆化性能提升：

• 时间复杂度：从O(2^n) 降为 O(n)
• 空间复杂度：O(n) 用于存储结果
• 实际效果：fib(40)从数秒降为毫秒级

5.8.3 其他优化策略

1. 迭代重写

// 将深度递归改为迭代
void dfsIterative(Node* root) {
    stack<Node*> stk;
    stk.push(root);
    
    while (!stk.empty()) {
        Node* current = stk.top();
        stk.pop();
        // 处理当前节点
        // 将子节点逆序入栈（保持遍历顺序）
        for (auto it = current->children.rbegin(); 
             it != current->children.rend(); ++it) {
            stk.push(*it);
        }
    }
}

2. 剪枝优化

// 在递归搜索中提前终止无效分支
void backtrack(vector<int>& path, int sum, int target) {
    if (sum > target) return;  // 剪枝：和已超过目标
    if (sum == target) {
        // 找到解
        return;
    }
    // 继续搜索...
}

5.9 递归算法适用场景与局限性

5.9.1 最适合使用递归的场景

1. 天然递归结构的问题

// 树的前序遍历
void preorder(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";  // 访问根节点
    preorder(root->left);      // 遍历左子树
    preorder(root->right);     // 遍历右子树
}

2. 分治算法

// 归并排序
void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);      // 排序左半部分
    mergeSort(arr, mid + 1, right); // 排序右半部分
    merge(arr, left, mid, right);   // 合并结果
}

3. 回溯算法

// 八皇后问题
void solveNQueens(int row, vector<string>& board) {
    if (row == board.size()) {
        // 找到解
        return;
    }
    
    for (int col = 0; col < board.size(); col++) {
        if (isValid(board, row, col)) {
            board[row][col] = 'Q';           // 做选择
            solveNQueens(row + 1, board);    // 递归
            board[row][col] = '.';           // 撤销选择
        }
    }
}

5.10 递归算法实践指南

5.10.1 递归思维训练方法

1. 数学归纳法思维

• 基础步骤：验证基本情况成立
• 归纳步骤：假设对n-1成立，证明对n也成立

2. 问题分解训练

// 练习：将数组逆序
void reverseArray(vector<int>& arr, int left, int right) {
    if (left >= right) return;  // 基本情况
    swap(arr[left], arr[right]);// 当前步骤
    reverseArray(arr, left+1, right-1); // 子问题
}

5.10.2 调试技巧与最佳实践

1. 递归调试模板

int recursiveFunction(int n, const string& callInfo) {
    static int callCount = 0;
    int currentCall = ++callCount;
    
    cout << "Call " << currentCall << ": " << callInfo 
         << " n=" << n << endl;
    
    // 基本情况
    if (n <= 1) {
        cout << "Base case reached: returning " << n << endl;
        return n;
    }
    
    // 递归调用
    int result = recursiveFunction(n-1, "left branch") + 
                 recursiveFunction(n-2, "right branch");
    
    cout << "Call " << currentCall << ": returning " << result << endl;
    return result;
}

2. 递归设计检查清单

• 是否明确定义了所有基本情况？
• 递归调用是否确实减小了问题规模？
• 是否可能陷入无限递归？
• 是否存在大量重复计算？
• 递归深度是否在合理范围内？
• 是否有更高效的迭代解法？

3. 性能监控方法

#include <chrono>
#include <iostream>

void measurePerformance() {
    auto start = chrono::high_resolution_clock::now();
    
    // 测试递归函数
    int result = fib(35);
    
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::milliseconds>(end - start);
    
    cout << "Result: " << result << ", Time: " << duration.count() << "ms" << endl;
}

5.10.3 从递归到迭代的转换模式

转换模板：

// 递归版本
返回类型 func(参数) {
    if (基本情况) return 基本解;
    return 组合(func(缩小参数));
}

// 迭代版本  
返回类型 funcIterative(参数) {
    stack<状态> stk;
    stk.push(初始状态);
    
    while (!stk.empty()) {
        状态 current = stk.top();
        stk.pop();
        
        if (满足基本条件) {
            // 处理基本解
        } else {
            // 将子问题状态入栈
            stk.push(子状态1);
            stk.push(子状态2);
        }
    }
    return 结果;
}

第6章 二分查找

6.1 二分查找的基本概念

​ 二分查找（Binary Search）又称折半搜索，是一种高效的查找算法，适用于在有序序列中快速定位目标元素。其核心思想是通过不断将搜索范围减半，显著减少比较次数，从而实现快速查找。

二分查找仅适用于已排序的序列（升序或降序），其基本原理是：

• 确定序列中的中间位置，将目标元素与中间元素进行比较。
• 根据比较结果缩小搜索范围：
  • 若目标元素等于中间元素，查找成功，返回中间位置。
  • 若目标元素小于中间元素（升序序列），则目标元素只能在中间元素左侧的子序列中，缩小范围至左半部分。
  • 若目标元素大于中间元素（升序序列），则目标元素只能在中间元素右侧的子序列中，缩小范围至右半部分。
• 重复上述过程，直到找到目标元素或搜索范围为空（查找失败）。

示例：在升序序列 [1, 3, 5, 7, 9, 11, 13] 中查找 7，二分查找的步骤为：

• 初始范围：[0, 6]（下标），中间元素为 5（下标 3），7 > 5，范围缩小至 [4, 6]。
• 新范围中间元素为 9（下标 5），7 < 9，范围缩小至 [4, 4]。
• 中间元素为 7（下标 4），匹配成功，返回下标 4。

6.2 二分查找的核心思想

​ 二分查找的核心思想是"分而治之，逐步缩小范围"，通过每次将搜索范围减半，实现对数级别的查找效率。与线性搜索（逐个遍历，时间复杂度 O(n)）相比，二分查找的效率更高，尤其在大规模数据中优势明显。

其关键前提是序列必须有序，若序列无序，需先排序（排序时间复杂度通常为 O(n log n)），但排序后多次查找可分摊排序成本。

6.3 二分查找的实现步骤

二分查找的实现需明确搜索范围的边界（通常用左、右指针表示）及终止条件，常见实现方式有迭代法和递归法。

6.3.1 迭代法实现（升序序列）

迭代法通过循环不断缩小搜索范围，是最常用的实现方式，步骤如下：

• 初始化左指针 left = 0，右指针 right = n - 1（n 为序列长度）。
• 当 left <= right 时，执行循环：
  • 计算中间指针 mid = left + (right - left) / 2（避免 left + right 溢出）。
  • 若 arr[mid] == target，返回 mid（查找成功）。
  • 若 arr[mid] < target，说明目标在右半部分，更新 left = mid + 1。
  • 若 arr[mid] > target，说明目标在左半部分，更新 right = mid - 1。
• 循环结束后仍未找到目标，返回 -1（查找失败）。

// 在升序数组 arr 中查找 target，返回下标（未找到返回-1）
int arr[100100],n;
int binarySearchIterative(int target) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 等价于(left + right) / 2，避免溢出
        if (arr[mid] == target) {
            return mid; // 找到目标，返回下标
        } else if (arr[mid] < target) {
            left = mid + 1; // 目标在右半部分
        } else {
            right = mid - 1; // 目标在左半部分
        }
    }
    return -1; // 未找到目标
}

6.3.2 递归法实现（升序序列）

递归法通过函数自身调用缩小范围，逻辑更简洁，步骤如下：

• 定义递归函数，左边界、右边界及目标元素。
• 递归终止条件：若 left > right，返回 -1（查找失败）。
• 计算中间指针 mid，比较 arr[mid] 与 target：
  • 若相等，返回 mid。
  • 若 arr[mid] < target，递归搜索右半部分（left = mid + 1）。
  • 若 arr[mid] > target，递归搜索左半部分（right = mid - 1）。

// 递归辅助函数
int arr[100100],n;
int binarySearchRecursiveHelper(int left, int right, int target) {
    if (left > right) {
        return -1; // 搜索范围为空，未找到
    }
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursiveHelper(mid + 1, right, target); // 搜索右半部分
    } else {
        return binarySearchRecursiveHelper(left, mid - 1, target); // 搜索左半部分
    }
}

// 递归法二分查找入口
int binarySearchRecursive(int n, int target) {
    return binarySearchRecursiveHelper(0, n - 1, target);
}

6.4 二分查找的变体

除基本查找外，二分查找还可用于解决更复杂的查找问题，如查找目标元素的第一个出现位置、最后一个出现位置或插入位置等。

6.4.1 查找第一个等于目标的元素

在存在重复元素的升序序列中，返回左指针。

int arr[100100],n;
int findFirstOccurrence(int target) {
    int left = 0;
    int right = n;//右指针落在无效的位置
    while (left < right) {
        int mid = left + (right - left) / 2;
         if (arr[mid] < target) {
            left = mid + 1;//左指针落在有效的位置
        } else {
            right = mid;//右指针落在有效的位置
        }
    }
    return left;
}

6.4.2 查找最后一个等于目标的元素

在存在重复元素的升序序列中，返回左指针-1。

int arr[100100],n;
int findLastOccurrence(int n, int target) {
    int left = 0;
    int right = n; // 右开区间 [left, right)
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            left = mid + 1; // 目标在右侧或当前位置
        } else {
            right = mid;    // 目标在左侧
        }
    }
    return left - 1;
}

6.5 二分查找的复杂度分析

时间复杂度

• 每次搜索将范围减半，最坏情况下需要 log₂n 次比较（n 为序列长度），因此时间复杂度为 O(log n)。
• 与线性搜索的 O(n) 相比，二分查找在 n 较大时（如 n > 1000）效率提升显著。

空间复杂度

• 迭代法：仅使用常数个指针变量，空间复杂度为 O(1)。
• 递归法：递归调用栈的深度为 log₂n，空间复杂度为 O(log n)。

6.6 二分查找的适用条件

二分查找并非适用于所有场景，其适用条件如下：

• 序列必须有序：二分查找的核心是通过比较中间元素缩小范围，无序序列无法应用此逻辑（需先排序，但排序成本可能高于查找收益）。
• 支持随机访问：序列需支持通过下标快速访问中间元素（如数组），链表等不支持随机访问的数据结构无法高效实现二分查找（访问中间元素需 O(n) 时间）。
• 静态数据或修改不频繁：若序列频繁插入或删除元素，维持有序状态的成本较高，此时二分查找的优势可能被抵消。

6.7 使用注意事项

• 避免整数溢出：计算 mid 时，应使用 mid = left + (right - left)/2，而非 mid = (left + right)/2，防止 left + right 超出整数范围（如 left 和 right 均为 10⁹时，求和会溢出）。
• 明确边界条件：需正确处理 left 和 right 的更新逻辑（mid ± 1），避免死循环或遗漏元素。例如，若更新为 left = mid 或 right = mid，可能导致 left 与 right 无法收敛。
• 处理重复元素：基本二分查找存在重复元素时，返回的位置不确定（可能是任意一个匹配元素），需根据需求实现变体（如查找第一个/最后一个出现位置）。
• 降序序列的适配：若序列为降序，需调整比较逻辑（目标元素大于中间元素时搜索左半部分，反之搜索右半部分）。

6.8 标准库中的二分查找函数

C++标准库 <algorithm> 提供了多个基于二分查找的函数，适用于有序序列（默认升序）：

函数名	功能
binary_search(first, last, target)	判断 [first, last] 范围内是否存在 target，返回 bool 值
lower_bound(first, last, target)	返回 [first, last] 范围内第一个大于等于 target 的元素迭代器
upper_bound(first, last, target)	返回 [first, last] 范围内第一个大于 target 的元素迭代器

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {1, 3, 5, 7, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    
    // 判断是否存在
    bool exists = binary_search(arr, arr + n, target); // exists = true
    
    // 第一个大于等于7的元素下标(3)
    int* lower = lower_bound(arr, arr + n, target);
    int lowerIdx = lower - arr;
    
    // 第一个大于7的元素下标(5)
    int* upper = upper_bound(arr, arr + n, target);
    int upperIdx = upper - arr;
    
    return 0;
}

6.9 二分答案算法

二分答案算法是二分查找思想的延伸，通过在可能的答案范围内二分搜索，高效确定最优解，适用于解决优化问题。

6.9.1 基本概念

核心是将求最优解转化为判断某个值是否满足条件，步骤如下：

• 确定答案范围 [left, right]，包含所有可能解。
• 计算中间值 mid，判断是否满足条件。
• 根据判断结果调整范围：
  • 求最大值时，满足则范围缩至 [mid, right]，否则缩至 [left, mid-1]。
  • 求最小值时，满足则范围缩至 [left, mid]，否则缩至 [mid+1, right]。
• 重复至找到最优解。

示例：求有序数组中第 k 大元素，范围为数组最值，通过判断 mid 是否至少有 k 元素大于等于它来确定。

6.9.2 核心思想

"以判断代替求解"，依赖问题的"单调性"——满足条件的解构成连续区间，以此通过二分快速定位最优解。

6.9.3 实现步骤

迭代法为主，分两类：

求满足条件的最大值

• 初始化 left = 最小值，right = 最大值。
• left < right 时，mid = left + (right - left + 1)/2（避免死循环）。
• 满足条件则 left = mid，否则 right = mid - 1。
• 循环结束，left 即为结果。

求满足条件的最小值

• 初始化 left = 最小值，right = 最大值。
• left < right 时，mid = left + (right - left)/2。
• 满足条件则 right = mid，否则 left = mid + 1。
• 循环结束，left 即为结果。

bool condition(int mid) { ... }

int findMaxValue(int minVal, int maxVal) {
    int left = minVal, right = maxVal;
    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (condition(mid)) left = mid;
        else right = mid - 1;
    }
    return left;
}

6.9.4 应用场景

• 最大化最小值：如分 n 个物品为 k 组，使每组最小值最大。
• 最小化最大值：如找路径，使最长边最短。
• 存在性转化的优化：如给定时间内找最大可完成工作量。

6.9.5 复杂度分析

• 时间复杂度：O(f(n) × log(范围))，f(n) 为每次判断的复杂度。
• 空间复杂度：O(1)。

6.9.6 使用注意事项

• 确定合理范围，避免遗漏或过大。
• 正确设计判断条件，反映问题要求。
• 根据求解类型处理 mid 计算，避免死循环。
• 验证问题单调性，确保算法适用。

第7章 贪心算法

7.1 贪心算法的基本概念

7.1.1 定义与核心思想

​ 贪心算法（Greedy Algorithm）是一种通过在每一步选择中采取局部最优策略，以期最终获得全局最优解的算法思想。其核心特点是"目光短浅"——在每一步决策时只考虑当前状态下的最优选择，而不考虑整体长远规划。

基本特征：

• 逐步构建：通过一系列局部最优选择构建全局解
• 不可回溯：一旦做出选择就不可更改
• 高效性：通常比其他算法（如动态规划）更高效

7.1.2 与其他算法的区别

算法类型	决策方式	子问题处理	适用场景
贪心算法	局部最优选择，不可逆	不存储子问题解	满足贪心选择性质和最优子结构的问题
分治算法	分解为独立子问题	递归求解后合并	子问题相互独立的问题
动态规划	考虑所有可能性	存储子问题解，避免重复计算	有重叠子问题和最优子结构的问题

7.2 贪心算法的核心思想与基本步骤

7.2.1 核心理论基础

贪心算法的有效性依赖于两个关键数学性质：

1. 贪心选择性质

• 全局最优解可以通过一系列局部最优选择获得
• 每一步的选择仅依赖当前状态，不影响后续选择
• 选择的不可逆性：一旦确定局部最优解，就不再更改

2. 最优子结构性质

• 问题的最优解包含其子问题的最优解
• 与动态规划共享这一性质，但实现方式不同
• 例如：最短路径问题中，A→C的最短路径若经过B，则A→B和B→C也是最短路径

7.3 贪心算法的典型应用

7.3.1 找零钱问题

• 题目描述

  小明是一名超市收银员，他需要给顾客找零钱。超市的硬币面额有若干种，小明希望用最少数量的硬币来找零给顾客。

  输入格式

  • 第一行包含两个整数：n 和 amount
    • n 表示硬币的种类数量 (1 ≤ n ≤ 100)
    • amount 表示需要找零的金额 (1 ≤ amount ≤ 10000)
  • 第二行包含 n 个整数，表示每种硬币的面额 (1 ≤ 面额 ≤ 10000)

  输出格式

  • 如果可以找零，输出一个整数，表示需要的最少硬币数量
  • 如果无法找零，输出 -1

  输入示例 1:

  4 36
  1 5 10 25
  

  输出示例 1:

  3
  

  解释： 25 + 10 + 1 = 36，需要3枚硬币。

  输入示例 2:

  3 5
  2 4 6
  

  输出示例 2:

  -1
  

  解释： 无法用面额为2、4、6的硬币凑出5元。

  解题思路

  贪心策略

  每次选择不超过剩余金额的最大面额硬币。

  算法步骤

  1. 将硬币按面额从大到小排序
  2. 遍历每种硬币，尽可能多地使用当前面额的硬币
  3. 如果最终金额刚好为0，返回使用的硬币数量；否则返回-1

  参考代码

  #include <bits/stdc++.h>
  using namespace std;
  
  int main() {
      int n, amount;
      cin >> n >> amount;
      
      int coins[100]; // 存储硬币面额
      for (int i = 0; i < n; i++) {
          cin >> coins[i];
      }
      
      // 将硬币按面额从大到小排序
      sort(coins, coins + n, greater<int>());
      
      int count = 0;
      // 遍历每种硬币
      for (int i = 0; i < n; i++) {
          int coin = coins[i];
          // 只要剩余金额大于等于当前硬币面额，就一直使用这种硬币
          while (amount >= coin) {
              amount -= coin; // 减去硬币面额
              count++;        // 硬币计数加1
          }
          // 如果金额已经凑够，提前结束
          if (amount == 0) {
              break;
          }
      }
      
      // 输出结果
      if (amount == 0) {
          cout << count << endl;
      } else {
          cout << -1 << endl;
      }
      
      return 0;
  }
  

7.3.2 活动选择问题

题目描述

学校要举办一系列活动，每个活动有固定的开始时间和结束时间。由于场地有限，不能同时举办两个活动。请问最多能举办多少个互不冲突的活动？

输入格式

• 第一行包含一个整数 n (1 ≤ n ≤ 1000)，表示活动的数量
• 接下来 n 行，每行包含两个整数 start 和 end (0 ≤ start < end ≤ 10000)，表示每个活动的开始时间和结束时间

输出格式

• 输出一个整数，表示最多能举办的活动数量

输入示例:

6
1 4
3 5
0 6
5 7
3 8
5 9

输出示例:

4

解释： 最多可以选择4个活动，例如选择 (1,4), (5,7), (8,11), (12,14) 等活动组合。

贪心策略

每次选择结束时间最早的活动，这样可以为后续活动留下更多时间。

算法步骤

1. 将所有活动按结束时间从小到大排序
2. 选择第一个活动作为初始选择
3. 遍历剩余活动，如果当前活动的开始时间不早于上一个选中活动的结束时间，则选择该活动
4. 统计最终选中的活动数量

参考代码

#include <bits/stdc++.h>
using namespace std;

struct Activity {
    int start; // 开始时间
    int end;   // 结束时间
}activities[1000];// 假设最多有1000个活动

// 按结束时间升序排序的比较函数
bool compare(Activity a, Activity b) {
    return a.end < b.end;
}

int main() {
    int n;
    cin >> n;
        
    // 读取活动数据
    for (int i = 0; i < n; i++) {
        cin >> activities[i].start >> activities[i].end;
    }
    
    // 按结束时间排序
    sort(activities, activities + n, compare);
    
    int count = 1; // 至少选择第一个活动
    int lastEnd = activities[0].end; // 记录上一个选中活动的结束时间
    
    // 选择后续活动
    for (int i = 1; i < n; i++) {
        // 如果当前活动与上一个选中活动不冲突
        if (activities[i].start >= lastEnd) {
            count++;
            lastEnd = activities[i].end; // 更新最后一个选中活动的结束时间
        }
    }
    
    cout << count << endl;
    
    return 0;
}

算法正确性证明：

1. 最早结束的活动必定在某个最优解中
2. 选择该活动后，问题简化为在剩余可用时间内选择活动
3. 递归应用此策略得到全局最优解

7.4 贪心算法的复杂度分析

贪心算法的时间复杂度主要取决于两个部分：

7.4.1 时间复杂度组成

1. 排序步骤

• 时间复杂度通常为：O(n log n)，其中n为数据规模

2. 选择步骤

• 遍历所有元素进行选择（如找零钱、活动选择）
• 时间复杂度通常为：O(n)

总时间复杂度： O(n log n)（通常受排序步骤主导）

7.4.2 空间复杂度分析

主要空间消耗：

• 输入数据存储：O(n)
• 辅助数据结构：O(n)（如并查集、优先队列）
• 排序算法空间：O(1) 或 O(n)（取决于排序算法）

典型空间复杂度： O(n)

7.4.3 各算法复杂度总结

算法	时间复杂度	空间复杂度	主导操作
找零钱问题	O(n log n)	O(1)	排序
活动选择

7.5 贪心算法的适用条件与局限性

7.5.1 适用条件

贪心算法并非适用于所有问题，其有效性依赖严格的数学条件：

1. 贪心选择性质

• 全局最优解可通过一系列局部最优选择获得
• 每一步选择仅依赖当前状态
• 选择不影响后续选择的可行性
• 验证方法： 证明在每一步，局部最优选择都在某个全局最优解中

2. 最优子结构性质

• 问题的最优解包含其子问题的最优解
• 子问题间相对独立
• 示例： 最短路径问题具有最优子结构

7.5.2 局限性

1. 不保证全局最优

• 许多问题不满足贪心选择性质
• 局部最优可能导致全局解次优
• 经典反例： 0-1背包问题（物品不可分割）

2. 对问题细节敏感

• 微小条件变化可能导致策略失效
• 示例： 找零钱问题中，不同的硬币面额集合会影响贪心策略的最优性

3. 正确性验证困难

• 需要严格的数学证明（如数学归纳法）
• 不能依赖直观判断
• 证明过程可能很复杂

7.5.3 贪心 vs 动态规划对比

方面	贪心算法	动态规划
决策依据	局部最优	全局考虑
子问题	不存储解	存储子问题解
时间复杂度	通常较低	通常较高
正确性保证	需要严格证明	总能得到最优解
适用问题	满足贪心性质	有重叠子问题

7.6 贪心算法实践指南

7.6.1 算法设计步骤

1. 问题分析
   • 确定是否满足贪心选择性质
   • 验证最优子结构
   • 考虑边界情况
2. 策略设计
   • 定义"局部最优"的标准
   • 确定选择顺序
   • 设计可行性检查
3. 正确性证明
   • 使用数学归纳法
   • 考虑反例验证
   • 进行严谨推导
4. 实现优化
   • 选择合适的数据结构
   • 优化排序策略
   • 处理边界条件

7.6.2 常见陷阱与避免方法

陷阱1： 错误假设贪心性质始终成立 避免： 总是用反例测试算法

陷阱2： 忽略问题约束条件 避免： 在每一步验证可行性

陷阱3： 选择标准设计不当 避免： 多尝试不同的贪心策略

贪心算法虽然思想简单，但正确性证明往往需要深厚的数学功底。在实际应用中，应当仔细分析问题特性，确保贪心策略的适用性。