1. Fração Continuada:
Qualquer número real x pode ser expresso como uma fração contínua:
x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ...)))
Abreviado como: x = [a₀; a₁, a₂, a₃, ...]
- a₀ = ⌊x⌋ (parte inteira de x)
- Se x não for um número inteiro, seja x₁ = 1/(x - a₀) e continue com a₁ = ⌊x₁⌋
- Repita este processo para obter a₂, a₃, ...
- A expansão fracionária contínua de números racionais é finita
- A expansão fracionária contínua de números irracionais é infinita
2. Convergentes:
A fração obtida pela interceptação dos primeiros n termos de uma fração contínua é chamada de n-ésima fração assintótica, registrada como pn/qn:
- p-1 = 1, q-1 = 0
- p0 = a₀, q0 = 1
- Fórmula de recursão: pn = an·p(n-1) + p(n-2)
- Fórmula de recursão: qn = an·q(n-1) + q(n-2)
- Uma fração assintótica é a melhor aproximação racional do número original
3. Melhor aproximação racional:
- Para um determinado número real x e um limite superior no denominador Q, encontre a fração p/q (q ≤ Q) tal que |x - p/q| seja minimizado
- Frações assintóticas de frações contínuas fornecem todas as melhores aproximações racionais
- Se p/q é uma fração assintótica de x, então para todo q' < q, |x - p/q| < |x - p'/q'|
4. Frações contínuas de números especiais:
- Proporção Áurea φ:[1; 1, 1, 1, 1, ...] (Todos 1, convergência mais lenta)
- √2:[1; 2, 2, 2, 2, ...] (fração contínua periódica)
- e:[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...] (Regularmente)
- π:[3; 7, 15, 1, 292, 1, ...] (nenhum padrão óbvio)
Complexidade do algoritmo:
- Complexidade de tempo:O(n)，onde n é o número de termos a serem expandidos
- Complexidade do espaço:O(n)，Todos os coeficientes e frações assintóticas precisam ser armazenados
- Estabilidade numérica:Use números de ponto flutuante de alta precisão ou números inteiros grandes para evitar perda de precisão
Cenários de aplicação:
- Cálculo numérico:Use frações simples para aproximar números irracionais complexos (por exemplo, π ≈ 22/7, 355/113)
- Teoria Musical:A harmonia de intervalo está relacionada à simplicidade das expansões de frações contínuas
- astronomia:Aproximação racional para calcular o período do movimento planetário
- Teoria dos números:Aproximação diofantina, solução da equação de Pell
- Computação Gráfica:Algoritmo de linha reta de Bresenham, etc.