Fotools
uk

Раціональне наближення/розклад у неперервний дроб

Введіть дійсне число

Швидкий приклад:

Результат розрахунку

Після введення чисел натисніть «Почати обчислення».

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

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, ...] (Усі 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)
  • Теорія музики:Інтервальна гармонія пов’язана з простотою розкладів неперервних дробів
  • астрономія:Раціональне наближення для обчислення періоду руху планет
  • Теорія чисел:Діофантове наближення, розв'язок рівняння Пелля
  • Комп'ютерна графіка:прямолінійний алгоритм Брезенхема тощо.