Fotools
bg

Рационално приближение / Разлагане на верижна дроб

Въведете реално число

Бързи примери:

Резултат от изчислението

Въведете число и натиснете Започни изчислението

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

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:
  • p-1 = 1, q-1 = 0
  • p0 = 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, ...] (Всички единици, най-бавна сходимост)
  • √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)
  • Теория на музиката:Консонансът на интервалите е свързан с простотата на разлаганията на верижна дроб
  • Астрономия:Рационални приближения за изчисляване на орбиталните периоди на планетите
  • Теория на числата:Диофантови приближения, решения на уравнението на Пел
  • Компютърна графика:Алгоритъм за права линия на Брезенхам и други