scala 99problem 32~
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
[[SCALAの記事一覧]]
&topicpath;
*目次 [#h7fd4b7e]
#contents
*練習問題 S-99 Ninety Nine Scala Problems † [#q9fbf881]
S-99 Ninety Nine Scala Problems
http://aperiodic.net/phil/scala/s-99/
*問1~31 [#y3bbd7cc]
S-99 Ninety Nine Scala Problemsの1~31問まではこちら
[[scala]]
*問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 ...
回答はこんな感じだ。
object S99Int {
def gcd(m: Int, n: Int): Int = if (n == 0) m else gcd(...
}
久しぶりにみたから、目が慣れていない。
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...
}
class S99Int(val start: Int) {
def isCoprimeTo(n: Int): Boolean = S99Int.gcd(start, n...
}
ウェブでの回答は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」って全体のっていう意味でよく使われているらしいね...
まあ、オイラーさんに文句はいえないわけだけど。
*問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) => (...
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]
問36の答えをつかって、もっと簡潔に問34の問題をとこうと...
foldLeftの使い方の復習をしてみたいと思う。一度、この99...
class S99Int(val start: Int) {
def totient: Int = start.primeFactorMultiplicity.foldLe...
f match { case (p, m) => r * (p - 1) * Math.pow(p, m ...
}
}
おさらいすると、foldLeftの引数は、初期値である。で、括弧...
無名関数の最初の(r,f)は引数で、まずは左側の引数に初期値の...
今回の例ではmatchの中に、無名関数があります。引数がp,mな...
**foldleftの説明 [#s718888f]
http://d.hatena.ne.jp/taktamur/20091114/1258210136
*問38 [#u2345b5a]
回答をみると、これは実行時間計測サンプルとして使えますな。
処理内容自体を引数として渡しているところが、Scalaっぽい書...
**ブロック受け側 [#o4e822c7]
def time[A](label: String)(block: => A): A = {
val now = System.currentTimeMillis()
val ret = block
println(label + ": " + (System.currentTimeMillis() - ...
ret
}
引数の型はJavaの”クラス 変数名”という書き方ではなく"変数...
で、=>ってなんだっけ?
**ブロックを使った呼び出し側 [#ad62b395]
time("P34 (" + n + ")") {
n.totientP34
}
ブロックは、変数としては渡しておらず、引数とは別に右隣に...
**takeWhile [#ufc03432]
久しぶりにtakeWhileがでてきて使い方を復習してみる
***takeWhile使い方の例 [#o5641f57]
まずは、処理対象のリストを用意しておきましてと、
scala> val list = List(1,2,3,4,5)
list: List[Int] = List(1, 2, 3, 4, 5)
こんな風に書くと、条件を満たす要素を返す処理かと思います...
scala> list.takeWhile( _ < 4)
res18: List[Int] = List(1, 2, 3)
でも違うんです。条件を満たさないとそれ以降の要素を無視す...
scala> list.takeWhile( _ > 3 )
res19: List[Int] = List()
たぶん次の結果を想定してしまいますが、
List(1, 2, 3)
これは、要素の最初が1だから 1>3 となって、条件を満たさ...
それ以降の要素を無視するようになっています。
**force [#y664ec78]
下記の模範回答のコードの一部にtimeだとか、forceとか使われ...
time("Preload primes") {
primes takeWhile { _ <= Math.sqrt(n) } force
}
timeって、よくわかんないなぁ。繰り返し実行しそうなイメー...
APIにでもかいてあんのかな?とか思って、scala api でググっ...
http://www.scala-lang.org/api/current/index.html
をみてみたら、検索テキストボックスがあったから、そこにtim...
forceについては、まったく何もでてきやしない。
***forceについて触れてある記事 [#b088e3f9]
Scala6階:型
http://www.h7.dion.ne.jp/~samwyn/Scala/type.htm
にて
Iterableの遅延相当型。
def force: Iterable[A]
Arrayを結果するforceのみを強制。
abstract def force: Array[A]
と書いてあった。
なんのことやらである。強制的に宣言するのであろうか?
もう一つあったので、書いておく
***"LazyJ: Seamless Lazy Evaluation in Java"。 LazyJ につ...
http://www.kmonos.net/wlog/69.html
にて下記コードが書いてあり
class List {
int head
lazy List tail;
List( int h, lazy List t ) { head=h; tail=t; }
static lazy List intsFrom(int n) { return new List(n, i...
}
int n = intsFrom(1).tail.tail.head; // 3
次のような解説が記載されていました。
lazyでない型が必要な文脈でlazyな型の値が現れていたら、
そこでforceする
(例えば ***.tail の *** には 非lazyなListが来るべきなの...
逆なら逆にdelayする。それだけ。
ちょっと面白いなあと思ったのは、lazy List を返すメソッド...
それはreturnの式だけではなくて、 メソッド全体をdelayする...
確かにそれは便利かも。 実装は明示的にサンクを操作するJav...
Javaを拡張しましたという話を見るたびに Polyglot の名前を...
誰か「3分でわかるPolyglot」とか書くとよいよ!
えーと、自分の理解力では、1%ぐらいしか理解できんなぁ。
何が1%かというと、それは、forceとは遅延評価に関係した単...
そこで今度は "Scala force 遅延評価"でググってみた。
そうすると、概念的な記事がwikiに掲載されていました。
***forceについて書かれている遅延評価のwiki [#df04a174]
http://ja.wikipedia.org/wiki/%e9%81%85%e5%bb%b6%e8%a9%95%...
-実際の計算が行われていない中間状態の時それをプロミス (pr...
-計算の実体をさしてサンク (thunk) といい、
-プロミスを強制(force)することで値が計算される。
この概念と単語をしらないといけなかったのだね。つまり、こ...
そのまま、前置きの説明もなく、forceがどうのこうのと書いて...
***結論 [#jfb97fb0]
説明はみつけられなかったが、遅延評価部分を、「ここで評価...
*問39 [#tcc264bc]
解答にあるprimesはどこにも定義されていないようだ。
この解答を理解するには次のことを理解するひつようがある。
-配列の変数を宣言して、インスタンスに数値の要素を持つ配列...
-配列の切り出し方法と最終的にリストにする方法
**解答は次のようになっている。 [#k286a1ac]
object S99Int {
def listPrimesinRange(r: Range): List[Int] =
primes dropWhile { _ < r.first } takeWhile { _ <= r.l...
}
配列変数の後ろにスペースをおいて dropWhileと書くのがscala...
配列へInt型の数値を格納する例
val primes = Array(1,2,3,5,7,11,13)
実行するには下記のように入力する
S99Int.listPrimesinRange(2 to 7)
結果
List[Int] = List(2, 3, 5, 7)
**実験してみた [#a2367f96]
次のコードを実験してみた
primes dropWhile { _ < 3 }
結果
Array[Int] = Array(3, 5, 7, 11, 13)
**実験してみた [#cf481440]
Array(3, 5, 7, 11, 13) toList
結果
List[Int] = List(3, 5, 7, 11, 13)
**考察 [#o44c2fd2]
scalaは配列を主語にしてスペース動詞という感じでプログラ...
終了行:
[[SCALAの記事一覧]]
&topicpath;
*目次 [#h7fd4b7e]
#contents
*練習問題 S-99 Ninety Nine Scala Problems † [#q9fbf881]
S-99 Ninety Nine Scala Problems
http://aperiodic.net/phil/scala/s-99/
*問1~31 [#y3bbd7cc]
S-99 Ninety Nine Scala Problemsの1~31問まではこちら
[[scala]]
*問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 ...
回答はこんな感じだ。
object S99Int {
def gcd(m: Int, n: Int): Int = if (n == 0) m else gcd(...
}
久しぶりにみたから、目が慣れていない。
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...
}
class S99Int(val start: Int) {
def isCoprimeTo(n: Int): Boolean = S99Int.gcd(start, n...
}
ウェブでの回答は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」って全体のっていう意味でよく使われているらしいね...
まあ、オイラーさんに文句はいえないわけだけど。
*問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) => (...
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]
問36の答えをつかって、もっと簡潔に問34の問題をとこうと...
foldLeftの使い方の復習をしてみたいと思う。一度、この99...
class S99Int(val start: Int) {
def totient: Int = start.primeFactorMultiplicity.foldLe...
f match { case (p, m) => r * (p - 1) * Math.pow(p, m ...
}
}
おさらいすると、foldLeftの引数は、初期値である。で、括弧...
無名関数の最初の(r,f)は引数で、まずは左側の引数に初期値の...
今回の例ではmatchの中に、無名関数があります。引数がp,mな...
**foldleftの説明 [#s718888f]
http://d.hatena.ne.jp/taktamur/20091114/1258210136
*問38 [#u2345b5a]
回答をみると、これは実行時間計測サンプルとして使えますな。
処理内容自体を引数として渡しているところが、Scalaっぽい書...
**ブロック受け側 [#o4e822c7]
def time[A](label: String)(block: => A): A = {
val now = System.currentTimeMillis()
val ret = block
println(label + ": " + (System.currentTimeMillis() - ...
ret
}
引数の型はJavaの”クラス 変数名”という書き方ではなく"変数...
で、=>ってなんだっけ?
**ブロックを使った呼び出し側 [#ad62b395]
time("P34 (" + n + ")") {
n.totientP34
}
ブロックは、変数としては渡しておらず、引数とは別に右隣に...
**takeWhile [#ufc03432]
久しぶりにtakeWhileがでてきて使い方を復習してみる
***takeWhile使い方の例 [#o5641f57]
まずは、処理対象のリストを用意しておきましてと、
scala> val list = List(1,2,3,4,5)
list: List[Int] = List(1, 2, 3, 4, 5)
こんな風に書くと、条件を満たす要素を返す処理かと思います...
scala> list.takeWhile( _ < 4)
res18: List[Int] = List(1, 2, 3)
でも違うんです。条件を満たさないとそれ以降の要素を無視す...
scala> list.takeWhile( _ > 3 )
res19: List[Int] = List()
たぶん次の結果を想定してしまいますが、
List(1, 2, 3)
これは、要素の最初が1だから 1>3 となって、条件を満たさ...
それ以降の要素を無視するようになっています。
**force [#y664ec78]
下記の模範回答のコードの一部にtimeだとか、forceとか使われ...
time("Preload primes") {
primes takeWhile { _ <= Math.sqrt(n) } force
}
timeって、よくわかんないなぁ。繰り返し実行しそうなイメー...
APIにでもかいてあんのかな?とか思って、scala api でググっ...
http://www.scala-lang.org/api/current/index.html
をみてみたら、検索テキストボックスがあったから、そこにtim...
forceについては、まったく何もでてきやしない。
***forceについて触れてある記事 [#b088e3f9]
Scala6階:型
http://www.h7.dion.ne.jp/~samwyn/Scala/type.htm
にて
Iterableの遅延相当型。
def force: Iterable[A]
Arrayを結果するforceのみを強制。
abstract def force: Array[A]
と書いてあった。
なんのことやらである。強制的に宣言するのであろうか?
もう一つあったので、書いておく
***"LazyJ: Seamless Lazy Evaluation in Java"。 LazyJ につ...
http://www.kmonos.net/wlog/69.html
にて下記コードが書いてあり
class List {
int head
lazy List tail;
List( int h, lazy List t ) { head=h; tail=t; }
static lazy List intsFrom(int n) { return new List(n, i...
}
int n = intsFrom(1).tail.tail.head; // 3
次のような解説が記載されていました。
lazyでない型が必要な文脈でlazyな型の値が現れていたら、
そこでforceする
(例えば ***.tail の *** には 非lazyなListが来るべきなの...
逆なら逆にdelayする。それだけ。
ちょっと面白いなあと思ったのは、lazy List を返すメソッド...
それはreturnの式だけではなくて、 メソッド全体をdelayする...
確かにそれは便利かも。 実装は明示的にサンクを操作するJav...
Javaを拡張しましたという話を見るたびに Polyglot の名前を...
誰か「3分でわかるPolyglot」とか書くとよいよ!
えーと、自分の理解力では、1%ぐらいしか理解できんなぁ。
何が1%かというと、それは、forceとは遅延評価に関係した単...
そこで今度は "Scala force 遅延評価"でググってみた。
そうすると、概念的な記事がwikiに掲載されていました。
***forceについて書かれている遅延評価のwiki [#df04a174]
http://ja.wikipedia.org/wiki/%e9%81%85%e5%bb%b6%e8%a9%95%...
-実際の計算が行われていない中間状態の時それをプロミス (pr...
-計算の実体をさしてサンク (thunk) といい、
-プロミスを強制(force)することで値が計算される。
この概念と単語をしらないといけなかったのだね。つまり、こ...
そのまま、前置きの説明もなく、forceがどうのこうのと書いて...
***結論 [#jfb97fb0]
説明はみつけられなかったが、遅延評価部分を、「ここで評価...
*問39 [#tcc264bc]
解答にあるprimesはどこにも定義されていないようだ。
この解答を理解するには次のことを理解するひつようがある。
-配列の変数を宣言して、インスタンスに数値の要素を持つ配列...
-配列の切り出し方法と最終的にリストにする方法
**解答は次のようになっている。 [#k286a1ac]
object S99Int {
def listPrimesinRange(r: Range): List[Int] =
primes dropWhile { _ < r.first } takeWhile { _ <= r.l...
}
配列変数の後ろにスペースをおいて dropWhileと書くのがscala...
配列へInt型の数値を格納する例
val primes = Array(1,2,3,5,7,11,13)
実行するには下記のように入力する
S99Int.listPrimesinRange(2 to 7)
結果
List[Int] = List(2, 3, 5, 7)
**実験してみた [#a2367f96]
次のコードを実験してみた
primes dropWhile { _ < 3 }
結果
Array[Int] = Array(3, 5, 7, 11, 13)
**実験してみた [#cf481440]
Array(3, 5, 7, 11, 13) toList
結果
List[Int] = List(3, 5, 7, 11, 13)
**考察 [#o44c2fd2]
scalaは配列を主語にしてスペース動詞という感じでプログラ...
ページ名: