2011-05-01から1ヶ月間の記事一覧

ScalaでProject Euler(19)

Problem 11この問題は特に難しいところはないですね。各マスに対して、右・下・左下・右下に4つ進んだマスが範囲内なら積を排出します。

ScalaでProject Euler(18)

Problem 10この問題はエラトステネスのふるいですね。ScalaではArrayを使うとよいと思います。配列ですね。 val a = new Array[Int](5) for(i <- 0 to 4) a(i) = i + 1 println (a(1)) // 2 println (a.toList) // List(1, 2, 3, 4, 5) []の代わりに()を使う…

Project Euler 340

http://projecteuler.net/index.php?section=problems&id=340S(50, 2000, 40)は5分で答え出たけど、ここからが難しいんだろうね。 出来た。46着。意外となんでもない問題だったけど、なんかてこずった。

ScalaでProject Euler(17)

Problem 9この問題は、ピタゴラス数生成式を使えば速く答えを得ることができます。これを使うと、 a + b + c = 2lm(m + n) となるので、500を素因数分解して約数を生成して、その一方の約数の約数を生成して条件にあてはまるか見ればよいです。 type 素因数…

Project Euler 339(3)

http://projecteuler.net/index.php?section=problems&id=339誤読していただけだった。 なにかいつもと違うと思ったら、 You are the 48th person to have solved this problem. って出てた。

ScalaでProject Euler(16)

Problem 9題意どおりに3辺の取りうる値と条件をforの中に書いてしまえば解けます。 val N = 1000 val s = for(a <- 1 to N; b <- (a + 1) to N; c <- (b + 1) to N if a + b + c == N && a * a + b * b == c * c) yield a * b * c println (s.toList) さすが…

ScalaでProject Euler(15)

Problem 8文字列の結合は、 val s = "a" + "b" ですが、複数行にわたるときはこうします。 val s = "a" + "b" これはダメです。 val s = "a" + "b" その行で次の行につながることを示さないといけないんでしょうね。Pythonよりはゆるいです。

ScalaでProject Euler(13)

Problem 6 val N = 100 val s = (1 to N).sum val s2 = (1 to N).map((n) => n * n).sum println (s * s - s2) これでもよいですが、fold系を使う方法もあります。 fold系メソッド 自乗和は、 (0 + 1 * 1) + 2 * 2 + ... と計算できます。これは初期値が必要…

Project Euler 339(2)

http://projecteuler.net/index.php?section=problems&id=339ちょっと考えて、簡単じゃんと思って組んでみたら、E(5)すら出てこない。おかしいな。なにが間違っているのかわからない。

Project Euler 339

http://projecteuler.net/index.php?section=problems&id=339素直な方法だと時間がかかるし、コーディングも難しい。買い物に出かけて考えていたら、ちょっと思いついたので、明日以降ゆっくり考える。

ScalaでProject Euler(12)

Problem 5この問題は最小公倍数を求めるだけですが、Intの範囲で収めようとするとちょっとだけ工夫が必要です。 reduce系メソッド 最小公倍数を次々と求めるにはreduceLeftを使います。これはPythonのreduceとだいたい同じです。違うところは初期値が取れな…

ScalaでProject Euler(11)

