Русская Википедия:Жадный алгоритм для египетских дробей

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Жадный алгоритм для египетских дробей — жадный алгоритм, который преобразует рациональные числа в египетские дроби, на каждом шаге выбирая наибольшую из возможных аликвотных дробей, которая может быть использована в остаточной дроби.

Разложение, полученное жадным алгоритмом для числа <math>x</math>, называется жадным египетским разложением, разложением Сильвестра или разложением Фибоначчи — Сильвестра числа <math>x</math>.

История

Среди нескольких различных методов построения египетских дробей, приведённых Фибоначчи в «Книге абака», был жадный алгоритм, который предлагался к применению, лишь если прочие методы не сработали. Впоследствии жадный алгоритм и его расширения для приближения иррациональных чисел был переоткрыт несколько раз, наиболее ранний и известный случай — алгоритм СильвестраШаблон:SfnШаблон:Sfn. Метод, дающий ближайшее приближение на каждом шаге, для чего разрешаются отрицательные дроби, принадлежит ЛамбертуШаблон:Sfn.

Алгоритм и примеры

Алгоритм Фибоначчи осуществляет разложение <math>x/y</math> путём последовательного проведения замены:

<math>\frac{x}{y}=\frac{1}{\lceil y/x\rceil}+\frac{(-y) \bmod x}{y\lceil y/x\rceil}</math>

(упрощая второй член, если необходимо). Например:

<math>\frac{7}{15}=\frac{1}{3}+\frac{2}{15}=\frac{1}{3}+\frac{1}{8}+\frac{1}{120}</math>.

В этом разложении знаменатель <math>3</math> первой аликвотной дроби является результатом округления <math>15/7</math> до следующего (большего) целого числа, а остаток <math>2/15</math> — результат сокращения <math>(-15 \pmod 7) / (15 \cdot 3) = 6/45</math>. Делитель второй дроби — <math>8</math>, — является результатом округления <math>15/2</math> до следующего (большего) целого числа, а остаток <math>1/120</math> — это то, что осталось от <math>7/15</math> после вычитания <math>1/3</math> и <math>1/8</math>.

Поскольку каждый шаг разложения уменьшает числитель остаточной дроби, этот метод завершится за конечное число шагов. Однако, по сравнению с древними египетскими методами разложения или более современными методами, этот метод может дать разложение с довольно большими знаменателями. Например, жадное разложение числа <math>5/121</math>:

<math>\frac{1}{25}+\frac{1}{757}+\frac{1}{763309}+\frac{1}{873960180913}+\frac{1}{1527612795642093418846225}</math>,

в то время как другие методы дают куда более простое разложение:

<math>\frac{5}{121}=\frac{1}{33}+\frac{1}{121}+\frac{1}{363}</math>,

а для <math>31/311</math> жадный алгоритм даёт разложение на десять дробей, последняя из которых имеет в знаменателе 500 знаков, тогда как существует представлениеШаблон:Sfn:

<math>\frac 1{12} + \frac 1{63} + \frac 1{2799} + \frac 1{8708}</math>.

Последовательность Сильвестра

Последовательность Сильвестра <math>2, 3, 7, 43, 1807, \dots</math> можно представить как образованную бесконечным разложением единицы посредством жадного алгоритма, где на каждом шаге выбирается знаменатель <math>\lfloor y/x\rfloor+1</math> вместо <math>\lceil y/x\rceil</math>. Если оборвать эту последовательность <math>k</math> членами и образовать соответствующую египетскую дробь, например, для <math>k = 4</math>:

<math>\frac12+\frac13+\frac17+\frac1{43}=\frac{1805}{1806}</math>,

то получается ближайшее приближение к <math>1</math> снизу среди египетских дробей с <math>k</math> членамиШаблон:SfnШаблон:Sfn. Например, для любой египетской дроби для числа в открытом интервале <math>(1805/1806, 1)</math> требуется по меньшей мере пять членов. Описано применение таких ближайших разложений для нижней оценки числа делителей совершенного числаШаблон:Sfn, а также в теории группШаблон:Sfn.

Разложения максимальной длины и условия сравнения по модулю

Любая дробь <math>x/y</math> даёт максимум <math>x</math> членов в жадном алгоритме. Исследованы условия, при которых для разложения <math>x/y</math> необходимо в точности <math>x</math> дробейШаблон:SfnШаблон:Sfn, эти условия можно описать в терминах сравнений <math>y</math> по модулю:

• любая дробь <math>1/y</math> приводит к одному члену в разложении, самая простая такая дробь — <math>1/1</math>;
• любая дробь вида <math>2/y</math> для нечётных <math>y > 1</math> требует двух членов в разложении, самая простая такая дробь — <math>2/3</math>;
• в разложении дроби <math>3/y</math> необходимы три члена в том и только в том случае, когда <math>y \equiv 1 \pmod 6</math>, в этом случае — <math>y = 2 \pmod x</math> и <math>y(y+2)/3</math> нечётно, так что остаток разложения после первого шага:

  <math>\frac{(-y)\bmod x}{y\lceil y/x\rceil} = \frac2{y(y+2)/3}</math>

  несократим, самая простая дробь вида <math>3/y</math>, дающая разложение с тремя членами — <math>3/7</math>;

