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

上限が不明なときの問題解決法

例えばProblem 60のような条件を満たす最小の解を求る問題を考えます。この問題は条件を満たすような解を小さい順に列挙するのが難しいです。しかし、上限を決めてその範囲で解が存在するかを含めて解くのは比較的簡単です。このようなときは、適当に上限を…

Project Euler 356

http://projecteuler.net/index.php?section=problems&id=35624時間経ったが、いまだに立方根のところがわからない。というかできそうにない。方針が間違っているのだろうか。

ScalaでProject Euler(93)

Problem 60まず、素数列を用意します。これにどの向きに結合しても素数になるような素数を探します。例えば(3, 7)ですね。これを結合素数と呼ぶことにします。こうして2つの素数の組を列挙します。これにさらにもう一つ素数を加えて3つの素数による結合素数…

ScalaでProject Euler(92)

Problem 59シャーロックホームズに出てきたようにeが一番多いのだろうと思ったら違いました。

setで違う値を同じとみなす

タイトルの意味がわかりにくいですが、 s = set([((2, 3), 1), ((2, 4), 2), ((2, 3), 3)]) print s set([((2, 4), 2), ((2, 3), 1), ((2, 3), 3)])となりますが、タプルの第2項は無視して第1項だけで同じ値か否かを判定したいときにこれでは困るという場合…

Project Euler 355(2)

http://projecteuler.net/index.php?section=problems&id=355蟻本を見てみたら、マッチング問題というのに似ている。しかし、違う。もっと複雑な問題だ。とても解けそうな気がしない。 しかし、問題を縮小することは可能そうだ。100のときはできる。そこでど…

Project Euler 355

http://projecteuler.net/index.php?section=problems&id=355開始3分、まったく何も思いつかない。何かほかごとでもしながら考えるかな。 C(10)はあってるけど、C(30)があわない。考え直しだな。 そうか、そういうことか。 グラフの問題になったんだけど、こ…

Project Euler 354(4)

http://projecteuler.net/index.php?section=problems&id=354やっと一般化できた。一般化というのは450だけじゃなくて別の数でも解けるようにしたということ。といっても18でしか試していない。しかも6の倍数でしかも6の奇数倍のみ。あと、2か所速くした。 …

Scalaで素数判定(2)

エラトステネスのふるいです。ふつうに書いてみます。 def sieve1(N :Int) :List[Int] = { val a = new Array[Boolean](N + 1) for(n <- 2 to N) a(n) = true for(p <- Iterator.range(2, N + 1).takeWhile(p => p * p <= N) if a(p); k <- Iterator.range(p…

Scalaで素数判定(1)

Pythonと同じことをします。 まずは試し割りから。 def is_prime1(n :Int) :Boolean = Iterator.from(2).takeWhile(p => p * p <= n).forall(p => n % p != 0) def make_primes(N :Int, is_prime :Int => Boolean) :List[Int] = Iterator.range(2, N + 1).fi…

Project Euler 354(3)

http://projecteuler.net/index.php?section=problems&id=354やっとできた。45着。 64ビットでなんとかしようとしていたけどうまくいかなくて、そこをあきらめたらあっさりできた。51秒。 もうちょっと速くなって一般化ができたら上げようかな。

Project Euler 354(2)

http://projecteuler.net/index.php?section=problems&id=354あれからなにも工夫せずに組んでみたら、30秒。でもincorrect。なにが間違っているのかわからない。

Project Euler 354

現在放送大学は掃き出し法の説明中。今週も見る必要はなさそうだ。http://projecteuler.net/index.php?section=problems&id=354本当に久しぶりに出題時間に問題を見ることができた。4分遅れたが。 この問題は、フェルマーの大定理がらみで、楕円上の格子点の…

Pythonで素数判定(3)

エラトステネスのふるいの速度を確認します。まずは最も単純なもの。 def sieve1(N): a = [ True ] * (N + 1) for p in takewhile(lambda p: p * p <= N, (n for n in count(2) if a[n])): for k in xrange(p * 2, N + 1, p): a[k] = False return [ n for n…

Pythonで素数判定(2)

昨日ひどかったので考え直してみました。要するに試し割りの回数がわかればいいのです。もちろんわからないので、n前後の試し割りの回数の平均を求めます。ガウスの故事に倣って1000個ずつ取って平均します。なるべく長いスパンで見たいので、平均を取る範囲…

Pythonで素数判定(1)

どの素数判定法を使うべきか迷うことがあるのでまとめてみます。 試し割り法 ある整数が素数であるか2から順に割っていきます。nが素数かどうかの判定には√nまでの素数で割り、全て割り切れなかったら素数です。途中で割り切れたらその時点で合成数と分かり…

Project Euler 353(2)

http://projecteuler.net/index.php?section=problems&id=353やっと球面上の格子点を求めるコードが書けた。Pythonの複素数のライブラリ使えば簡単に書ける。Pythonの複素数はdoubleのはずなのでその分遅いはずだが、それでも十分に速い。 残りはもう土日に…

Project Euler 353

http://projecteuler.net/index.php?section=problems&id=353きのう夜帰ってきて問題を見たが、また問題文が長くて読む気力が。寝る前になんとか読んだ。疑問が2つ。球面上の距離はどうやって出す?これは簡単か。球面上の格子点はどうやって求める?円周上…

Project Euler 352(2)

http://projecteuler.net/index.php?section=problems&id=352朝電車の中で考えていてわかった。やっぱり誤読していた。 でも、いざコードを組もうとするとまだ考えたらないことがある。明日考えよう。

Project Euler 352

http://projecteuler.net/index.php?section=problems&id=352帰ってきたらすでに20人が正答。いや、もう7時間以上が経っているのでまだと言うべきか。問題を見たら、長い。問題を見たら買い物に出かけて考えようと思っていたのでいらつく。とりあえず読んで…