[[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] 互いに素かどうかを返す問題だ。 どうでもいいんだけど、互いに素っていう表現は3つあるって知ってた? 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] 模範解答例には2つの解き方が書いてあるが、あえて難しいほうの回答を読解してみる。 - 引数 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 の組み合わせがどのように計算されるのか、イメージがわかない。 **matchを調べてみる [#p74826ab] http://d.hatena.ne.jp/taktamur/20091115/1258292009