ユークリッドの互除法で最大公約数をだすコードを一生懸命書いた後で、GCD関数とLCM関数を紹介して、便利になったなぁと感謝する話

言語を問わず、プログラミングのチャレンジ問題でよくでてくる「ユークリッドの互除法」を紹介します。

「ユークリッドの互除法(ユークリッドのごじょほう)は、2 つの自然数または整式の最大公約数を求める手法の一つである。2 つの自然数(または整式) a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。」
(Wikipediaより転載)

最小公倍数についてはa*b/(aとbの最大公約数)でだせるので省略します。

これをSASで書くなら

data _NULL_;
 X=1029;
 Y=1071;
 call sortn(X,Y);
  MD=mod(Y,X);
  ANSWER=X;
 do while(MD^=0);
  MD_=MD;
  MD=mod(Y,MD);
  Y=MD_;
  ANSWER=Y;
 end;
 put '最大公約数は' ANSWER;
run;









上記の感じでしょうか?XとYの値を色々変えてみてください。
call sortnルーチンで横ソートしているので、大小関係を気にせず指定できます。

要は余りが0になるまで、割ってけばいいんですね。
でも実際、アルゴリズムはわかっていても、コードにおこすのは、結構大変ですよね。


ところが9.2からgcd関数で最大公約数をl㎝関数で最小公倍数を簡単にだせるようになりました。
複数変数指定も可能で、もう二度とデータステップでループ書く必要がなくなりました。

data _NULL_;
ANSWER1=gcd(1029,1071,63);
ANSWER2=lcm(8,3,5);
 put '最大公約数は' ANSWER1;
 put '最小公倍数は' ANSWER2;
run;








0 件のコメント:

コメントを投稿