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

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

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

　分子が１である分数を単位分数と呼びます．古代エジプト人は分数を表すのに，互いに異なる単位分数の和として表しました．たとえば，５／７は

　　５／７＝１／７＋１／７＋１／７＋１／７＋１／７

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

　　５／７＝１／２＋１／５／１／７０

と書くことができます．

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

　(1)分数ｐ／ｑを越えない最大の単位分数を求め，ｐ／ｑから差し引き，それをｐ1／ｑ1とする

　(2)分数ｐ1／ｑ1を越えない最大の単位分数を求め，ｐ1／ｑ1から差し引き，それをｐ2／ｑ2とする

　(3)分数ｐi／ｑiを越えない最大の単位分数を求め，ｐi／ｑiから差し引き，それをｐi+1／ｑi+1とする

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

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

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

　単位分数の和としての表現は少なくとも１つは存在するのですが，しかし，単位分数表示は１通りとは限らず，たとえば，前述の５／７は

　　５／７＝１／２＋１／７＋１／１４

　　５／７＝１／３＋１／４＋１／８＋１／１６８

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

　２／（２ｎ−１）という形の分数の相異なる単位分数の和による表現では，欲張り算法により

　　２／（２ｎ−１）＝１／ｎ＋１／ｎ（２ｎ−１）

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

　　２／３＝１／２＋１／６

　　２／５＝１／３＋１／１５

　　２／７＝１／４＋１／２８

　　２／１１＝１／６＋１／６６

　　２／２３＝１／１２＋１／２７６

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

　　２／９＝１／６＋１／１８

　　２／１３＝１／８＋１／５２＋１／１０４

　　２／１５＝１／１０＋１／３０

　　２／１７＝１／１２＋１／５１＋１／６８

　　２／１９＝１／１２＋１／７６＋１／１１４

　　２／２１＝１／１４＋１／４２

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

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