第二十七 代数（Algebra）

代数是数学的一个基础分支，主要研究数、符号、数量关系以及运算结构。它通过用符号（如字母）代替具体数字，抽象地探讨运算规律、方程求解以及数学结构（如群、环、域等）。

法国数学家弗朗索瓦·韦达（François Viète，1540—1603）第一次有意识地使用系统的代数字母与符号，以辅音字母表示已知量，元音字母表示未知量，推进了方程论的发展，使代数成为一般类型的形式和方程的学问，因其抽象而应用更为广泛，被称为“代数符号之父“。在研究一元二次方程的解法时，他发现了一元二次方程的根与系数之间存在的特殊关系，人们把这个关系称为韦达定理。

一、一元二次方程

1.1 一般形式

$$ax^2+bx+c=0 \quad (a\neq0)$$

1.2 求根公式

$$x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$$

其中 $\Delta = b^2 - 4ac$ 称为判别式：

1.3 韦达定理

设方程 $ax^2+bx+c=0$ 的两个根为 $x_1, x_2$，则：

$$x_1 + x_2 = -\frac{b}{a}$$

$$x_1 \cdot x_2 = \frac{c}{a}$$

1.4 Rust 实现

fn solve_quadratic(a: f64, b: f64, c: f64) -> (Option<f64>, Option<f64>) {
    let discriminant = b * b - 4.0 * a * c;

    if discriminant > 0.0 {
        let sqrt_d = discriminant.sqrt();
        let x1 = (-b + sqrt_d) / (2.0 * a);
        let x2 = (-b - sqrt_d) / (2.0 * a);
        (Some(x1), Some(x2))
    } else if discriminant == 0.0 {
        let x = -b / (2.0 * a);
        (Some(x), Some(x))  // 重根
    } else {
        (None, None)  // 无实数根
    }
}

fn main() {
    // x² - 5x + 6 = 0，根为 2 和 3
    let (x1, x2) = solve_quadratic(1.0, -5.0, 6.0);
    println!("x² - 5x + 6 = 0 的根: {:?}, {:?}", x1, x2);

    // x² + 2x + 1 = 0，根为 -1（重根）
    let (x1, x2) = solve_quadratic(1.0, 2.0, 1.0);
    println!("x² + 2x + 1 = 0 的根: {:?}, {:?}", x1, x2);

    // x² + x + 1 = 0，无实数根
    let (x1, x2) = solve_quadratic(1.0, 1.0, 1.0);
    println!("x² + x + 1 = 0 的根: {:?}, {:?}", x1, x2);
}

二、数列

2.1 等差数列

等差数列是相邻两项之差为常数的数列，这个常数称为公差（$d$）。

通项公式： $a_n = a_1 + (n-1)d$

前 n 项和： $S_n = \frac{n(a_1 + a_n)}{2} = \frac{n}{2}[2a_1 + (n-1)d]$

fn arithmetic_sum(a1: f64, d: f64, n: usize) -> f64 {
    n as f64 * (2.0 * a1 + (n as f64 - 1.0) * d) / 2.0
}

fn main() {
    // 1 + 2 + 3 + ... + 100 = 5050
    println!("1+2+...+100 = {}", arithmetic_sum(1.0, 1.0, 100));  // 5050
}

2.2 等比数列

等比数列是相邻两项之比为常数的数列，这个常数称为公比（$q$）。

通项公式： $a_n = a_1 \cdot q^{n-1}$

前 n 项和： $S_n = \frac{a_1(1 - q^n)}{1 - q} \quad (q \neq 1)$

fn geometric_sum(a1: f64, q: f64, n: usize) -> f64 {
    if q == 1.0 {
        a1 * n as f64
    } else {
        a1 * (1.0 - q.powi(n as i32)) / (1.0 - q)
    }
}

fn main() {
    // 1 + 2 + 4 + 8 + ... 前 10 项
    println!("等比求和: {}", geometric_sum(1.0, 2.0, 10));  // 1023.0
}

2.3 斐波那契数列

斐波那契数列（Fibonacci Sequence）是递推数列的经典代表：

$$ F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \quad (n \ge 2) $$

fn fib_iterative(n: u32) -> u32 {
    if n == 0 { return 0; }
    if n == 1 { return 1; }

    let mut prev = 0;  // F(n-2)
    let mut curr = 1;  // F(n-1)

    for _ in 2..=n {
        let next = prev + curr;
        prev = curr;
        curr = next;
    }
    curr
}

fn main() {
    for i in 0..=10 {
        println!("F{} = {}", i, fib_iterative(i));
    }
    // F0=0, F1=1, F2=1, F3=2, F4=3, F5=5, F6=8, F7=13, F8=21, F9=34, F10=55
}

斐波那契数列通项公式（Binet 公式）：

$$ F(n) = \frac{1}{\sqrt{5}} \left[\left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right] $$

2.4 调和数列

调和数列的通项为 $a_n = \frac{1}{n}$，其前 n 项和为：

$$ H_n = \sum_{k=1}^{n} \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} $$

结论： 调和级数 $\sum_{n=1}^{\infty} \frac{1}{n}$ 发散（其和趋向于无穷大），尽管增长速度非常缓慢。$H_n$ 的增长速度约为 $\ln(n) + \gamma$，其中 $\gamma \approx 0.5772$ 是欧拉-马歇罗尼常数。

fn harmonic_number(n: u32) -> f64 {
    (1..=n).map(|k| 1.0 / k as f64).sum()
}

fn main() {
    println!("H(10) = {:.6}", harmonic_number(10));    // 2.928968
    println!("H(100) = {:.6}", harmonic_number(100));  // 5.187378
    println!("H(1000) = {:.6}", harmonic_number(1000)); // 7.485471
}

三、黄金分割数

3.1 定义

黄金分割数 $\phi$（phi）是满足方程 $\phi^2 = \phi + 1$ 的正根：

$$ \phi = \frac{1+\sqrt{5}}{2} \approx 1.618033988749895 $$

3.2 黄金分割数的性质

黄金分割数满足公式：

$$ \phi = 1 + \frac{1}{\phi} $$

上述方程的另一个共轭根为：

$$ \hat{\phi} = \frac{1-\sqrt{5}}{2} \approx -0.618033988749895 $$

3.3 与斐波那契数列的关系

斐波那契数列相邻项的极限趋向于黄金分割数：

$$ \lim_{n \to \infty} \frac{F(n+1)}{F(n)} = \phi $$

fn fib(n: u32) -> u64 {
    if n == 0 { return 0; }
    if n == 1 { return 1; }
    let (mut prev, mut curr) = (0u64, 1u64);
    for _ in 2..=n {
        let next = prev + curr;
        prev = curr;
        curr = next;
    }
    curr
}

fn main() {
    let phi = (1.0 + 5.0_f64.sqrt()) / 2.0;
    println!("黄金分割数 φ = {:.15}", phi);

    // 验证相邻项之比趋近于 φ
    for n in [10, 15, 20, 25, 30] {
        let ratio = fib(n + 1) as f64 / fib(n) as f64;
        println!("F{}/F{} = {:.15}  (误差: {:.2e})",
            n + 1, n, ratio, (ratio - phi).abs());
    }
}

3.4 斐波那契数列定理

$$ \gcd(F_n, F_{n-1}) = 1 $$

$$ \gcd(F_m, F_n) = F_{\gcd(m,n)} $$

四、欧拉数与欧拉恒等式

4.1 欧拉数（自然常数）

$$ e = \lim_{n \to \infty} \left(1 + \frac{1}{n}\right)^n \approx 2.718281828459045 $$

fn compute_e(iterations: u32) -> f64 {
    (1..=iterations).map(|n| {
        let n_f = n as f64;
        (1.0 + 1.0 / n_f).powf(n_f)
    }).last().unwrap()
}

fn main() {
    println!("e (近似) = {:.15}", compute_e(100000));
    println!("e (标准库) = {:.15}", std::f64::consts::E);
}

