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

Project Euler 50

http://projecteuler.net/index.php?section=problems&id=50 unfoldを作ってみた。

Project Euler 41

F#

http://projecteuler.net/index.php?section=problems&id=41 順列を逆に出すだけです。

Project Euler 294(2)

http://projecteuler.net/index.php?section=problems&id=294 出来た。 22のべき乗じゃなくて11のべき乗なので、ややこしくなるかと思ったが、そうでもなかった。しかし、なぜ13secもかかるのだろうか。Pythonはこの手のリストの計算が遅いからか。

Project Euler 294(1)

http://projecteuler.net/index.php?section=problems&id=294 何時間経っているのか知らないが、もう26人も解けている。 うーん、どうやるんだろう。明日にするかな。

Project Euler 40

F#

http://projecteuler.net/index.php?section=problems&id=40 遅延評価を使うと簡単です。 (fun k -> k <= N)このラムダは、こう書けます。 ((>=) N)これは、(>=)は2つの引数を取る関数とみなせて、 (>=) N kで、 N >= kと同じになります。これをカリー化して…

Project Euler 49

http://projecteuler.net/index.php?section=problems&id=49 重複組合せを出し、それぞれについて順列を出し、その中の2つずつを取って等差数列を作って次の口が順列にあるか調べて、あればそれぞれ素数か調べる。

Project Euler 39

F#

http://projecteuler.net/index.php?section=problems&id=39 配列を使うと簡単。

Project Euler 291(5)

http://projecteuler.net/index.php?section=problems&id=291 http://d.hatena.ne.jp/inamori/20100518/p1の続き。同じようなことをやっているはてなダイアリーProject Euler 41、高速な素数判定に書いてあった。pow(a, b, c)という関数でab % cが計算できる…

Project Euler 48

http://projecteuler.net/index.php?section=problems&id=48 下10桁だけ計算すればよいから64ビットで済むが、64ビット同士の掛け算はできないので、5桁ずつに分けて計算する。

Project Euler 38

F#

http://projecteuler.net/index.php?section=problems&id=38 nで左辺第1項の範囲が決まるので、あとはpandigitalになっているかチェックするだけ。

Project Euler 1

今見たら、正答者数が10万を超えていた。100027だった。

Project Euler 37

F#

http://projecteuler.net/index.php?section=problems&id=37 2パターンは数字を右から追加するか左から追加するかなので、数字を追加する関数をそれぞれ作っておきます。 let add_right m d n = m * 10 + d let add_left m d n = m + d * nnはmが3桁なら1000…

Project Euler 47

http://projecteuler.net/index.php?section=problems&id=47 順番に素数の個数を求めるだけ。

Project Euler 36

F#

http://projecteuler.net/index.php?section=problems&id=36 10進の回文数を再帰的に出して、2進で回文数になるかを調べます。パイプライン処理というのを使ってみました。例えば、数字のリストがあってリストを逆にして10進数にする処理というのは通常、 le…

Project Euler 293

http://projecteuler.net/index.php?section=problems&id=293 3時間ですでに35人も正答している。問題文長いなあ。いちおう理解した。あとで買い物行くときに考えよう。考えるまでもなさそうな気もする。 出来た。これは至極易しい。

Project Euler 35

F#

http://projecteuler.net/index.php?section=problems&id=35 重複して素数判定したくないのでうまく代表元を選んでそれを回転して素数判定したいところです。それには、回転して最小の数を代表元に選べばよいです。例えば、791なら791→917→179だから、179を…

Project Euler 46

http://projecteuler.net/index.php?section=problems&id=46 これも一致する値を探すが、探すだけなので同じコードを使えなかった。 一致しない最初の値を出すので、dropwhileを作った。

Project Euler 34

F#

http://projecteuler.net/index.php?section=problems&id=34 Problem 30とほとんど同じです。やはり重複組合せを使います。

ミラー・ラビン素数判定法

ミラー・ラビン素数判定法(Miller-Rabin primarity test)はフェルマーテストを改良したものなので、まずはその説明をします。フェルマーの小定理は、pを素数、aをpと互いに素な自然数とすると、 an-1 ≡ 1 (mod p) が成り立ちます。例えば、p = 7, a = 2と…

Project Euler 291(4)

http://projecteuler.net/index.php?section=problems&id=291 C++でMiller-Rabin法を実装してみた。除算はdoubleで概算して微調整という手抜き。 これで15分。最初の方法では1分だが、ミラー・ラビン法のコードがあれば、ほとんどコードを書くことなく答えを…

Project Euler 291(3)

http://projecteuler.net/index.php?section=problems&id=291Miller-Rabin法を実装してみた。これは確率的な素数判定法である。(そのうち説明を書くかも) この方法と単純に素数で割っていく方法では、107くらいでは同じようなスピードだが、1015では2000倍…

Project Euler 45

http://projecteuler.net/index.php?section=problems&id=45 2つのiterableが一致する値を出すクラスを作る。 多角数を出すiterableがなかなか書けなかった。 場合分けしているのは、こうしないとギリギリintの範囲に収まらないから。long longにしておけば…

Project Euler 33

F#

http://projecteuler.net/index.php?section=problems&id=33 yieldを使うと簡単です。

市制60周年記念第38回刈谷市かきつばたマラソン大会

名古屋シティから半年振りのレース。今まで何をやっていたのだろう。会場に着くと、受付はスタジアムの外。まずは自己申告でメディカルチェック。本当はおなかの調子がちょっと悪くて寝不足なのだが、レースの前夜に十分な睡眠を取れることなどまずない。 ○…

Project Euler 292

http://projecteuler.net/index.php?section=problems&id=292 素直に組んでみたが、P(30)すら出ない。 グルグル回ってる。 回らないようにしたつもりなのに、まだP(30)合わない。 12でも想定外の多角形が出てくる。 やっぱり図形描かないとおかしな例か判別…

Project Euler 44

http://projecteuler.net/index.php?section=problems&id=44 とても遅い。確か逆から考えたほうが速いはず。

Project Euler 32

F#

http://projecteuler.net/index.php?section=problems&id=32 yieldを使うと何でも簡単に書けます。値を束縛できないところが問題ですが。

Project Euler 43

http://projecteuler.net/index.php?section=problems&id=43 最後に頭に数字をつけるところは、45からその数の各桁の合計を引けばよい。

Project Euler 31

F#

http://projecteuler.net/index.php?section=problems&id=31 素直に書くと次のようになるでしょうか。 let coins = [ 1; 2; 5; 10; 20; 50; 100; 200 ] // nポンドをm番目までのコインを使って何通りの表し方があるか let rec num_ways n m = if n = 0 || m …

Project Euler 30

F#

http://projecteuler.net/index.php?section=problems&id=30 重複組合せを自作しました(15 + 25 + 25 = 25 + 15 + 25だから)。yieldを使うと簡単ですね。 let rec repeated_combination a n = seq { if n = 0 then yield [] else if a <> [] then for b in…