• разложение дроби <math>4/y</math> даёт четыре члена тогда и только тогда, когда <math>y \equiv 1 \pmod {24}</math> или <math>y \equiv 17 \pmod {24}</math>. В этих случаях числитель — <math>y \bmod x</math> остаточной дроби равен <math>3</math> и знаменатель сравним с <math>1 \pmod 6</math>. Самая простая дробь вида <math>4/y</math> с четырьмя членами разложения — <math>4/17</math>, гипотеза Эрдёша — Штрауса утверждает, что все дроби вида <math>4/y</math> имеют разложение с тремя или меньше членами, но при <math>y \equiv 1 \pmod 24</math> или <math>y \equiv 17 \pmod 24</math> такие разложения следует искать методами, отличными от жадного алгоритма.

В общем случае последовательность дробей <math>x/y</math> с минимальным знаменателем <math>y</math>, имеющих разложение жадным алгоритмом с <math>x</math> членами:

<math>1, \frac{2}{3}, \frac{3}{7}, \frac{4}{17}, \frac{5}{31}, \frac{6}{109}, \frac{7}{253}, \frac{8}{97}, \frac{9}{271}, \dots</math>.

Приближённое вычисление корней многочленов

Существует метод приближённого вычисления корней многочлена, основанный на жадном алгоритмеШаблон:SfnШаблон:Sfn, определяющем жадное разложение корня. На каждом шаге образуется дополнительный многочлен, который имеет остаток разложения в качестве корня. Например, для вычисления жадного разложения золотого сечения как одного из двух решений уравнения <math>P_0(x) = x^2 - x -1 = 0</math> алгоритм осуществляет следующие шаги.

1. Поскольку <math>P_0(x) < 0</math> для <math>x = 1</math> и <math>P_0(x) > 0</math> для всех <math>x \geqslant 2</math>, корень <math>P_0(x)</math> должен находиться между <math>1</math> и <math>2</math>. Таким образом, первый член разложения — <math>1/1</math>. Если <math>x_1</math> — остаток после первого шага жадного разложения, должно выполняться уравнение <math>P_0(x_1 + 1) = 0</math>, которое можно преобразовать в <math>P_1(x_1) = x_1^2 + x_1 - 1 = 0</math>.
2. Поскольку <math>P_1(x) < 0</math> для <math>x = 1/2</math> и <math>P_1(x) > 0</math> для всех <math>x > 1</math>, корень <math>P_1</math> лежит между <math>1/2</math> и <math>1</math>, первый член в разложении <math>x_1</math> (второй член в разложении золотого сечения) равен <math>1/2</math>. Если <math>x_2</math> — остаток после этого шага жадного разложения, он удовлетворяет уравнению <math>P_1(x_2 + 1/2) = 0</math>, которое можно преобразовать в <math>P_2(x_2) = 4x_2^2 + 8x_2 -1 = 0</math>.
3. Поскольку <math>P_2(x) < 0</math> для <math>x = 1/9</math> и <math>P_2(x) > 0</math> для всех <math>x > 1/8</math>, следующим членом разложения будет <math>1/9</math>. Если <math>x_3</math> — остаток после этого шага жадного разложения, он удовлетворяет уравнению <math>P_2(x_3 + 1/9) = 0</math>, которое можно преобразовать в уравнение с целыми коэффициентами <math>P_3(x_3) = 324x_3^2 + 720x_3 - 5 = 0</math>.

Продолжая этот процесс приближения, получается разложение золотого сечения в египетскую дробь:

<math>\varphi = \frac11+\frac12+\frac19+\frac1{145}+\frac1{37986}+\cdots</math>.

Другие целочисленные последовательности

Длина, минимальный знаменатель и максимальный знаменатель жадного разложения для дробей с малыми числителями и знаменателями включены в Энциклопедии целочисленных последовательностей. Кроме того, жадное разложение любого иррационального числа приводит к бесконечной возрастающей последовательности целых, и OEIS содержит разложения некоторых хорошо известных констант.

Связанные разложения

Возможно определить жадный алгоритм с некоторыми ограничениями на знаменатель:

<math>\frac{x}{y}=\frac{1}{d}+\frac{xd-y}{yd}</math>,

где <math>d</math> выбирается среди всех значений, которые удовлетворяют наложенным ограничениям и имеют как можно меньшее значение, при котором <math>xd > y</math> и такое, что <math>d</math> отличается от всех предыдущих знаменателей. Например, разложение Энгеля можно рассматривать как алгоритм этого типа, в котором каждый допустимый знаменатель должен быть получен умножением предыдущего на некоторое целое число. Однако зачастую нетривиально установить, приводит ли такой алгоритм всегда к конечному разложению. В частности нечётное жадное разложение дроби <math>x/y</math> образуется жадным алгоритмом с ограничением на нечётность знаменателей. Известно, что при нечётном <math>y</math> существует разложение в египетскую дробь, в которой все знаменатели нечётны, но приведёт ли нечётный жадный алгоритм всегда к конечному разложению — неизвестно.

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья