目次
Kotlin でユークリッドの互除法を書いてみました。
ユークリッドの互除法
2つの自然数の最大公約数を求める方法のひとつ。 ユークリッドの原論に記述があります。
Example
46 と 36 の最大公約数をユークリッドの互除法で求めてみます。
\begin{eqnarray} 46 & = & 36 \times 1 + 10 \\ 36 & = & 10 \times 3 + 6 \\ 10 & = & 6 \times 1 + 4 \\ 6 & = & 4 \times 1 + 2 \\ 4 & = & 2 \times 2 \end{eqnarray}これより最大公約数は 2 となります。
環境
- Kotlin 1.0.0
コード
ユークリッドの互除法は2つの整数についてのものが基本ですが、ここでは複数の整数の最大公約数を計算できるようにしました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
import java.util.* open class MainKt { companion object Static { @JvmStatic fun main(args: Array<String> = arrayOf()) { println( MainKt().solve( args.toList<String>(). map { it.toLong() } as MutableList<Long>)) } } fun solve(numList: MutableList<Long>): Long { var newList = numList.distinct().sorted() as MutableList var r: Long = 0 while (newList.count() > 1) { r = newList[0] newList = newList. takeLast(newList.count() - 1).map { it % newList[0]} as MutableList newList.add(r) newList = newList.distinct().sorted(). filter { it != 0L } as MutableList<Long> } return r } } |
main関数は solve を呼び出します。 計算をやっているのは solve です。
solveに最大公約数を求めたい自然数のリストを渡して、 solveが最大公約数を返します。 main はその値を標準出力に出力しています。
最大公約数がない場合(共通因数がない場合)は1を返します。
きっともっと効率のいいやり方があると思います。
使い方
jar を作って実行する場合は、 次のようにします。
例
|
1 2 |
java -jar Jar.jar 82 48 36 72 # => 2 |
活用
最大公約数が求められますから、分数の約分をすることができます。
クラスの分け方はきれいではないですが、 例えば次のように 分数のクラス Fraction を作ります。 初期化処理のところで分母と分子を最大公約数で割って既約分数にしています。 もし 分母(numerator) が 1 になれば整数です。
|
1 2 3 4 5 6 7 8 9 |
data class Fraction( var denominator: Long, var numerator: Long) { init { var r = MainKt().solve( mutableListOf(denominator, numerator)) denominator /= r numerator /= r } } |
