- 追加された行はこの色です。
- 削除された行はこの色です。
[[SCALAの記事一覧]]
&topicpath;
*目次 [#h7fd4b7e]
#contents
*練習問題 S-99 Ninety Nine Scala Problems † [#q9fbf881]
S-99 Ninety Nine Scala Problems
http://aperiodic.net/phil/scala/s-99/
*問32 [#d250c212]
ユークリッドのアルゴリズムを使っているそうだ。
*ユークリッドのアルゴリズムってなんだっけ [#q3a54de7]
**(例題) 1071 と 1029 の最大公約数を求める。 [#m5f0fe7d]
1071 を 1029 で割った余りは 42
1029 を 42 で割った余りは 21
42 を 21 で割った余りは 0
よって、最大公約数は21である。
**アルゴリズム [#b477dae8]
入力を 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の略だからね。
**実行方法 [#zc6e1896]
サイトには、
gcd(36,63)
ってだけ書いてあるけど、実際には
S99Int.gcd(36,63)
だからね。
でも、これって、どういうときつかうんだろ。
「あー今日は、最大公約数でも求めたいなぁ」っていうときかな？
そんなことってないよね。
*問33 [#mceb6639]
互いに素かどうかを返す問題だ。
どうでもいいんだけど、互いに素っていう表現は３つあるって知ってた？
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 [#r9d67974]
オイラーのファイ関数
totientって、英次郎でしらべたら、
《数学》その数以下｛すう いか｝でその数と互いに素な数の個数
で、それ以外の意味ってないんだね。これって、絶対に日常使わないから、英語圏の人でも、数学詳しくない人て、普通だとおもうから、きっとみんなしらないだろうね。
「toti」って全体のっていう意味でよく使われているらしいね。Javaやっていると、このような単純んな名前付けは、名前空間で重複するからだめだとか、ほかの人が読んでも意味を連想しにくいとかで、とかく誤解がなければすべてよし、みたいな感じで、ながったらしい名前をかくんだよね。
まあ、オイラーさんに文句はいえないわけだけど。
*問35 [#j7f541bc]
最大公約数を求める問題なんだけど、回答しているプログラムがうまく通らなかった。
primesが定義されていないからだ。
回答されているプログラムをみる限りprimesにはStream形の配列に素数リストを定義したものを代入すれば、動くようなつくりになっている。
だから、どうっていうことでもないんだけどね。
**Stream [#q9928a1b]
Streamは要素が必要になったときに作成されるList(みたいなモノ)です。
要素は必要になったときに初めて作成されるので、
-要素の作成に時間がかかる場合に初期作成コストを抑えることができます。
-また、要素を全部辿らない場合に無駄な作成コストを削減できます。
-JavaのInputStreamとかとは何の関係もありません。
*問36 [#y12cb8d8]
模範解答例には２つの解き方が書いてあるが、あえて難しいほうの回答を読解してみる。
- 引数 n 元の数
- 引数 p ためしに割ってみる素数
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 の組み合わせがどのように計算されるのか、イメージがわかない。
=> がScalaのクロージャだってことも、最初のころはわからないので、つぎのようには勘違いしない。
case クロージャ
てなってるって、どーゆうことよって思うわけさ。
match { case っていう組み合わせはパターンだ、でもこれって、
クロージャの構文と類似していて、意味合いも、ほぼそんな感じなんだよ。
scala のif はjavaのifと違って、かならず値を返すことになっている。
**matchを調べてみる [#p74826ab]
自分でまとめるよりも、はるかにわかりやすくまとめている人がいるのを発見したので、リンクしておきます。
かなりまとまっているところへリンク
http://sites.google.com/site/scalamemo/kihon-1/matchingu
ややまとまっているところへのリンク
http://d.hatena.ne.jp/taktamur/20091115/1258292009
だいたいまとめると、
***switchみたいな使い方 [#v92113d8]
val ret = x match{
case "a" => "Alpha";
case "b" => "Beta";
case _ => "unknown";
}
***マッチさせながら変数に代入 [#s66e137f]
def generalSize(x:Any) = x match{
case s:String => s.length;
case m:Map[_,_] => m.size;
case _ => -1;
}
*scalaの_アンダーバー [#of6c8bab]
-あるときは高階関数の引数
-あるときは仮引数
-あるときはmatchの、何でもマッチ表記
_* だと可変長の配列のマッチ表記
*問37 [#ibbacf23]
問３６の答えをつかって、もっと簡潔に問34の問題をとこうという趣旨だとおもうが、ここでは、ふたたび
foldLeftの使い方の復習をしてみたいと思う。一度、この９９問題の例題にとりあげたのだが、すっかりわすれてしまっている。
class S99Int(val start: Int) {
def totient: Int = start.primeFactorMultiplicity.foldLeft(1) { (r, f) =>
f match { case (p, m) => r * (p - 1) * Math.pow(p, m - 1).toInt }
}
}
おさらいすると、foldLeftの引数は、初期値である。で、括弧の中身は、無名関数でありますな。
無名関数の最初の(r,f)は引数で、まずは左側の引数に初期値の１が入る。で、配列の要素数分ループしますが、その際に、初期値が入っていた変数に、評価したものが格納されるしくみになっています。
今回の例ではmatchの中に、無名関数があります。引数がp,mなのでrがpになって、fがmになるってことでいいのかな？
**foldleftの説明 [#s718888f]
http://d.hatena.ne.jp/taktamur/20091114/1258210136
