Processing math: 93%

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

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

История


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

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


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

xy=1y/x+(y)modxyy/x
 (упрощая второй член, если необходимо). Например:

715=13+215=13+18+1120.
 В этом разложении знаменатель 3 первой аликвотной дроби являетсярезультатом округления 15/7 до следующего (большего) целого числа, аостаток 2/15 — результат сокращения(15(mod7))/(153)=6/45. Делитель второй дроби —8, — является результатом округления 15/2 до следующего (большего)целого числа, а остаток 1/120 — это то, что осталось от 7/15 послевычитания 1/3 и 1/8.
 Поскольку каждый шаг разложения уменьшает числитель остаточной дроби,этот метод завершится за конечное число шагов. Однако, по сравнению сдревними египетскими методами разложения или более современнымиметодами, этот метод может дать разложение с довольно большимизнаменателями. Например, жадное разложение числа 5/121:

125+1757+1763309+1873960180913+11527612795642093418846225,
 в то время как другие методы дают куда более простое разложение:

5121=133+1121+1363,
 а для 31/311 жадный алгоритм даёт разложение на десять дробей,последняя из которых имеет в знаменателе 500 знаков, тогда каксуществует представление:

112+163+12799+18708.

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


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

12+13+17+143=18051806,
 то получается ближайшее приближение к 1 снизу среди египетских дробейс k членами. Например, для любой египетской дроби для числа в открытоминтервале (1805/1806,1) требуется по меньшей мере пять членов.Описано применение таких ближайших разложений для нижней оценки числаделителей совершенного числа, а также в теории групп.

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


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

  • любая дробь 1/y приводит к одному члену в разложении, самая простая такая дробь — 1/1;
  • любая дробь вида 2/y для нечётных y>1 требует двух членов в разложении, самая простая такая дробь — 2/3;
  • в разложении дроби 3/y необходимы три члена в том и только в том случае, когда y1(mod6), в этом случае — y=2(modx) и y(y+2)/3 нечётно, так что остаток разложения после первого шага:
    (y)modxyy/x=2y(y+2)/3
  • разложение дроби 4/y даёт четыре члена тогда и только тогда, когда y1(mod24) или y17(mod24). В этих случаях числитель — ymodx остаточной дроби равен 3 и знаменатель сравним с 1(mod6). Самая простая дробь вида 4/y с четырьмя членами разложения — 4/17, гипотеза Эрдёша — Штрауса утверждает, что все дроби вида 4/y имеют разложение с тремя или меньше членами, но при y1(mod2)4 или y17(mod2)4 такие разложения следует искать методами, отличными от жадного алгоритма.

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

1,23,37,417,531,6109,7253,897,9271,.

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


 Существует метод приближённого вычисления корней многочлена, основанныйна жадном алгоритме, определяющем жадное разложение корня. На каждомшаге образуется дополнительный многочлен, который имеет остатокразложения в качестве корня. Например, для вычисления жадного разложениязолотого сечения как одного из двух решений уравненияP0(x)=x2x1=0 алгоритм осуществляет следующие шаги.

  1. Поскольку P0(x)<0 для x=1 и P0(x)>0 для всех x2, корень P0(x) должен находиться между 1 и 2. Таким образом, первый член разложения — 1/1. Если x1 — остаток после первого шага жадного разложения, должно выполняться уравнение P0(x1+1)=0, которое можно преобразовать в P1(x1)=x21+x11=0.
  2. Поскольку P1(x)<0 для x=1/2 и P1(x)>0 для всех x>1, корень P1 лежит между 1/2 и 1, первый член в разложении x1 (второй член в разложении золотого сечения) равен 1/2. Если x2 — остаток после этого шага жадного разложения, он удовлетворяет уравнению P1(x2+1/2)=0, которое можно преобразовать в P2(x2)=4x22+8x21=0.
  3. Поскольку P2(x)<0 для x=1/9 и P2(x)>0 для всех x>1/8, следующим членом разложения будет 1/9. Если x3 — остаток после этого шага жадного разложения, он удовлетворяет уравнению P2(x3+1/9)=0, которое можно преобразовать в уравнение с целыми коэффициентами P3(x3)=324x23+720x35=0.

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

φ=11+12+19+1145+137986+.

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


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

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


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

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