4.2 欧拉恒等式

$$ e^{i\pi} + 1 = 0 $$

欧拉恒等式将数学中五个最重要的常数联系在一起：$e$（自然常数）、$i$（虚数单位）、$\pi$（圆周率）、1（乘法单位元）、0（加法单位元）。它被誉为“最美的数学公式“。

五、最大公约数与最小公倍数

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

辗转相除法是一种高效求两个正整数最大公约数（GCD, Greatest Common Divisor）的方法。

核心定理：

$$ \gcd(a, b) = \gcd(b, a \bmod b) $$

反复应用这个等式，直到余数为 0，此时的除数就是最大公约数。

fn gcd(mut a: u64, mut b: u64) -> u64 {
    while b != 0 {
        let temp = b;
        b = a % b;
        a = temp;
    }
    a
}

fn lcm(a: u64, b: u64) -> u64 {
    a / gcd(a, b) * b  // 先除后乘，避免溢出
}

fn main() {
    println!("gcd(48, 18) = {}", gcd(48, 18));  // 6
    println!("gcd(100, 75) = {}", gcd(100, 75));  // 25
    println!("lcm(48, 18) = {}", lcm(48, 18));  // 144
}

六、重要常数与公式

6.1 圆周率的计算

丘德诺夫斯基算法（Chudnovsky Algorithm）是计算圆周率最快的算法之一，由丘德诺夫斯基兄弟在1988年发现，每迭代一次增加约14位精度：

$$ \frac{1}{\pi} = 12 \sum_{k=0}^{\infty} \frac{(-1)^k (6k)! (13591409 + 545140134k)}{(3k)! (k!)^3 (640320)^{3k + 3/2}} $$

fn factorial(n: u64) -> u64 {
    (1..=n).product()
}

fn chudnovsky_pi(terms: usize) -> f64 {
    let mut sum = 0.0_f64;
    for k in 0..terms {
        let k_f = k as f64;
        let numerator = (-1.0_f64).powi(k as i32)
            * factorial(6 * k as u64) as f64
            * (13591409.0 + 545140134.0 * k_f);
        let denominator = factorial(3 * k as u64) as f64
            * (factorial(k as u64) as f64).powi(3)
            * (640320.0_f64).powf(3.0 * k_f + 1.5);
        sum += numerator / denominator;
    }
    1.0 / (12.0 * sum)
}

fn main() {
    let pi = chudnovsky_pi(2);
    println!("π (Chudnovsky, 2项) = {:.15}", pi);
    println!("π (标准库) = {:.15}", std::f64::consts::PI);
}

6.2 常用数学函数速查

七、线性代数基础

线性代数是代数的重要分支，研究向量空间、线性变换以及矩阵等概念。

7.1 基本概念

7.2 向量运算

fn dot_product(a: &[f64], b: &[f64]) -> f64 {
    a.iter().zip(b.iter()).map(|(x, y)| x * y).sum()
}

fn vector_add(a: &[f64], b: &[f64]) -> Vec<f64> {
    a.iter().zip(b.iter()).map(|(x, y)| x + y).collect()
}

fn vector_scale(a: &[f64], scalar: f64) -> Vec<f64> {
    a.iter().map(|x| x * scalar).collect()
}

fn magnitude(v: &[f64]) -> f64 {
    v.iter().map(|x| x * x).sum::<f64>().sqrt()
}

fn main() {
    let a = vec![1.0, 2.0, 3.0];
    let b = vec![4.0, 5.0, 6.0];

    println!("点积: {}", dot_product(&a, &b));           // 32
    println!("向量加: {:?}", vector_add(&a, &b));        // [5, 7, 9]
    println!("标量乘: {:?}", vector_scale(&a, 2.0));     // [2, 4, 6]
    println!("向量 a 的模: {:.4}", magnitude(&a));       // 3.7417
}

7.3 矩阵运算

type Matrix = Vec<Vec<f64>>;

