JSER

有理逼近 / 连分数展开

输入实数

快速示例：

计算结果

输入数字后点击"开始计算"

算法说明：

1. 连分数（Continued Fraction）：
任何实数 x 都可以表示为连分数形式：
x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ...)))
简记为: x = [a₀; a₁, a₂, a₃, ...]
  • a₀ = ⌊x⌋（x 的整数部分）
  • 如果 x 不是整数，令 x₁ = 1/(x - a₀)，继续计算 a₁ = ⌊x₁⌋
  • 重复此过程，得到 a₂, a₃, ...
  • 有理数的连分数展开是有限的
  • 无理数的连分数展开是无限的
2. 渐近分数（Convergents）：
截取连分数的前 n 项得到的分数称为第 n 个渐近分数，记为 pn/qn：
  • p-1 = 1, q-1 = 0
  • p0 = a₀, q0 = 1
  • 递推公式：pn = an·pn-1 + pn-2
  • 递推公式：qn = an·qn-1 + qn-2
  • 渐近分数是原数的最佳有理逼近
3. 最佳有理逼近：
  • 对于给定的实数 x 和分母上界 Q，找到分数 p/q (q ≤ Q) 使得 |x - p/q| 最小
  • 连分数的渐近分数给出了所有最佳有理逼近
  • 如果 p/q 是 x 的渐近分数，则对于所有 q' < q，都有 |x - p/q| < |x - p'/q'|
4. 特殊数的连分数：
  • 黄金比例 φ：[1; 1, 1, 1, 1, ...] (全为1，最慢收敛)
  • √2：[1; 2, 2, 2, 2, ...] (周期连分数)
  • e：[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...] (有规律)
  • π：[3; 7, 15, 1, 292, 1, ...] (无明显规律)

算法复杂度：

  • 时间复杂度：O(n)，其中 n 是展开的项数
  • 空间复杂度：O(n)，需要存储所有系数和渐近分数
  • 数值稳定性：使用高精度浮点数或大整数可避免精度损失

应用场景：

  • 数值计算：用简单分数近似复杂无理数（如 π ≈ 22/7, 355/113）
  • 音乐理论：音程和谐度与连分数展开的简单性相关
  • 天文学：计算行星运动周期的有理近似
  • 数论：丢番图逼近、佩尔方程的解
  • 计算机图形：Bresenham 直线算法等