Problem 4 時間計測 この問題で2通りの解法を示しましたが、どちらが速いでしょう。時間計測はこんな感じです。 val t0 = System.currentTimeMillis val N = 3 val M = pow(10, N) println (palindrome(N).filter(is_product).head) println ((System.curren…

ScalaでProject Euler(10)

Problem 4次は積を生成してそれが回文数になっているか判定します。 PriorityQueue 積を生成するのは簡単ですが、それを降順に並べなければなりません。それを簡単にしかも速く可能にするのがPriorityQueueです。 import scala.collection.mutable.PriorityQ…

ScalaでProject Euler(9)

Problem 4この問題は、回文数を大きいほうから順に生成して3桁同士の積になっているかを調べる方法と、3桁同士の積を大きいほうから順に生成して回文数かどうか調べる方法の2通りがあります。今回は前者、次回は後者を考えます。 まず、回文数を生成します。…

Project Euler 338(3)

http://projecteuler.net/index.php?section=problems&id=338今朝考えていたらO(N3/4)になりそうだったので組んでみたらやっとできた。でも15分かかった。なんでかなあ。 2日半かかったのに24着。 フォーラムを見ると、O(N2/3)のアルゴリズムがあるらしい。…

Project Euler 338(2)

http://projecteuler.net/index.php?section=problems&id=338きのう悩んでいたところ解決した。つまらなかった。 でも、答えを出すにはあと一工夫。そんなに難しくないと思うけど。 まだ16人なのか。

Project Euler 338

http://projecteuler.net/index.php?section=problems&id=338今日はひさしぶりにスタンバイ。 午前中に片付けたいと思っていたが、これは難しそうだ。 G(10)出た。でもO(N3)以上かかってそう。 G(1000)2分かかって出た。 やっとG(105)が出た。もう昼になるじ…

ScalaでProject Euler(8)

Problem 3 パターンマッチ パターンマッチを使えばもう少しきれいに書けます。パターンマッチは、switch〜case〜を拡張したようなものです。こんな感じに使います。 def count(n :Int) = n match { case 1 => "1" case 2 => "2" case _ => "たくさん" } prin…

ScalaでProject Euler(7)

Problem 3素因数分解して最後の素因数を表示すればよいでしょう。 Long 今まで使ってきたIntは32ビット符号付き整数です。与えられた整数はその範囲を超えています。Scalaには64ビット符号付き整数も用意されています。それがLongです。サフィックスLをつけ…

ScalaでProject Euler(6)

Problem 2 プレースホルダー 無名関数で引数を1回しか使わないとき、引数を省略できます。 (n) => n % 2 == 0 これは、 _ % 2 == 0 こう書けます。_をプレースホルダーというらしいです。そして、 (n) => n < N は、 _ < N と書けます。実はこの場合プレース…

ScalaでProject Euler(5)

Problem 2 Stream Iterableをつかったフィボナッチ数列はイケてなかったですが、もう一つHaskellと同じような無限列を生成する方法があります。それがStreamです。次はPythonのcountと同じように1ずつ増える無限列を生成するメソッドの例です。 def count(n …

ScalaでProject Euler(4)

Problem 2フィボナッチ数列ですね。これは無限に続くフィボナッチ数列を作る問題です。Pythonなら def fib(): a, b = 0, 1 while True: yield b a, b = b, a + b Haskellなら fib = 1:1:[ a + b | (a, b) <- zip fib (tail fib) ] Scalaには2種類の無限列が…

Project Euler 337

http://projecteuler.net/index.php?section=problems&id=337眠いけど、問題読んだ。今日は久しぶりに夜中まで戦える、と意気込んでみたが、よく分からないなあ。とりあえず、オイラーのφ関数を書いてみるか。 書けた。 S(10)出たけど、S(100)が全然違う。 S…

ScalaでProject Euler(3)

Problem 1Pythonなら from itertools import * N = 1000 print sum(ifilter(lambda n: n % 3 == 0 or n % 5 == 0, xrange(1, N))) Haskellなら n = 1000 main = print (sum (filter (\m -> mod m 3 == 0 || mod m 5 == 0) [1..n-1])) こんな関数型で書くこと…

ScalaでProject Euler(2)

さて、Problem 1から解いていきましょうか。Problem 1この問題の最も簡単な解き方は、オイラー図を描くことです。オイラー図はここではベン図と同じようです。すなわち、3の倍数の和と5の倍数の和を足して、そこから重なる部分の15の倍数の和を引くことです…

ScalaでProject Euler(1)

Scalaは書きやすくて実行速度も速いという話なので、これからProject Eulerの問題を解きながら勉強していきます。関数型ということなので、HaskellとPythonと比較しながら進められたらと思います。 まず、ScalaはJavaVM上で動くのでそれをインストールしなけ…

n次方程式の判別式の具体的表示(2)

判別式を根で表せたので、今度は基本対称式で表すことを考えましょう。3次方程式の場合基本対称式は根をp, q, rで表したとき、 s1 = p + q + r s2 = pq + pr + qr s3 = pqr の3つがあります。判別式は6次なので、これらの基本対称式の積で6次になる式の線形…

n次方程式の判別式の具体的表示(1)

現代思想2011年4月号 特集=ガロアの思考 若き数学者の革命作者: 上野 健爾,吉田 輝義,砂田 利一,黒川 信重,小島 寛之,竹内 薫出版社/メーカー: 青土社発売日: 2011/03/28メディア: ムック購入: 15人 クリック: 269回この商品を含むブログ (6件) を見るこの雑…

Project Euler 336

http://projecteuler.net/index.php?section=problems&id=336これはしらみつぶしだから簡単だろう、と思って書いてみたら例とあわない。誤読していた。ちょっと考えたらこれはさらにやさしい問題だとわかった。先週はHardとMiddle、今週はEasyだったのね。じ…