JavaScriptで有理数を「分子が1の分数」の和に分解するアルゴリズム

問題概要

今回は、JavaScriptで有理数を「分子がすべて1である分数」の和に分解する関数を作成する課題です。

入力には、有理数を表す文字列（例：'2/3'）を使用します。このような分解はエジプト分数と呼ばれ、古代エジプトで実際に使われていた記法に由来する有名な数学的テーマです。

関数が満たすべき条件は以下の通りです。

• 返り値は、各要素が「1/分母」の形式を持つ部分配列からなる配列であること
• 部分配列が表す分数をすべて加算すると、入力された有理数と一致すること
• 使用する分数の個数はできるだけ少なくすること

解き方：貪欲法（グリーディーアルゴリズム）

この種の問題に対する標準的なアプローチは貪欲法です。手順はシンプルです。

1. 残りの値を超えない範囲で、最も大きい単位分数（1/n）を選ぶ
2. 選んだ分数を現在の合計に加算する
3. 合計が目標の値にほぼ一致するまで、分母を増やしながら繰り返す

なお、浮動小数点数の計算には微小な誤差が生じるため、ループ終了判定では小さな許容誤差（ここでは 0.000000001）を使って比較しています。

コード例

const num = '2/3';

const decompose = (num = '') => {
  // 文字列を分子と分母に分割して数値化
  const [numerator, denominator] = num.split('/').map(Number);
  let res = numerator / denominator;

  const fractions = [];

  // 整数部分がある場合は先に取り出す
  if (res >= 1) {
    fractions.push(String(Math.floor(res)));
    res -= Math.floor(res);
  }

  let sum = 0;
  let denom = 2;

  // 誤差を考慮しつつ、残りがほぼ0になるまで探索
  while (sum <= res - 0.000000001) {
    if (sum + 1 / denom <= res) {
      fractions.push(`1/${denom}`);
      sum += 1 / denom;
    }
    denom++;
  }

  return fractions;
};

console.log(decompose(num));

出力結果

[ '1/2', '1/6' ]

処理の流れを解説

入力が '2/3' の場合、処理は以下のように進みます。

1. まず 1/2 を試します。1/2 ≤ 2/3 なので採用し、残りは 2/3 − 1/2 = 1/6 となります。
2. 次に 1/3 を試しますが、合計が 1/2 + 1/3 = 5/6 となり 2/3 を超えるため不採用です。
3. 同じ理由で 1/4、1/5 も不採用です。
4. 1/6 を加えると合計がちょうど 2/3 になるため採用されます。

その結果、['1/2', '1/6'] という最小の分解が得られます。

この貪欲法は常に有限回のステップで収束することが知られており、単位分数への分解を求める際に非常に有用な手法です。ぜひ自分のコードにも応用してみてください。