SCALAの記事一覧

Top / scala 99problem 32～

目次 †

↑

練習問題 S-99 Ninety Nine Scala Problems † †

S-99 Ninety Nine Scala Problems http://aperiodic.net/phil/scala/s-99/

↑

問32 †

ユークリッドのアルゴリズムを使っているそうだ。

↑

ユークリッドのアルゴリズムってなんだっけ †

↑

(例題) 1071 と 1029 の最大公約数を求める。 †

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)

だからね。

でも、これって、どういうときつかうんだろ。

「あー今日は、最大公約数でも求めたいなぁ」っていうときかな？

そんなことってないよね。

トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS