附录 问题

提出问题比解决问题更重要。—— 爱因斯坦

打开一切科学的钥匙毫无异议的是问号。—— 巴尔扎克

提出正确的问题，往往等于解决了问题的大半。—— 海森堡

问题 → 猜想 → 证明 → 验证 → 定理 → 推论

一、物不知数（中国剩余定理）

《孙子算经》：今有物，不知其数。三三数之，剩二；五五数之，剩三；七七数之，剩二。问：物几何？

解法口诀：

三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五使得知

同余方程组：

$$ \begin{cases} x \equiv 2 \pmod{3} \ x \equiv 3 \pmod{5} \ x \equiv 2 \pmod{7} \end{cases} $$

中国剩余定理： 设 $m_1, m_2, \ldots, m_k$ 两两互质，则同余方程组在模 $M = \prod m_i$ 下有唯一解。

二、鸡兔同笼

《孙子算经》：今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？

解法：

设鸡有 $x$ 只，兔有 $y$ 只：

$$ \begin{cases} x + y = 35 \ 2x + 4y = 94 \end{cases} $$

解得：鸡 23 只，兔 12 只。

三、引葭赴岸

《九章算术》：今有池方一丈，葭生其中央。出水一尺，引葭赴岸，适与岸齐。问水深、葭长各几何。

（1丈 = 10尺）

古代解法：

$$ b = \frac{a^2 - (c - b)^2}{2(c - b)} $$

现代解法：

设水深 $x$ 尺，则葭长 $(x+1)$ 尺：

$$ x^2 + 5^2 = (x + 1)^2 $$

解得：水深 12 尺，葭长 13 尺。

四、最速降线

问题：在重力作用下，一个质点从点 $A$ 滑到点 $B$（不在正下方），沿什么路径所需时间最短？

答案：摆线（Cycloid）。

摆线的参数方程：

$$ \begin{cases} x = r(\theta - \sin\theta) \ y = r(1 - \cos\theta) \end{cases} $$

五、巴塞尔问题

求所有正整数平方倒数的和：

$$ \sum_{n=1}^{\infty} \frac{1}{n^2} = \frac{\pi^2}{6} $$

该问题由欧拉在 1735 年解决，一举成名。

六、费马引理

若函数 $f(x)$ 在 $x_0$ 处可导且取得极值，则 $f’(x_0) = 0$。

这是微分中值定理的基础。

七、素数问题

素数定理： 不超过 $x$ 的素数个数 $\pi(x) \sim \frac{x}{\ln x}$。

费马小定理： 若 $p$ 是质数，且 $a$ 不是 $p$ 的倍数，则：

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

克拉茨猜想（3n+1 猜想）： 任取一正整数，若为偶数则除以 2，若为奇数则乘以 3 再加 1，重复操作，最终总会落入 4→2→1 的循环。至今未被证明。

八、密码学相关问题

密钥管理

• 如何生成公私钥对？
• 如何根据编码后的公私钥对得到 PrivateKey、PublicKey？
• 如何保护密钥的安全？
• 如何传输交换密钥？

身份认证

如何证明我是我，我妈是我妈？

数字证书及CA

传输层安全性协议（TLS/SSL）是一种安全协议，目的是为互联网通信提供安全及数据完整性保障。

• Rustls — Rust 实现的现代 TLS 库
• ECDH 算法概述
• ockam — 端到端加密通信库

九、算法经典问题

9.1 汉诺塔（Tower of Hanoi）

将 $n$ 个大小不同的圆盘从一根柱子移动到另一根柱子，要求每次只移动一个圆盘，且大盘不能压在小盘上。

最少移动次数： $2^n - 1$

#![allow(unused)]
fn main() {
fn hanoi(n: u32, from: &str, to: &str, aux: &str) {
    if n == 0 { return; }
    hanoi(n - 1, from, aux, to);
    println!("移动圆盘 {} 从 {} 到 {}", n, from, to);
    hanoi(n - 1, aux, to, from);
}
}

9.2 斐波那契数列

$$F(n) = F(n-1) + F(n-2), \quad F(0)=0, ; F(1)=1$$

数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

斐波那契数列与黄金分割比 $\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618$ 密切相关：$\lim_{n\to\infty} \frac{F(n+1)}{F(n)} = \varphi$。

#![allow(unused)]
fn main() {
fn fibonacci(n: u64) -> u64 {
    let (mut a, mut b) = (0u64, 1u64);
    for _ in 0..n {
        let tmp = a + b;
        a = b;
        b = tmp;
    }
    a
}
}

9.3 背包问题（Knapsack Problem）

给定 $n$ 件物品，每件有重量 $w_i$ 和价值 $v_i$，背包容量为 $W$，求装入背包的最大总价值。

0-1 背包（动态规划）：

#![allow(unused)]
fn main() {
fn knapsack_01(weights: &[usize], values: &[usize], capacity: usize) -> usize {
    let n = weights.len();
    let mut dp = vec![0usize; capacity + 1];
    for i in 0..n {
        for w in (weights[i]..=capacity).rev() {
            dp[w] = dp[w].max(dp[w - weights[i]] + values[i]);
        }
    }
    dp[capacity]
}
}

9.4 最长公共子序列（LCS）

给定两个序列，求它们的最长公共子序列的长度。

#![allow(unused)]
fn main() {
fn lcs_length(a: &[char], b: &[char]) -> usize {
    let (m, n) = (a.len(), b.len());
    let mut dp = vec![vec![0usize; n + 1]; m + 1];
    for i in 1..=m {
        for j in 1..=n {
            dp[i][j] = if a[i-1] == b[j-1] {
                dp[i-1][j-1] + 1
            } else {
                dp[i-1][j].max(dp[i][j-1])
            };
        }
    }
    dp[m][n]
}
}

9.5 旅行商问题（TSP）

给定 $n$ 个城市和它们之间的距离，求一条经过所有城市恰好一次并回到起点的最短回路。

TSP 是经典的 NP-hard 问题。暴力求解时间复杂度为 $O(n!)$，动态规划（Held-Karp 算法）可优化至 $O(n^2 \cdot 2^n)$。

9.6 八皇后问题

在 $8 \times 8$ 的国际象棋棋盘上放置 8 个皇后，使得任意两个皇后都不能互相攻击（不同行、不同列、不同对角线）。共有 92 种解法。

#![allow(unused)]
fn main() {
fn solve_n_queens(n: usize) -> Vec<Vec<usize>> {
    let mut solutions = Vec::new();
    let mut cols = vec![0usize; n];
    backtrack(0, n, &mut cols, &mut solutions);
    solutions
}

fn backtrack(row: usize, n: usize, cols: &mut Vec<usize>, solutions: &mut Vec<Vec<usize>>) {
    if row == n {
        solutions.push(cols.clone());
        return;
    }
    for col in 0..n {
        if is_safe(row, col, cols) {
            cols[row] = col;
            backtrack(row + 1, n, cols, solutions);
        }
    }
}

fn is_safe(row: usize, col: usize, cols: &[usize]) -> bool {
    for i in 0..row {
        if cols[i] == col
            || (cols[i] as isize - col as isize).abs() == (row as isize - i as isize)
        {
            return false;
        }
    }
    true
}
}

十、数据结构经典问题

10.1 约瑟夫环（Josephus Problem）

$n$ 个人围成一圈，从第 1 人开始报数，每报到 $m$ 的人出局，求最后幸存者的编号。

递推公式：

$$J(1) = 0, \quad J(n) = (J(n-1) + m) \bmod n$$

#![allow(unused)]
fn main() {
fn josephus(n: usize, m: usize) -> usize {
    let mut pos = 0usize;
    for i in 2..=n {
        pos = (pos + m) % i;
    }
    pos
}
}

10.2 表达式求值与逆波兰表示法

将中缀表达式 3 + 4 * 2 转换为后缀表达式（逆波兰表示法）3 4 2 * +，可用栈高效求值。

#![allow(unused)]
fn main() {
fn eval_rpn(tokens: &[&str]) -> f64 {
    let mut stack: Vec<f64> = Vec::new();
    for &token in tokens {
        match token {
            "+" | "-" | "*" | "/" => {
                let b = stack.pop().unwrap();
                let a = stack.pop().unwrap();
                let result = match token {
                    "+" => a + b,
                    "-" => a - b,
                    "*" => a * b,
                    "/" => a / b,
                    _ => unreachable!(),
                };
                stack.push(result);
            }
            _ => stack.push(token.parse().unwrap()),
        }
    }
    stack.pop().unwrap()
}
}

10.3 图的遍历：BFS 与 DFS

