Жадный алгоритм для египетских дробей — жадный алгоритм, который преобразует рациональные числа в египетские дроби, на каждом шаге выбирая наибольшую из возможных аликвотных дробей, которая может быть использована в остаточной дроби.
Разложение, полученное жадным алгоритмом для числа , называется жадным египетским разложением, разложением Сильвестра или разложением Фибоначчи — Сильвестра числа .
История Среди нескольких различных методов построения египетских дробей, приведённых Фибоначчи в «Книге абака», был жадный алгоритм, который предлагался к применению, лишь если прочие методы не сработали, chapter II.7. Впоследствии жадный алгоритм и его расширения для приближения иррациональных чисел был переоткрыт несколько раз, наиболее ранний и известный случай — алгоритм Сильвестра. Метод, дающий ближайшее приближение на каждом шаге, для чего разрешаются отрицательные дроби, принадлежит Ламберту.
Алгоритм и примеры Алгоритм Фибоначчи осуществляет разложение путём последовательного проведения замены:
(упрощая второй член, если необходимо). Например: . В этом разложении знаменатель первой аликвотной дроби является результатом округления до следующего (большего) целого числа, а остаток — результат сокращения . Делитель второй дроби — , — является результатом округления до следующего (большего) целого числа, а остаток — это то, что осталось от после вычитания и .
Поскольку каждый шаг разложения уменьшает числитель остаточной дроби, этот метод завершится за конечное число шагов. Однако, по сравнению с древними египетскими методами разложения или более современными методами, этот метод может дать разложение с довольно большими знаменателями. Например, жадное разложение числа : , в то время как другие методы дают куда более простое разложение: , а для жадный алгоритм даёт разложение на десять дробей, последняя из которых имеет в знаменателе 500 знаков, тогда как существует представление: .
Последовательность Сильвестра Последовательность Сильвестра можно представить как образованную бесконечным разложением единицы посредством жадного алгоритма, где на каждом шаге выбирается знаменатель вместо . Если оборвать эту последовательность членами и образовать соответствующую египетскую дробь, например, для : , то получается ближайшее приближение к снизу среди египетских дробей с членами. Например, для любой египетской дроби для числа в открытом интервале требуется по меньшей мере пять членов. Описано применение таких ближайших разложений для нижней оценки числа делителей совершенного числа, а также в теории групп.
Разложения максимальной длины и условия сравнения по модулю Любая дробь даёт максимум членов в жадном алгоритме. Исследованы условия, при которых для разложения необходимо в точности дробей, эти условия можно описать в терминах сравнений по модулю: любая дробь приводит к одному члену в разложении, самая простая такая дробь — ; любая дробь вида для нечётных требует двух членов в разложении, самая простая такая дробь — ; в разложении дроби необходимы три члена в том и только в том случае, когда , в этом случае — и нечётно, так что остаток разложения после первого шага:
несократим, самая простая дробь вида , дающая разложение с тремя членами — ; разложение дроби даёт четыре члена тогда и только тогда, когда или . В этих случаях числитель — остаточной дроби равен и знаменатель сравним с . Самая простая дробь вида с четырьмя членами разложения — , гипотеза Эрдёша — Штрауса утверждает, что все дроби вида имеют разложение с тремя или меньше членами, но при или такие разложения следует искать методами, отличными от жадного алгоритма.
В общем случае последовательность дробей с минимальным знаменателем , имеющих разложение жадным алгоритмом с членами: .
Приближённое вычисление корней многочленов Существует метод приближённого вычисления корней многочлена, основанный на жадном алгоритме, определяющем жадное разложение корня. На каждом шаге образуется дополнительный многочлен, который имеет остаток разложения в качестве корня. Например, для вычисления жадного разложения золотого сечения как одного из двух решений уравнения алгоритм осуществляет следующие шаги. Поскольку для и для всех , корень должен находиться между и . Таким образом, первый член разложения — . Если — остаток после первого шага жадного разложения, должно выполняться уравнение , которое можно преобразовать в . Поскольку для и для всех , корень лежит между и , первый член в разложении (второй член в разложении золотого сечения) равен . Если — остаток после этого шага жадного разложения, он удовлетворяет уравнению , которое можно преобразовать в . Поскольку для и для всех , следующим членом разложения будет . Если — остаток после этого шага жадного разложения, он удовлетворяет уравнению , которое можно преобразовать в уравнение с целыми коэффициентами .
Продолжая этот процесс приближения, получается разложение золотого сечения в египетскую дробь: .
Другие целочисленные последовательности Длина, минимальный знаменатель и максимальный знаменатель жадного разложения для дробей с малыми числителями и знаменателями включены в Энциклопедии целочисленных последовательностей, , . Кроме того, жадное разложение любого иррационального числа приводит к бесконечной возрастающей последовательности целых, и OEIS содержит разложения некоторых хорошо известных констант.
Связанные разложения Возможно определить жадный алгоритм с некоторыми ограничениями на знаменатель: , где выбирается среди всех значений, которые удовлетворяют наложенным ограничениям и имеют как можно меньшее значение, при котором и такое, что отличается от всех предыдущих знаменателей. Например, разложение Энгеля можно рассматривать как алгоритм этого типа, в котором каждый допустимый знаменатель должен быть получен умножением предыдущего на некоторое целое число. Однако зачастую нетривиально установить, приводит ли такой алгоритм всегда к конечному разложению. В частности нечётное жадное разложение дроби образуется жадным алгоритмом с ограничением на нечётность знаменателей. Известно, что при нечётном существует разложение в египетскую дробь, в которой все знаменатели нечётны, но приведёт ли нечётный жадный алгоритм всегда к конечному разложению — неизвестно.
Примечания
Литература
Категория:Теория чисел Категория:Целочисленные последовательности