Цепные дроби — это мощный математический инструмент, который находит применение не только в теории чисел, но и в алгоритмах, криптографии и даже в игровых механиках. Давай разберёмся, как они работают и где их можно использовать в играх.
Цепные дроби
Цепная дробь — это способ представления действительного числа в виде последовательности целых чисел. Особенно полезна для построения наилучших рациональных приближений, решения диофантовых уравнений и анализа иррациональных чисел.
Теория
Цепная дробь числа \( x \) записывается как:
\[ x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \ddots}}} \]
где \( a_0 \in \mathbb{Z} \), а \( a_1, a_2, a_3, \ldots \in \mathbb{N} \). Кратко обозначается: \( [a_0; a_1, a_2, a_3, \ldots] \).
- Положим \( x_0 = x \).
- Для \( n = 0, 1, 2, \ldots \):
\( a_n = \lfloor x_n \rfloor \),
\( x_{n+1} = \dfrac{1}{x_n — a_n} \) (если \( x_n \notin \mathbb{Z} \)). - Процесс завершается, когда \( x_n \) становится целым (для рациональных чисел).
- Рациональные числа имеют конечные цепные дроби.
- Иррациональные — бесконечные.
- Квадратичные иррациональности (например, \( \sqrt{2} \)) дают периодические цепные дроби (теорема Лагранжа).
- Подходящие дроби \( \frac{p_n}{q_n} \) — наилучшие рациональные приближения к \( x \) при ограничении на знаменатель.
Типовые задачи
Задача 1: Разложите \( \dfrac{415}{93} \) в цепную дробь.
\( 415 ÷ 93 = 4 \) (ост. 43) → \( a_0 = 4 \)
\( 93 ÷ 43 = 2 \) (ост. 7) → \( a_1 = 2 \)
\( 43 ÷ 7 = 6 \) (ост. 1) → \( a_2 = 6 \)
\( 7 ÷ 1 = 7 \) → \( a_3 = 7 \)
Ответ: \( [4; 2, 6, 7] \)
Задача 2: Найдите первые 4 члена цепной дроби для \( \sqrt{2} \).
\( \sqrt{2} ≈ 1.414 \) → \( a_0 = 1 \)
\( x_1 = \dfrac{1}{\sqrt{2}-1} = \sqrt{2}+1 ≈ 2.414 \) → \( a_1 = 2 \)
Далее процесс повторяется → периодичность.
Ответ: \( [1; \overline{2}] \)
Задача 3: Найдите подходящую дробь \( \dfrac{p_2}{q_2} \) для \( [1; 2, 2, 2, \ldots] \).
Рекуррентные формулы:
\( p_{-1}=1,\ p_0=a_0=1 \)
\( q_{-1}=0,\ q_0=1 \)
\( p_1 = a_1 p_0 + p_{-1} = 2·1 + 1 = 3 \)
\( q_1 = 2·1 + 0 = 2 \)
\( p_2 = 2·3 + 1 = 7,\ q_2 = 2·2 + 1 = 5 \)
Ответ: \( \dfrac{7}{5} \)
Задача 4: Докажите, что \( [1; 1, 1, 1, \ldots] = \dfrac{1+\sqrt{5}}{2} \).
Пусть \( x = 1 + \dfrac{1}{x} \). Тогда \( x^2 = x + 1 \) → \( x^2 — x — 1 = 0 \).
Положительный корень: \( x = \dfrac{1+\sqrt{5}}{2} \) — золотое сечение.
Ответ: \( [1; \overline{1}] = \varphi \)
Конструктор: разложение числа в цепную дробь
Введите положительное число (например: 3.245, sqrt(3), pi):
Где применяются цепные дроби?
Такие дроби помогают находить наилучшие приближения чисел и решать разные задачи..
Рассмотрим конкретные примеры использования цепных дробей в игровых механиках и алгоритмах.
Пример 1: Оптимальные стратегии в играх
Допустим, мы делаем игру, где враги атакуют волнами, и хотим, чтобы интервалы между атаками не были монотонными.
Возьмём число √2 ≈ 1.41421356… и разложим его:
Если чередовать эти интервалы (1.5, 1.4, 1.416, …), атаки будут непредсказуемыми, но не хаотичными!
Пример 2: Алгоритмы сжатия данных
В некоторых алгоритмах (например, JPEG) числа представляют в компактной форме. Цепные дроби помогают найти простые и точные приближения, чтобы уменьшить размер данных.
Пример:
Число 2.542.54 (дюймы в сантиметрах) можно записать как:
(Коэффициенты: [2, 1, 1, 5, 1])
Вместо хранения десятичной части (0.54) можно хранить всего 5 чисел, что иногда выгоднее.
Пример 3: Генерация случайных уровней
Если взять число золотого сечения φ≈1.618…, его цепная дробь выглядит так:
Если использовать его коэффициенты (1, 1, 1, …), можно создавать красивые фрактальные паттерны.
Пример 4. Алгоритм Евклида и НОД (наибольший общий делитель)
Суть алгоритма Евклида заключается в последовательном делении большего числа на меньшее с выделением целой части (частного) и остатка, после чего процесс повторяется для меньшего числа и остатка. Последовательность этих частных и есть коэффициенты цепной дроби, представляющей исходное рациональное число. Таким образом, разложение рационального числа в цепную дробь напрямую соответствует шагам алгоритма Евклида.
Цепные дроби тесно связаны с алгоритмом Евклида. Например, найдём НОД(56, 32):
- 56=1×32+24
- 32=1×24+8
- 24=3×8+0
Коэффициенты (1, 1, 3) — это цепная дробь для 56/32:
Так можно быстро находить сокращение дробей в играх (например, для расчёта шансов выпадения предмета).
Пример 5. Быстрое вычисление квадратных корней (алгоритм без калькулятора)
Быстрое вычисление квадратных корней с помощью цепных дробей основано на разложении квадратного корня из целого числа в периодическую цепную дробь. Этот метод позволяет получать последовательные рациональные приближения к корню, которые с каждым шагом становятся всё точнее.
Основная идея алгоритма
- Квадратные корни из целых чисел (квадратичные иррациональности) имеют периодические цепные дроби. Это значит, что их разложение в цепную дробь повторяется с некоторым периодом.
- Разложение начинается с выделения целой части корня, после чего дробная часть преобразуется так, чтобы избавиться от иррациональности в знаменателе, и повторяется процесс выделения целой части на каждом шаге.
- На каждом шаге получается очередной неполный частный цепной дроби, а последовательные частные дают приближения к корню.
Попробуй разложить в цепную дробь число 13/55.
Ответ
