2013年1月14日
小学校高学年で分数を習うけれど、分子、分母の桁が大きいとき、「約分」の方法って悩まなかった? 爺は直感的に分子、分母を同じ数で割って、それなりに小さい数になれば、それでよし!としていた。でも、例えば「239/929を約分せよ!」とゆー問題だったらどうだろう。下一桁が9なので、直感的に約分可能なのは、3か9、あるいは(7×7=49)なので、7も考えられる。この問題は意地悪で分子も分母も素数なので、これ以上約分できない。でも、どーやったら、これ以上約分できないと言えるの? それが2つの値の最大公約数を求めるとゆーことなのら。
ふたつの数の最大公約数(Greatest Common Divisor)を求めるには、「ユークリッドの互除法」という超有名な方法(アルゴリズム)がある。その方法とは、例えば、gcd(123,45)の場合、123を45で割ってその余りを求める。もし、余りが「0」ならば、45が最大公約数なのだが、「123%45」は「33」だ。次は「除数%剰余」として、つまり「gcd(45,33)」として、「45%33」を実行。余りが「12」なので→「33%12=9」→「12%9=3」→「9%3=0」、余りが「0」になったので、除数「3」が123と45の最大公約数となる。gcd関数の中でgcd関数を呼び出していることに注目。これを「再帰的呼び出し」、あるいは「再帰関数」と言う。最小公倍数(Least Common Multiple)の求め方は、ふたつの数を掛け合わせ、それを最大公約数で割ればよい。
<script> function myCalc(select){ var m = document.myFORM.myValue1.value; var n = document.myFORM.myValue2.value; if(isNaN(m)||isNaN(n)){ alert("数値ではありません!"); }else{ switch(select){ case 0: ans1 = gcd(m,n); document.getElementById("result1").value = ans1; break; case 1: ans2 = lcm(m,n); document.getElementById("result2").value = ans2; break; } } function gcd(m,n){ var r = m % n; if (r == 0) return n; return gcd(n, r); } function lcm(m,n){ var r = Math.abs(m*n)/gcd(m,n); return r; } } </script>
<form name="myFORM"> 値(1)<input type="text" size="8" name="myValue1" value="123"> <input type="button" value=" 最大公約数 " onclick="myCalc(0)"> <input type="text" size="8" id="result1" value="0"><br /> 値(2)<input type="text" size="8" name="myValue2" value="45"> <input type="button" value=" 最小公倍数 " onclick="myCalc(1)"> <input type="text" size="8" id="result2" value="0"> </form>
※参考:「C言語によるアルゴリズム事典」(奥村晴彦/著)
※爺註:「m % n」とする際、「m > n」になっていることが前提条件なのだが、例えば、gcd(45,123)を実行すると、「45%123=45」となり、次に再帰呼び出しをする際には、「gcd(除数,剰余)」なので、ちゃんと「gcd(123,45)」になっちゃうところが、アルゴリズム的には、おもしろい。ってゆーか、先人たちの考えたアルゴリズムは完璧なまでに洗練されていて、「うまいことできてるなぁ!」と爺は感心するばかり^^;