#Javaで学ぶアルゴリズム < ユークリッドの互除法 >
はじめに
Javaは授業で触れただけで全くの初心者であり，何もわかっていない．なので，基本的なアルゴリズムをJavaで実装し，アルゴリズムの理解を深めるとともに，Javaにも慣れていきたい．
その第6弾としてユークリッドの互除法を扱う．
ユークリッドの互除法
Pythonでもユークリッドの互除法を扱った．(https://qiita.com/Yuya-Shimizu/items/d82bbdf15d31e25cf544 )
そのときにも示したようにユークリッドの互除法は１つではない．
ここで，2つ定理とそれを利用したときの互除法の手順を示す．
定理①：余りを利用
「2つの自然数m, nについて，mをnで割ったときの商をq，あまりをkとすると，「mとnの最大公約数」は「nとkの最大公約数」に等しい．」
【step1】: mをnで割り，あまりkを求める
【step2】: m, nをn, kでそれぞれ置き換える
【step3】: あまりkが0なら，その時の割る数nが最大公約数で，そうでなければstep1へ戻る
定理②：差を利用
「2つの整数m, n (m>n)があったとき，mとnの最大公約数はm-nとnの最大公約数に置き換えることができる．」
【step1】: m > n ⇒ m = m - n , m < n ⇒ n = n - m
【step2】: mとnが等しくなければstep1へ戻る
【step3】: mとnが等しくなった時m(nでもよい)が求める最大公約数となる
実装
先ほどの説明に従い，Javaでの実装を行う．以下にそれぞれの方法についてソースコードとそのときの出力を示す．
ソースコード①：余りの利用
//2020/12/16
//@Yuya Shimizu
//-------------------------------------------
//* ユークリッドの互除法（余りの利用） *
//-------------------------------------------
import java.awt.*;
import java.awt.event.*;
//フレームの設定
class Euclid_Frame1 extends Frame{
private TextField tf1, tf2, tf3; //入力2つと出力1つに対してテキストフィールドを準備
public Euclid_Frame1(){
setSize(300, 100);//300×100の大きさでフレームを作成
//×ボタンを押したら終了
addWindowListener(new WindowAdapter(){
public void windowClosing(WindowEvent e){
System.exit(0);
}
});
Button bt;
//ボタンとテキストフィールドの配置
setLayout(new FlowLayout());
add(new Label("二つの整数"));
add(tf1=new TextField("", 6));
add(tf2=new TextField("", 6));
add(bt=new Button("最大公約数"));
add(tf3=new TextField("", 10));
//ボタン設定
bt.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e){
int m, n, k;
m = Integer.parseInt(tf1.getText()); //テキストフィールドに入力されたものを取得し整数として格納
n = Integer.parseInt(tf2.getText()); //テキストフィールドに入力されたものを取得し整数として格納
//以下，アルゴリズム
do{
k = m%n;
m = n;
n = k;
}while (k!=0);
tf3.setText("最大公約数 = " + m); //結果をテキストフィールドにセット
}
});
}
}
//クラス
public class Euclidean_algorithm1{
//メイン関数
public static void main(String[] args){
Frame w=new Euclid_Frame1();
w.show();
}
}
出力
計算前
計算後
ソースコード②：差の利用
//2020/12/16
//@Yuya Shimizu
//-------------------------------------------
//* ユークリッドの互除法（差を利用） *
//-------------------------------------------
import java.awt.*;
import java.awt.event.*;
//フレームの設定
class Euclid_Frame2 extends Frame{
private TextField tf1, tf2, tf3; //入力2つと出力1つに対してテキストフィールドを準備
public Euclid_Frame2(){
setSize(300, 100);//300×100の大きさでフレームを作成
//×ボタンを押したら終了
addWindowListener(new WindowAdapter(){
public void windowClosing(WindowEvent e){
System.exit(0);
}
});
Button bt;
//ボタンとテキストフィールドの配置
setLayout(new FlowLayout());
add(new Label("二つの整数"));
add(tf1=new TextField("", 6));
add(tf2=new TextField("", 6));
add(bt=new Button("最大公約数"));
add(tf3=new TextField("", 10));
//ボタン設定
bt.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e){
int m, n;
m = Integer.parseInt(tf1.getText()); //テキストフィールドに入力されたものを取得し整数として格納
n = Integer.parseInt(tf2.getText()); //テキストフィールドに入力されたものを取得し整数として格納
//以下，アルゴリズム
while (m!=n){
if (m > n)
m -= n;
else
n -= m;
}
tf3.setText("最大公約数 = " + m); //結果をテキストフィールドにセット
}
});
}
}
//クラス
public class Euclidean_algorithm2{
//メイン関数
public static void main(String[] args){
Frame w=new Euclid_Frame2();
w.show();
}
}
出力
計算前
計算後
感想
ユークリッドの互除法は高校でも学習し，Pythonでも学習したため，アルゴリズム自体は理解している．改めて確認しておくことは，次のことだと思う．「2つの整数の差が大きいときは差よりも余りを利用した方が効率が良い」また，簡単なアプリケーションの作成も何となく理解してきたような気がする．
参考文献
Javaによるはじめてのアルゴリズム入門 河西 朝雄 著 技術評論社