Shadow Academy トップ > 我流・物理数学 > ユークリッドの互除法


ユークリッドの互除法

割られる数、或いは、分子(numerator)をm
割る数、或いは、分母(denominator)をn
(m, n∈ℕ)としたとき、ユークリッドの互除法を用いて、
最大公約数(greatest common divisor)を求めるスクリプト。
m < nのときでも、m > nのときでも動作する。
但し、mnが1以外に公約数を持たないときは、
mnは互いに素である旨のメッセージも出力する。

副産物として、分数m / nを約分して既約分数にしたり、
両者の積を最大公約数で割ることによって、
最小公倍数(least common multiple)を計算したり、
分数の連分数展開は、ユークリッドの互除法に対応していることから、
分数m / n連分数展開を導出することも可能である。




割られる数(分子):m
割る数(分母):n
最大公約数:G.C.D.=
既約分数の分子:m/gcd
既約分数の分母:n/gcd
最小公倍数:L.C.M.=
連分数展開:m/n
【参考】小数表示:m/n



ソースコード

euclid.html

<form><!-- getElementByIdを使用する為、name属性を指定しない -->
<table border="1" style="margin-left:auto;margin-right:auto;text-align:center;">
  <tr>
    <td style="text-align:right;">割られる数(分子):<i>m</i>=</td>
    <td style="text-align:left;"><input type="text" id="m"></td>
  </tr>
  <tr>
    <td style="text-align:right;">割る数(分母):<i>n</i>=</td>
    <td style="text-align:left;"><input type="text" id="n"></td>
  </tr>
  <tr>
    <td colspan="2" style="text-align:center;"><input type="button" value="計算する" onClick="euclid()"></td>
  </tr>
  <tr>
    <td style="text-align:right;">最大公約数:G.C.D.=</td>
    <td style="text-align:left;"><input type="text" id="gcd"></td>
  </tr>
  <tr>
    <td style="text-align:right;">既約分数の分子:<i>m</i>/<i>gcd</i>=</td>
    <td style="text-align:left;"><input type="text" id="numerator"></td>
  </tr>
  <tr>
    <td style="text-align:right;">既約分数の分母:<i>n</i>/<i>gcd</i>=</td>
    <td style="text-align:left;"><input type="text" id="denominator"></td>
  </tr>
  <tr>
    <td style="text-align:right;">最小公倍数:L.C.M.=</td>
    <td style="text-align:left;"><input type="text" id="lcm"></td>
  </tr>
  <tr>
    <td style="text-align:right;">連分数展開:<i>m</i>/<i>n</i>=</td>
    <td style="text-align:left;"><input type="text" id="continuedfraction"></td>
  </tr>
  <tr>
    <td style="text-align:right;">【参考】小数表示:<i>m</i>/<i>n</i>=</td>
    <td style="text-align:left;"><input type="text" id="mdivn"></td>
  </tr>
</table>
</form>

euclid.js

var euclid = function(){
  var m = parseInt(document.getElementById("m").value); // 
  var n = parseInt(document.getElementById("n").value); // 
  var q, r; // 商と余り

  var cf = ""; // データを表す変数を空の初期値と共に宣言
  var temp_m, temp_n, gcd, lcm;

  if(isNaN(m)==true){ // 分子mの値が半角の数値ではない場合に
    alert("半角の数値を入力して下さい"); // アラートを表示して
    return false; // 処理を中断する
  } else if(m<=0){ // 分子mの値が自然数ではない場合に
    alert("数値は、自然数を入力して下さい"); // アラートを表示して
    return false; // 処理を中断する
  } else {
    temp_m = m; // 割られる数(分子)の値を記憶し保存しておく
  }

  if(isNaN(n)==true){ // 分母nの値が半角の数値ではない場合に
    alert("半角の数値を入力して下さい"); // アラートを表示して
    return false; // 処理を中断する
  } else if(n<=0){ // 分母nの値が自然数ではない場合に
    alert("数値は、自然数を入力して下さい"); // アラートを表示して
    return false; // 処理を中断する
  } else {
    temp_n = n; // 割る数(分母)の値を記憶し保存しておく
  }

  q = parseInt(m / n); // 商
  r = m - n * q; // 余り

  cf = q;

  if(r > 0){
    cf += "; "; // 連分数展開の整数部分をセミコロンで区切る
  }

  while(r > 0){
    m = n; // mにnを代入
    n = r; // mにnを代入

    q = parseInt(m / n); // 商
    r = m - n * q; // 余り

    cf += q;

    if(r > 0){
      cf += ", "; // 連分数展開が継続する場合はコンマで区切る
    }
  }

  gcd = n; // 最大公約数の値を記憶し保存しておく

  document.getElementById("gcd").value = gcd;
  // 最大公約数の値をテキストエリアへ出力する

  if(n == 1){
    document.getElementById("gcd").value += " (mとnは互いに素である。)";
  } // mとnが1以外に公約数を持たないときは、mとnは互いに素である旨のメッセージも出力

  document.getElementById("numerator").value = temp_m / gcd;
  // 既約分数の分子をテキストエリアへ出力する
  document.getElementById("denominator").value = temp_n / gcd;
  // 既約分数の分母をテキストエリアへ出力する
  document.getElementById("lcm").value = temp_m * temp_n / gcd;
  // 最小公倍数の値をテキストエリアへ出力する
  document.getElementById("continuedfraction").value = cf;
  // 連分数展開の結果をテキストエリアへ出力する
  document.getElementById("mdivn").value = temp_m / temp_n;
  // 【参考】小数表示の結果をテキストエリアへ出力する
};



Shadow Academy トップへ戻る

inserted by FC2 system