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

Question

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

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

:

3/4 = 1/2 + 1/4

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

Answer 1

Одним из способов является жадный алгоритм. Учитывая долю 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

Answer 2

Вырезано из Египетские фракции

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

Давайте использовать 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.

Answer 3

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

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

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

Редактировать: О да!Не забудьте учесть 2/3!

Answer 4

Вы задали вопрос на веб-сайте, где люди обычно предоставляют код в своих ответах. Других ответов с кодом нет, 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