こんばんは、すずしんです。
今日は、Kotlinのプログラミングをしてみました。
今回作成したプログラムは、ユークリッドの互除法で最大公約数(GCD)を求めるというものです。
Kotlinのプログラミングは、なかなか楽しいです。
最大公約数(GCD)とは？
最大公約数というのは、共通する約数の中で一番大きな数のことを言います。
最大公約数は、英語で「Greatest Common Divisor」と言います。
略してGCDですね！
最大公約数の例を挙げてみます。
例えば、16と24の最大公約数の基本的な求め方では以下のように行います。
16の約数: 1, 2, 4, 8, 16 24の約数: 1, 2, 3, 4, 6, 8, 12, 24 16と24の最大公約数: 8
ユークリッドの互除法とは？
ユークリッドの互除法と言うのは、2つの自然数の最大公約数を求めるアルゴリズムの1つです。
2つの自然数a,b(a ≧ b)において、aのbによる剰余をrとした時、aとbの最大公約数はbとrとの最大公約数に等しいという性質が成り立ちます。
この性質を利用して、bをrで割った剰余、除数rをその剰余で割った剰余、と剰余を求める計算を繰り返し、剰余が0になった時の除数がaとbとの最大公約数となります。
最大公約数を求める関数をgcd(a, b)として、先ほどの例であげた16と24の最大公約数を求める例を見てみます。
gcd(24, 16) = gcd(16, 8) = gcd(8, 0) = 8
いかがでしょうか？
かなりシンプルに最大公約数を求めることができますよね。
Kotlinで最大公約数(GCD)を求めるプログラム
それでは本題です。
以上の事を踏まえて、Kotlinで2つの数a,bの最大公約数(GCD)を求めるプログラムを作成してみました。
それが以下のプログラムです。
import java.util.* fun main(args: Array<String>) { val scanner = Scanner(System.`in`) val a = scanner.nextInt() val b = scanner.nextInt() scanner.close() println(String.format("gcd(%d, %d) = %d%n", a, b, gcd(a, b))) } fun gcd(a: Int, b: Int): Int { if(a < b) return gcd(b, a) if(b == 0) return a return gcd(b, a % b) }
main関数では、まずScannerを用意して標準入力を受け付けるようにします。
そして、nextInt()を使って2つの数字を取得します。
最後に、それらの最大公約数をgcd()で求めて結果を出力しています。
gcd関数では、最初のif文でaとbの大きさの比較をしています。
その後、剰余bが0になっていたら、最大公約数はaなのでaの値を返します。
そうでなければ、剰余r = a % bとして、gcd(b, r)を計算します。
再起呼び出しなので、bが0になるまで繰り返し計算されます。
プログラム自体は、どちらも非常にシンプルですよね。
プログラムの実行結果
上記プログラムを実行した結果の例は以下の通りです。
ここでも、16と24の最大公約数を求めてみました。
確かに、最大公約数が8となっていて、正しい値になっていることが分かりますね。
16 24 gcd(16, 24) = 8
ひとこと
今回の記事では、Kotlinでユークリッドの互除法を使った最大公約数(GCD)を求めるプログラムを作成しました。
ユークリッドの互除法のアルゴリズムが理解できれば、実装は非常に簡単ですね。
比較的サクッとプログラムを書くことができました。
こうしたプログラムを書くことは、プログラミングにおいて良い練習になると思います。
あなたも得意なプログラミング言語で、最大公約数(GCD)を求めてみてはいかがでしょうか？