Top / scala 99problem 32~
S-99 Ninety Nine Scala Problems http://aperiodic.net/phil/scala/s-99/
ユークリッドのアルゴリズムを使っているそうだ。
1071 を 1029 で割った余りは 42 1029 を 42 で割った余りは 21 42 を 21 で割った余りは 0 よって、最大公約数は21である。
入力を m, n (m ≧ n) とする。 n = 0 なら、 m を出力してアルゴリズムを終了する。 n が m を割り切るなら、 n を出力してアルゴリズムを終了する。 m を n で割った余りを新たに n とし、更に 元のnを新たにm とし 3. に戻る。
回答はこんな感じだ。
object S99Int { def gcd(m: Int, n: Int): Int = if (n == 0) m else gcd(n, m % n) }
久しぶりにみたから、目が慣れていない。
GCDって英語圏の最大公約数greatest common divisorの略だからね。
サイトには、
gcd(36,63)
ってだけ書いてあるけど、実際には
S99Int.gcd(36,63)
だからね。
でも、これって、どういうときつかうんだろ。
「あー今日は、最大公約数でも求めたいなぁ」っていうときかな?
そんなことってないよね。
互いに素かどうかを返す問題だ。
これは問32をつかって解くと簡単なんだ。でも、ここの回答のチェックポイントは
クラスのコンストラクターの書き方に注目したい。
object S99Int { def gcd(m: Int, n: Int): Int = if (n == 0) m else gcd(n, m % n) } class S99Int(val start: Int) { def isCoprimeTo(n: Int): Boolean = S99Int.gcd(start, n) == 1 }
ウェブでの回答はS99Int.gcdのところが単にgcdって書いてあるだけなんだけどね。
確かめる方法はこんな具合
scala> var a = new S99Int(35); a: S99Int = S99Int@1a422d9 scala> a.isCoprimeTo(64) res3: Boolean = true
一行で書くとこんなかんじかな
scala> new S99Int(35).isCoprimeTo(64) res4: Boolean = true