強欲算法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/02 23:28 UTC 版)
以上のいずれの方法の通用しない場合に対して、フィボナッチは強欲算法(greedy algorithm) と呼ばれる方法を提案した。単位分数の和に展開しようとする分数に対して、それ以下の最大の単位分数を取る。それを引いた残りに対しても、繰り返し最大の単位分数を取る。式で書けば、分数 x/y を x y = 1 ⌈ y / x ⌉ + x − ( y mod x ) y ⌈ y / x ⌉ {\displaystyle {\frac {x}{y}}={\frac {1}{\lceil y/x\rceil }}+{\frac {x-(y\,{\bmod {\,}}x)}{y\lceil y/x\rceil }}} と、次々に置き換える方法である。ここに、括弧は天井関数である。例えば、4/13 に強欲算法を適用すると、 4/13 = 1/4 + 1/18 + 1/468 となる。 フィボナッチは、強欲算法の手続きが有限回で終了することの証明を与えてはいない。後にシルベスターはこの方法を再発見し、有限回で終了することの証明も与え、1880年に発表した。実際、一度の手続きで分子は少なくとも 1 小さくなるので、a/b は多くとも a 個の単位分数の和で表せる。2人の名を取って、強欲算法は「フィボナッチ＝シルベスターのアルゴリズム」とも呼ばれる。 フィボナッチ自身も注意したように、強欲算法はときに複雑な単位分数展開を与える。例えば、5/121 に強欲算法を適用すると、 5/121 = 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225 となるが、ずっと簡潔な単位分数展開 5/121 = 1/33 + 1/121 + 1/363 を持つ。強欲算法は単純で分かりやすく、任意の分数が異なる単位分数の和で表せることの易しい証明も与えるが、このように複雑な展開になる場合もあるため、フィボナッチ自身は、最初の分解の後は他の方法を適用することを勧めている。 単位分数 1/n に強欲算法を適用すると、恒等式 1/n = 1/n + 1 + 1/n(n + 1) を得る。これより、単位分数は2つの単位分数の和に表せるので、任意の分数は無数に多くの単位分数展開を持つ。
※この「強欲算法」の解説は、「エジプト式分数」の解説の一部です。
「強欲算法」を含む「エジプト式分数」の記事については、「エジプト式分数」の概要を参照ください。
- 強欲算法のページへのリンク
