6

古代エジプト人は形の分数しか使用し1/nていなかったので、他の分数はそのような単位分数の合計として表されなければならず、さらに、すべての単位分数は異なっていました！

CまたはJavaで任意の分数をエジプト式分数（合計が少ないほど良い）にするための良い方法は何ですか？どのアルゴリズムを使用できますか、分枝限定法、a *？

例えば：

3/4 = 1/2 + 1/4

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

4 に答える 4

8

1つの方法は、欲張りアルゴリズムです。分数が与えられた場合、以下fの最大のエジプト式分数を見つけます（つまり、n = ceil（1 / f））。次に、残りの部分について、まで繰り返します。1/nff - 1/nf == 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
于 2011-03-20T06:03:48.450 に答える
3

エジプト式分数から切り取った

どうやってこれらの値を思いついたのですか？さて、私は与えられた分数よりもちょうど小さい最大の単位分数を持つ分数を推定しました。与えられた分数からこの単位分数を引きました。この余りがまだ単位分数でない場合は、この余りよりも小さい最大の単位分数を選択して、プロセスを繰り返しました。そして、このプロセスは何度も繰り返される可能性があります。

例として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です。

于 2011-03-20T06:00:19.327 に答える
2

の場合a / b、MAXをa*bにします。

MAXの素因数（prime_fac（a）とprime_fac（b）の和集合、およびこれら2つのリストからそれぞれ1つずつの倍数）を取得し、それらを繰り返し、低く始めて高くします。

それらはあなたの可能な1/xです。

編集：そうそう！考慮に入れることを忘れないでください2/3！

于 2011-03-20T05:54:58.887 に答える
1

あなたは、人々が通常彼らの答えにコードを提供するウェブサイトで質問をしました。コードには他に答えはありません。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より大きい値の分数を処理し、次の出力を生成します。

1/2 + 1/4
1/2 + 1/3 + 1/42
23 + 1/2 + 1/3 + 1/92 + 1/29532
于 2016-05-03T16:28:26.163 に答える