Египетские фракции в C

Древние египтяне использовали только фракции формы 1/n поэтому любая другая фракция должна была быть представлена ​​в виде суммы таких единичных фракций и, кроме того, все единичные фракции были разными!

Какой хороший способ сделать какую-либо фракцию египетской фракцией (чем меньше сумм лучше) в C или java, какой алгоритм можно использовать, ветвь и связанная, a *?

например:

 3/4 = 1/2 + 1/4 6/7 = 1/2 + 1/3 + 1/42 

    Один из способов – жадный алгоритм. Учитывая долю f , найдите наибольшую египетскую фракцию 1/n меньшую или равную f (т. Е. N = ceil (1 / f)). Затем повторите для остатка f - 1/n , пока f == 0 .

    Итак, для 3/4 вы должны вычислить:

    • n = ceil (4/3) = 2 ; остаток = 3/4 – 1/2 = 1/4
    • n = ceil (4) = 4 ; остаток = 1/4 – 1/4 = 0
    • 3/4 = 1/2 + 1/4

    И для 6/7:

    • n = ceil (7/6) = 2 ; остаток = 6/7 – 1/2 = 5/14
    • n = ceil (14/5) = 3 ; остаток = 5/14 – 1/3 = 1/42
    • n = ceil (42) = 42 ; остаток = 1/42 – 1/42 = 0
    • 6/7 = 1/2 + 1/3 + 1/42

    Обрезано из египетских фракций

    Как я придумал эти ценности? Ну, я оценил фракцию с наибольшей единичной фракцией, которая была меньше этой фракции. Я вычитал эту единичную фракцию из данной фракции. Если этот остаток по-прежнему не был единицей, я повторил этот процесс, выбирая наибольшую долю единицы, которая меньше этого остатка. И этот процесс можно повторять снова и снова.

    Давайте используем 7/8 в качестве примера. Мы оцениваем 7/8 с 2/3 (наибольшая удельная доля меньше 7/8). Мы вычитаем 7/8 – 2/3, что составляет 5/24, что не может быть упрощено до единицы. Таким образом, мы оцениваем 5/24 с 1/5 (наибольшая единичная доля меньше 5/24). Вычитаем 5 / 24-1 / 5, и получим 1/120, что является единичной. Итак, 7/8 = 2/3 + 1/5 + 1/120.

    Для a / b сделайте MAX a * b.

    Возьмем основные коэффициенты MAX (который является объединением prime_fac (a) и prime_fac (b) и кратным каждым из этих двух списков) и прокручивайте их, начиная с минимума и поднимаясь высоко.

    Это ваши возможные 1 / x.

    Редактировать: О да! Не забудьте принять во внимание 2/3 !

    Вы задали вопрос на веб-сайте, где люди обычно предоставляют код в своих ответах. Нет других ответов с кодом, C и Java не являются моей специальностью, и вот здесь есть код в Python.

     #! /usr/bin/env python3 import fractions import functools import math def main(): f = fractions.Fraction(3, 4) e = to_egyptian_fractions(f) print(*e, sep=' + ') f = fractions.Fraction(6, 7) e = to_egyptian_fractions(f) print(*e, sep=' + ') f = fractions.Fraction(7654, 321) e = to_egyptian_fractions(f) print(*e, sep=' + ') def validate(function): @functools.wraps(function) def wrapper(fraction): total = fractions.Fraction(0) for egyptian in function(fraction): if 1 not in {egyptian.numerator, egyptian.denominator}: raise AssertionError('function has failed validation') yield egyptian total += egyptian if total != fraction: raise AssertionError('function has failed validation') return wrapper @validate def to_egyptian_fractions(fraction): quotient = math.floor(fraction.numerator / fraction.denominator) if quotient: egyptian = fractions.Fraction(quotient, 1) yield egyptian fraction -= egyptian while fraction: quotient = math.ceil(fraction.denominator / fraction.numerator) egyptian = fractions.Fraction(1, quotient) yield egyptian fraction -= egyptian if __name__ == '__main__': main() 

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

     1/2 + 1/4 1/2 + 1/3 + 1/42 23 + 1/2 + 1/3 + 1/92 + 1/29532