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)

だからね。

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

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

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

↑

問33 †

互いに素かどうかを返す問題だ。

どうでもいいんだけど、互いに素っていう表現は３つあるって知ってた？

relatively prime/disjoint/coprime

primeは素って出てくれば、よさそうなんだけど。覚えにくい。プライムってサブプライムローンのプライムなのかな？

しらべてみたら、サブプライムローンのプライムであってるじゃん。

primeのpriは、「主要な」っていう意味。じゃあmeは？自分？主要な自分だっていっていると、互いに素になっちゃうね。っておぼえときゃいいのかな？

話を戻して、これは問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
↑

問34 †

オイラーのファイ関数

totientって、英次郎でしらべたら、

《数学》その数以下｛すう いか｝でその数と互いに素な数の個数

で、それ以外の意味ってないんだね。これって、絶対に日常使わないから、英語圏の人でも、数学詳しくない人て、普通だとおもうから、きっとみんなしらないだろうね。

「toti」って全体のっていう意味でよく使われているらしいね。Javaやっていると、このような単純んな名前付けは、名前空間で重複するからだめだとか、ほかの人が読んでも意味を連想しにくいとかで、とかく誤解がなければすべてよし、みたいな感じで、ながったらしい名前をかくんだよね。

まあ、オイラーさんに文句はいえないわけだけど。

↑

問35 †

最大公約数を求める問題なんだけど、回答しているプログラムがうまく通らなかった。

primesが定義されていないからだ。

回答されているプログラムをみる限りprimesにはStream形の配列に素数リストを定義したものを代入すれば、動くようなつくりになっている。

だから、どうっていうことでもないんだけどね。

↑

Stream †

Streamは要素が必要になったときに作成されるList(みたいなモノ)です。

要素は必要になったときに初めて作成されるので、

↑

問36 †

模範解答例には２つの解き方が書いてあるが、あえて難しいほうの回答を読解してみる。

def factorCount(n: Int, p: Int): (Int,Int) = 
     if (n % p != 0) (0, n)
     else factorCount(n / p, p) match { case (c, d) => (c + 1, d) }

else と match　の組み合わせがどのように計算されるのか、イメージがわかない。

↑

matchを調べてみる †

http://d.hatena.ne.jp/taktamur/20091115/1258292009

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