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

4-04-2021, 03:30

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

Разложение, полученное жадным алгоритмом для числа 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} алгоритм осуществляет следующие шаги.

  • Поскольку P 0 ( x ) < 0 {displaystyle P_{0}(x)<0} для x = 1 {displaystyle x=1} и P 0 ( x ) > 0 {displaystyle P_{0}(x)>0} для всех x ⩾ 2 {displaystyle xgeqslant 2} , корень P 0 ( x ) {displaystyle P_{0}(x)} должен находиться между 1 {displaystyle 1} и 2 {displaystyle 2} . Таким образом, первый член разложения — 1 / 1 {displaystyle 1/1} . Если x 1 {displaystyle x_{1}} — остаток после первого шага жадного разложения, должно выполняться уравнение P 0 ( x 1 + 1 ) = 0 {displaystyle P_{0}(x_{1}+1)=0} , которое можно преобразовать в P 1 ( x 1 ) = x 1 2 + x 1 − 1 = 0 {displaystyle P_{1}(x_{1})=x_{1}^{2}+x_{1}-1=0} .
  • Поскольку P 1 ( x ) < 0 {displaystyle P_{1}(x)<0} для x = 1 / 2 {displaystyle x=1/2} и P 1 ( x ) > 0 {displaystyle P_{1}(x)>0} для всех x > 1 {displaystyle x>1} , корень P 1 {displaystyle P_{1}} лежит между 1 / 2 {displaystyle 1/2} и 1 {displaystyle 1} , первый член в разложении x 1 {displaystyle x_{1}} (второй член в разложении золотого сечения) равен 1 / 2 {displaystyle 1/2} . Если x 2 {displaystyle x_{2}} — остаток после этого шага жадного разложения, он удовлетворяет уравнению P 1 ( x 2 + 1 / 2 ) = 0 {displaystyle P_{1}(x_{2}+1/2)=0} , которое можно преобразовать в P 2 ( x 2 ) = 4 x 2 2 + 8 x 2 − 1 = 0 {displaystyle P_{2}(x_{2})=4x_{2}^{2}+8x_{2}-1=0} .
  • Поскольку P 2 ( x ) < 0 {displaystyle P_{2}(x)<0} для x = 1 / 9 {displaystyle x=1/9} и P 2 ( x ) > 0 {displaystyle P_{2}(x)>0} для всех x > 1 / 8 {displaystyle x>1/8} , следующим членом разложения будет 1 / 9 {displaystyle 1/9} . Если x 3 {displaystyle x_{3}} — остаток после этого шага жадного разложения, он удовлетворяет уравнению P 2 ( x 3 + 1 / 9 ) = 0 {displaystyle P_{2}(x_{3}+1/9)=0} , которое можно преобразовать в уравнение с целыми коэффициентами P 3 ( x 3 ) = 324 x 3 2 + 720 x 3 − 5 = 0 {displaystyle P_{3}(x_{3})=324x_{3}^{2}+720x_{3}-5=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} существует разложение в египетскую дробь, в которой все знаменатели нечётны, но приведёт ли нечётный жадный алгоритм всегда к конечному разложению — неизвестно.


  • Дважды стохастическая матрица
  • Число Коксетера
  • Особенности ремонта средств измерений
  • Сельские труженики Карачаево-Черкессии будут получать кредиты на льготных условиях
  • Омское сельскохозяйственное ведомство будет помогать местным переработчикам выходить на прилавки крупнейших торговых сетей

  •  

    • Яндекс.Метрика
    • Индекс цитирования