#![allow(unused)]
fn main() {
use std::collections::VecDeque;

fn bfs(adj: &[Vec<usize>], start: usize) -> Vec<usize> {
    let n = adj.len();
    let mut visited = vec![false; n];
    let mut order = Vec::new();
    let mut queue = VecDeque::new();
    visited[start] = true;
    queue.push_back(start);
    while let Some(u) = queue.pop_front() {
        order.push(u);
        for &v in &adj[u] {
            if !visited[v] {
                visited[v] = true;
                queue.push_back(v);
            }
        }
    }
    order
}
}

十一、计算理论与复杂度经典问题

11.1 P vs NP 问题

P：能在多项式时间内求解的问题。

NP：能在多项式时间内验证解的问题。

核心问题：$P = NP$ 是否成立？这是计算机科学最重要的未解之谜，也是克雷数学研究所七大千禧年难题之一（悬赏 100 万美元）。

11.2 停机问题（Halting Problem）

1936 年，图灵证明：不存在一个通用算法，能判定任意程序在任意输入上是否会停机。

这是计算理论的核心结论，证明了计算的固有局限性。

11.3 复杂度类全景

十二、操作系统与网络经典问题

12.1 哲学家就餐问题

5 位哲学家围坐圆桌，每人左右各有一根筷子。哲学家交替思考和进餐，进餐需同时拿到左右两根筷子。如何设计算法避免死锁？

12.2 生产者-消费者问题

生产者向缓冲区写入数据，消费者从缓冲区读取数据。需要用信号量或条件变量同步，避免缓冲区溢出或下溢。

#![allow(unused)]
fn main() {
use std::sync::{Arc, Mutex, Condvar};
use std::collections::VecDeque;

struct Buffer<T> {
    queue: Mutex<VecDeque<T>>,
    capacity: usize,
    not_full: Condvar,
    not_empty: Condvar,
}

impl<T> Buffer<T> {
    fn new(capacity: usize) -> Self {
        Buffer {
            queue: Mutex::new(VecDeque::with_capacity(capacity)),
            capacity,
            not_full: Condvar::new(),
            not_empty: Condvar::new(),
        }
    }

    fn produce(&self, item: T) {
        let mut queue = self.queue.lock().unwrap();
        while queue.len() >= self.capacity {
            queue = self.not_full.wait(queue).unwrap();
        }
        queue.push_back(item);
        self.not_empty.notify_one();
    }

    fn consume(&self) -> T {
        let mut queue = self.queue.lock().unwrap();
        while queue.is_empty() {
            queue = self.not_empty.wait(queue).unwrap();
        }
        let item = queue.pop_front().unwrap();
        self.not_full.notify_one();
        item
    }
}
}

12.3 拜占庭将军问题

在分布式系统中，部分节点可能故障或恶意作恶。如何在存在叛徒的情况下达成共识？

结论： 若系统有 $f$ 个故障节点，至少需要 $3f + 1$ 个节点才能达成共识（即容忍 $f$ 个叛徒需要总共 $n \geq 3f+1$ 个节点）。

这是区块链共识算法（PoW、PoS、BFT）的理论基础。

十三、人工智能与博弈经典问题

13.1 图灵测试

1950 年，图灵在论文《计算机器与智能》中提出：如果一台机器能在对话中让人类无法分辨对方是人还是机器，则可以认为该机器具有智能。

13.2 蒙特霍尔问题（三门问题）

参赛者面对三扇门，其中一扇后有汽车，两扇后是山羊。参赛者选择一扇后，主持人打开另一扇有山羊的门，问：是否换门？

答案：换门。 换门后中奖概率从 $\frac{1}{3}$ 提升到 $\frac{2}{3}$。

$$P(\text{换门赢}) = \frac{2}{3}, \quad P(\text{不换赢}) = \frac{1}{3}$$

13.3 极小化极大（Minimax）与井字棋

Minimax 是博弈搜索的核心算法：假设对手采取最优策略，选择使自己收益最大化的行动。

对于井字棋（Tic-Tac-Toe），完整博弈树仅有约 255,168 个节点，可以完全搜索得出最优策略——双方均最优时必然平局。

十四、经典问题索引

算法与数据结构

计算理论与数学

系统与工程

十五、学习资源

• LeetCode
• Project Euler — 数学与编程挑战
• The Algorithms — 开源算法实现集合
• rust-by-example
• leetcode-rust
• MindSpore 官方文档
• 中国互联网联合辟谣平台
• freebuf 网络安全行业门户

向量知识库