Fotools
vi

Xấp xỉ hữu tỉ / Khai triển phân số liên tục

Nhập số thực

Ví dụ nhanh:

Kết quả tính toán

Nhập số rồi nhấn Bắt đầu tính toán

Mô tả thuật toán:

1. Phân số liên tục:
Mọi số thực x đều có thể biểu diễn dưới dạng phân số liên tục:
x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ...)))
Viết tắt: x = [a₀; a₁, a₂, a₃, ...]
  • a₀ = ⌊x⌋ (phần nguyên của x)
  • Nếu x không phải số nguyên, đặt x₁ = 1/(x - a₀), tiếp tục với a₁ = ⌊x₁⌋
  • Lặp lại quá trình để có a₂, a₃, ...
  • Khai triển phân số liên tục của số hữu tỉ là hữu hạn
  • Khai triển phân số liên tục của số vô tỉ là vô hạn
2. Phân số hội tụ:
Phân số lấy từ n hạng đầu được gọi là phân số hội tụ thứ n, ký hiệu pn/qn:
  • p-1 = 1, q-1 = 0
  • p0 = a₀, q0 = 1
  • Công thức truy hồi: pn = an·p(n-1) + p(n-2)
  • Công thức truy hồi: qn = an·q(n-1) + q(n-2)
  • Phân số hội tụ là xấp xỉ hữu tỉ tốt nhất của số gốc
3. Xấp xỉ hữu tỉ tốt nhất:
  • Với số thực x và giới hạn trên Q của mẫu số, tìm phân số p/q (q ≤ Q) sao cho |x - p/q| nhỏ nhất
  • Các phân số hội tụ của phân số liên tục cho tất cả xấp xỉ hữu tỉ tốt nhất
  • Nếu p/q là phân số hội tụ của x, thì với mọi q' < q, |x - p/q| < |x - p'/q'|
4. Phân số liên tục của các số đặc biệt:
  • Tỷ lệ vàng φ:[1; 1, 1, 1, 1, ...] (Toàn số 1, hội tụ chậm nhất)
  • √2:[1; 2, 2, 2, 2, ...] (Phân số liên tục tuần hoàn)
  • e:[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...] (Có quy luật)
  • π:[3; 7, 15, 1, 292, 1, ...] (Không có quy luật rõ ràng)

Độ phức tạp thuật toán:

  • Độ phức tạp thời gian:O(n)，trong đó n là số hạng khai triển
  • Độ phức tạp không gian:O(n)，Cần lưu trữ tất cả các hệ số và phân số hội tụ
  • Độ ổn định số học:Sử dụng số dấu phẩy động độ chính xác cao hoặc số nguyên lớn để tránh mất độ chính xác

Các tình huống ứng dụng:

  • Tính toán số học:Xấp xỉ số vô tỉ phức tạp bằng phân số đơn giản (ví dụ π ≈ 22/7, 355/113)
  • Lý thuyết âm nhạc:Sự hòa âm của quãng nhạc liên quan đến tính đơn giản của khai triển phân số liên tục
  • Thiên văn học:Xấp xỉ hữu tỉ để tính chu kỳ quỹ đạo hành tinh
  • Lý thuyết số:Xấp xỉ Diophantine, nghiệm của phương trình Pell
  • Đồ họa máy tính:Thuật toán đường thẳng Bresenham và các ứng dụng khác