fn matrix_multiply(a: &Matrix, b: &Matrix) -> Option<Matrix> {
    let rows_a = a.len();
    let cols_a = a[0].len();
    let cols_b = b[0].len();

    if cols_a != b.len() {
        return None;
    }

    let mut result = vec![vec![0.0; cols_b]; rows_a];

    for i in 0..rows_a {
        for j in 0..cols_b {
            for k in 0..cols_a {
                result[i][j] += a[i][k] * b[k][j];
            }
        }
    }

    Some(result)
}

fn matrix_transpose(a: &Matrix) -> Matrix {
    let rows = a.len();
    let cols = a[0].len();
    let mut result = vec![vec![0.0; rows]; cols];

    for i in 0..rows {
        for j in 0..cols {
            result[j][i] = a[i][j];
        }
    }

    result
}

fn main() {
    let a = vec![vec![1.0, 2.0], vec![3.0, 4.0]];
    let b = vec![vec![5.0, 6.0], vec![7.0, 8.0]];

    if let Some(c) = matrix_multiply(&a, &b) {
        println!("矩阵乘法:");
        for row in &c {
            println!("  {:?}", row);
        }
        // [19, 22]
        // [43, 50]
    }

    let t = matrix_transpose(&a);
    println!("转置: {:?}", t);
    // [[1, 3], [2, 4]]
}

八、抽象代数

抽象代数（Abstract Algebra）研究代数结构的一般性质，是代数学的最高层次。

8.1 重要概念

8.2 群在密码学中的应用

群论是现代密码学的数学基础。许多密码算法的安全性依赖于群上的困难问题：

• RSA 加密：基于整数乘法群中大整数分解的困难性
• 椭圆曲线密码：基于椭圆曲线群上离散对数问题的困难性
• Diffie-Hellman 密钥交换：基于有限域中离散对数问题的困难性

抽象代数看似抽象，但它支撑着我们日常使用的加密通信、数字签名等安全技术。

九、代数应用实例

9.1 等额本息贷款计算

问题：贷款 10 万元，年利率 5%，分 60 个月还清，计算每月还款金额。

等额本息月还款公式：

$$ A = P \cdot \frac{i(1+i)^n}{(1+i)^n - 1} $$

其中 $A$ 为每月还款金额，$P$ 为贷款本金，$i$ 为月利率，$n$ 为还款月数。

fn monthly_payment(principal: f64, annual_rate: f64, months: u32) -> f64 {
    let monthly_rate = annual_rate / 12.0;
    let n = months as f64;

    principal * monthly_rate * (1.0 + monthly_rate).powf(n)
        / ((1.0 + monthly_rate).powf(n) - 1.0)
}

fn main() {
    let p = 100_000.0;      // 贷款本金 10 万元
    let rate = 0.05;        // 年利率 5%
    let months = 60;        // 60 个月

    let payment = monthly_payment(p, rate, months);
    println!("每月还款: {:.2} 元", payment);
    println!("总还款: {:.2} 元", payment * months as f64);
    println!("总利息: {:.2} 元", payment * months as f64 - p);
}

9.2 楼梯问题

一段楼梯有 10 级，每次只能走 1 级或 2 级，有多少种上楼方法？

答案就是 $F_{11} = 89$ 种（斐波那契数列的第 11 项）。因为到达第 n 级的方法数等于到达第 n-1 级和第 n-2 级方法数之和。

fn climb_stairs(n: u32) -> u64 {
    if n <= 2 { return n as u64; }

    let (mut prev, mut curr) = (1u64, 2u64);
    for _ in 3..=n {
        let next = prev + curr;
        prev = curr;
        curr = next;
    }
    curr
}

fn main() {
    println!("10 级楼梯的走法: {} 种", climb_stairs(10));  // 89
}

十、学习资源

十一、总结

代数是连接算术与高等数学的桥梁。从简单的一元二次方程到抽象的群论，代数的思想贯穿了计算机科学的方方面面。

练习建议：

1. 实现一个支持复数运算的一元二次方程求解器
2. 用 Rust 实现矩阵的行列式计算
3. 探索椭圆曲线上的点加法运算