Fotools
ru

Рациональное приближение/разложение непрерывных дробей

Введите реальный номер

Быстрый пример:

Результат расчета

После ввода цифр нажмите Начать расчет.

Описание алгоритма:

1. Продолжительная фракция:
Любое действительное число 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. Конвергенты:
Дробь, полученная путем перехвата первых n членов цепной дроби, называется n-й асимптотической дробью и записывается как pn/qn:
  • р-1 = 1, q-1 = 0
  • р0 = a₀, q0 = 1
  • Формула рекурсии: pn = an·p(n-1) + p(n-2)
  • Формула рекурсии: qn = an·q(n-1) + q(n-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, ...] (периодическая непрерывная дробь)
  • е:[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)
  • Теория музыки:Интервальная гармония связана с простотой разложения цепных дробей.
  • астрономия:Рациональное приближение для расчета периода движения планет
  • Теория чисел:Диофантово приближение, решение уравнения Пелля
  • Компьютерная графика:Алгоритм прямых линий Брезенхема и т. д.