■数のフィボナッチ数分割(その25)

 反復アルゴリズムにおいて,各ステップごとに最大化を試みるものを欲張り算法(greedy algorithm)と呼びます.欲張り算法はあるときは最も賢明な方法ですが,ときとして破綻します.今回のコラムでは成功のケースを紹介します.

===================================

【1】アルゴリズムは破綻しない・・・「エジプト式単位分数」

 分子が1である分数を単位分数と呼びます.古代エジプト人は分数を表すのに,互いに異なる単位分数の和として表しました.たとえば,5/7は

  5/7=1/7+1/7+1/7+1/7+1/7

ではなく,互いに異なる単位分数の和ですから,3つの単位分数を用いて

  5/7=1/2+1/5/1/70

と書くことができます.

 どんな分数でも相異なる単位分数の和として表現できることは,簡単に証明できます.それでは

 (1)分数p/qを越えない最大の単位分数を求め,p/qから差し引き,それをp1/q1とする

 (2)分数p1/q1を越えない最大の単位分数を求め,p1/q1から差し引き,それをp2/q2とする

 (3)分数pi/qiを越えない最大の単位分数を求め,pi/qiから差し引き,それをpi+1/qi+1とする

という手順を繰り返せば,つねに単位分数表示が得られるでしょうか?

 答えはyesで,このアルゴリズムは破綻しないことが知られています.もちろん,その表示の仕方はただ1通りです.

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

 単位分数の和としての表現は少なくとも1つは存在するのですが,しかし,単位分数表示は1通りとは限らず,たとえば,前述の5/7は

  5/7=1/2+1/7+1/14

  5/7=1/3+1/4+1/8+1/168

のように何通りも表し方があります.

 2/(2n−1)という形の分数の相異なる単位分数の和による表現では,欲張り算法により

  2/(2n−1)=1/n+1/n(2n−1)

のように2個の単位分数を用いて表示できます.

  2/3=1/2+1/6

  2/5=1/3+1/15

  2/7=1/4+1/28

  2/11=1/6+1/66

  2/23=1/12+1/276

はこの式に従っていますが,

  2/9=1/6+1/18

  2/13=1/8+1/52+1/104

  2/15=1/10+1/30

  2/17=1/12+1/51+1/68

  2/19=1/12+1/76+1/114

  2/21=1/14+1/42

は欲張り算法によるものではありません.

===================================