16 October, 2008

[Project Euler] Problem 1

Project EulerをScalaで挑戦してみることにしました。

 Project Eulerってのは数学っぽいプログラミングの問題が出題されているサイトです。「どう書く.org」の数学問題とかに割と近い。特に数学を専攻した人でなくても解けるし、コンピュータでの計算時間も賢くプログラミング出来れば1分以内ぐらいだそうです。
 問題は英語で出題されているけど、和訳サイトもあります。

 アカウントを作ってログインし、profileの画面で解いた問題を選択し、正しい答えを入力すると、その問題は回答済みとなります。とりあえずの目標は25問解いてLevel 1に昇格すること。200問解くとLevel 5なんだが、78人しかいない様子。

 Project Eulerの良いところは、Webサイトに答えを入力すると、正しいか間違っているかが判ることです。現実の問題は予め正解が判っている訳ではないのが、予め正解の判っている問題を解く学校の勉強と違うところだ、というのは良く聞く話ですが、逆に言うと正解の判らない問題を解くのは勉強方法としては効率が悪い訳です。その点でProject Eulerは勉強用に向いています。
 関数型言語(に限らずにCとかJavaとかプログラミング言語一般でも良いと思いますが)の入門用の例題としては良いのではないでしょうか。

 出来るだけ毎日1題づつ解いて行こうと思っています。

 Problem 1のコードはこんな感じで簡単に解けた。

object P001 {
def main(args:Array[String]) {
println(List.range(1,10).filter{x => (x%3==0)||(x%5==0)}.foldLeft(0)(_+_))
println(List.range(1,1000).filter{x => (x%3==0)||(x%5==0)}.foldLeft(0)(_+_))
}
}

 List.rangeで1, 2,..., 9という数値のリストを作り、filterで3または5の倍数を選択し、foldLeftで合計を求めます。まぁ割とScalaとか関数型言語での定番のイディオムなんじゃなかろうか。
 解法としては勿論、受験数学的に数列の和の公式とかを使って解いてもOKなんだけど、計算時間が1分以内ならばどんな解き方でもOKと考えることにして、素直に実装した。

No comments: