Жадный алгоритм для египетских дробей — жадный алгоритм, который преобразует рациональные числа в египетские дроби, на каждом шаге выбирая наибольшую из возможных аликвотных дробей, которая может быть использована в остаточной дроби.
Разложение, полученное жадным алгоритмом для числа x {displaystyle x} , называется жадным египетским разложением, разложением Сильвестра или разложением Фибоначчи — Сильвестра числа x {displaystyle x} .
История
Среди нескольких различных методов построения египетских дробей, приведённых Фибоначчи в «Книге абака», был жадный алгоритм, который предлагался к применению, лишь если прочие методы не сработали. Впоследствии жадный алгоритм и его расширения для приближения иррациональных чисел был переоткрыт несколько раз, наиболее ранний и известный случай — алгоритм Сильвестра. Метод, дающий ближайшее приближение на каждом шаге, для чего разрешаются отрицательные дроби, принадлежит Ламберту.
Алгоритм и примеры
Алгоритм Фибоначчи осуществляет разложение x / y {displaystyle x/y} путём последовательного проведения замены:
x y = 1 ⌈ y / x ⌉ + ( − y ) mod x y ⌈ y / x ⌉ {displaystyle {frac {x}{y}}={frac {1}{lceil y/x ceil }}+{frac {(-y){mod {x}}}{ylceil y/x ceil }}}(упрощая второй член, если необходимо). Например:
7 15 = 1 3 + 2 15 = 1 3 + 1 8 + 1 120 {displaystyle {frac {7}{15}}={frac {1}{3}}+{frac {2}{15}}={frac {1}{3}}+{frac {1}{8}}+{frac {1}{120}}} .В этом разложении знаменатель 3 {displaystyle 3} первой аликвотной дроби является результатом округления 15 / 7 {displaystyle 15/7} до следующего (большего) целого числа, а остаток 2 / 15 {displaystyle 2/15} — результат сокращения ( − 15 ( mod 7 ) ) / ( 15 ⋅ 3 ) = 6 / 45 {displaystyle (-15{pmod {7}})/(15cdot 3)=6/45} . Делитель второй дроби — 8 {displaystyle 8} , — является результатом округления 15 / 2 {displaystyle 15/2} до следующего (большего) целого числа, а остаток 1 / 120 {displaystyle 1/120} — это то, что осталось от 7 / 15 {displaystyle 7/15} после вычитания 1 / 3 {displaystyle 1/3} и 1 / 8 {displaystyle 1/8} .
Поскольку каждый шаг разложения уменьшает числитель остаточной дроби, этот метод завершится за конечное число шагов. Однако, по сравнению с древними египетскими методами разложения или более современными методами, этот метод может дать разложение с довольно большими знаменателями. Например, жадное разложение числа 5 / 121 {displaystyle 5/121} :
1 25 + 1 757 + 1 763309 + 1 873960180913 + 1 1527612795642093418846225 {displaystyle {frac {1}{25}}+{frac {1}{757}}+{frac {1}{763309}}+{frac {1}{873960180913}}+{frac {1}{1527612795642093418846225}}} ,в то время как другие методы дают куда более простое разложение:
5 121 = 1 33 + 1 121 + 1 363 {displaystyle {frac {5}{121}}={frac {1}{33}}+{frac {1}{121}}+{frac {1}{363}}} ,а для 31 / 311 {displaystyle 31/311} жадный алгоритм даёт разложение на десять дробей, последняя из которых имеет в знаменателе 500 знаков, тогда как существует представление:
1 12 + 1 63 + 1 2799 + 1 8708 {displaystyle {frac {1}{12}}+{frac {1}{63}}+{frac {1}{2799}}+{frac {1}{8708}}} .Последовательность Сильвестра
Последовательность Сильвестра 2 , 3 , 7 , 43 , 1807 , … {displaystyle 2,3,7,43,1807,dots } можно представить как образованную бесконечным разложением единицы посредством жадного алгоритма, где на каждом шаге выбирается знаменатель ⌊ y / x ⌋ + 1 {displaystyle lfloor y/x floor +1} вместо ⌈ y / x ⌉ {displaystyle lceil y/x ceil } . Если оборвать эту последовательность k {displaystyle k} членами и образовать соответствующую египетскую дробь, например, для k = 4 {displaystyle k=4} :
1 2 + 1 3 + 1 7 + 1 43 = 1805 1806 {displaystyle {frac {1}{2}}+{frac {1}{3}}+{frac {1}{7}}+{frac {1}{43}}={frac {1805}{1806}}} ,то получается ближайшее приближение к 1 {displaystyle 1} снизу среди египетских дробей с k {displaystyle k} членами. Например, для любой египетской дроби для числа в открытом интервале ( 1805 / 1806 , 1 ) {displaystyle (1805/1806,1)} требуется по меньшей мере пять членов. Описано применение таких ближайших разложений для нижней оценки числа делителей совершенного числа, а также в теории групп.
Разложения максимальной длины и условия сравнения по модулю
Любая дробь x / y {displaystyle x/y} даёт максимум x {displaystyle x} членов в жадном алгоритме. Исследованы условия, при которых для разложения x / y {displaystyle x/y} необходимо в точности x {displaystyle x} дробей, эти условия можно описать в терминах сравнений y {displaystyle y} по модулю:
- любая дробь 1 / y {displaystyle 1/y} приводит к одному члену в разложении, самая простая такая дробь — 1 / 1 {displaystyle 1/1} ;
- любая дробь вида 2 / y {displaystyle 2/y} для нечётных y > 1 {displaystyle y>1} требует двух членов в разложении, самая простая такая дробь — 2 / 3 {displaystyle 2/3} ;
- в разложении дроби 3 / y {displaystyle 3/y} необходимы три члена в том и только в том случае, когда y ≡ 1 ( mod 6 ) {displaystyle yequiv 1{pmod {6}}} , в этом случае — y = 2 ( mod x ) {displaystyle y=2{pmod {x}}} и y ( y + 2 ) / 3 {displaystyle y(y+2)/3} нечётно, так что остаток разложения после первого шага: ( − y ) mod x y ⌈ y / x ⌉ = 2 y ( y + 2 ) / 3 {displaystyle {frac {(-y){mod {x}}}{ylceil y/x ceil }}={frac {2}{y(y+2)/3}}} несократим, самая простая дробь вида 3 / y {displaystyle 3/y} , дающая разложение с тремя членами — 3 / 7 {displaystyle 3/7} ;
- разложение дроби 4 / y {displaystyle 4/y} даёт четыре члена тогда и только тогда, когда y ≡ 1 ( mod 24 ) {displaystyle yequiv 1{pmod {24}}} или y ≡ 17 ( mod 24 ) {displaystyle yequiv 17{pmod {24}}} . В этих случаях числитель — y mod x {displaystyle y{mod {x}}} остаточной дроби равен 3 {displaystyle 3} и знаменатель сравним с 1 ( mod 6 ) {displaystyle 1{pmod {6}}} . Самая простая дробь вида 4 / y {displaystyle 4/y} с четырьмя членами разложения — 4 / 17 {displaystyle 4/17} , гипотеза Эрдёша — Штрауса утверждает, что все дроби вида 4 / y {displaystyle 4/y} имеют разложение с тремя или меньше членами, но при y ≡ 1 ( mod 2 ) 4 {displaystyle yequiv 1{pmod {2}}4} или y ≡ 17 ( mod 2 ) 4 {displaystyle yequiv 17{pmod {2}}4} такие разложения следует искать методами, отличными от жадного алгоритма.
В общем случае последовательность дробей x / y {displaystyle x/y} с минимальным знаменателем y {displaystyle y} , имеющих разложение жадным алгоритмом с x {displaystyle x} членами:
1 , 2 3 , 3 7 , 4 17 , 5 31 , 6 109 , 7 253 , 8 97 , 9 271 , … {displaystyle 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 } .Приближённое вычисление корней многочленов
Существует метод приближённого вычисления корней многочлена, основанный на жадном алгоритме, определяющем жадное разложение корня. На каждом шаге образуется дополнительный многочлен, который имеет остаток разложения в качестве корня. Например, для вычисления жадного разложения золотого сечения как одного из двух решений уравнения P 0 ( x ) = x 2 − x − 1 = 0 {displaystyle P_{0}(x)=x^{2}-x-1=0} алгоритм осуществляет следующие шаги.
Продолжая этот процесс приближения, получается разложение золотого сечения в египетскую дробь:
φ = 1 1 + 1 2 + 1 9 + 1 145 + 1 37986 + ⋯ {displaystyle varphi ={frac {1}{1}}+{frac {1}{2}}+{frac {1}{9}}+{frac {1}{145}}+{frac {1}{37986}}+cdots } .Другие целочисленные последовательности
Длина, минимальный знаменатель и максимальный знаменатель жадного разложения для дробей с малыми числителями и знаменателями включены в Энциклопедии целочисленных последовательностей. Кроме того, жадное разложение любого иррационального числа приводит к бесконечной возрастающей последовательности целых, и OEIS содержит разложения некоторых хорошо известных констант.
Связанные разложения
Возможно определить жадный алгоритм с некоторыми ограничениями на знаменатель:
x y = 1 d + x d − y y d {displaystyle {frac {x}{y}}={frac {1}{d}}+{frac {xd-y}{yd}}} ,где d {displaystyle d} выбирается среди всех значений, которые удовлетворяют наложенным ограничениям и имеют как можно меньшее значение, при котором x d > y {displaystyle xd>y} и такое, что d {displaystyle d} отличается от всех предыдущих знаменателей. Например, разложение Энгеля можно рассматривать как алгоритм этого типа, в котором каждый допустимый знаменатель должен быть получен умножением предыдущего на некоторое целое число. Однако зачастую нетривиально установить, приводит ли такой алгоритм всегда к конечному разложению. В частности нечётное жадное разложение дроби x / y {displaystyle x/y} образуется жадным алгоритмом с ограничением на нечётность знаменателей. Известно, что при нечётном y {displaystyle y} существует разложение в египетскую дробь, в которой все знаменатели нечётны, но приведёт ли нечётный жадный алгоритм всегда к конечному разложению — неизвестно.