アルゴリズムの勉強(6)

エジプトの分数

環境

$ node --version
v13.5.0
$ tsc --version
Version 3.7.4

コード

// フィボナッチの貪欲アルゴリズム(再帰)
function frac(m: number, n: number) {
  const q_plus1 = Math.floor(n / m) + 1;
  if (n % m == 0) {
    return ("1/" + n/m);
  } else {
    const m_prime = m * q_plus1 - n;
    const n_prime = n * q_plus1;
    return ("1/" + q_plus1 + ' + ' + frac(m_prime, n_prime));
  }
}

// m = 分子, n = 分母
let m = 2;
let n = 5;
console.log(m + "/" + n + " = " + frac(m, n));

実行結果

$ tsc egypfrac.ts && node egypfrac.js
2/5 = 1/3 + 1/15

所感

リンド・パピルスの話が出てきて興味をそそられる。 古代エジプト数学に関する書籍は出版されているので、いずれ読みたい。

今回のコードはアルゴリズム事典に載っているループ式ではなく再帰的な形にした。 載ってるコードをそのまま引き写すだけだと頭に残らなかったので、少し実装を工夫するようにしてみた。