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

Project Euler 36

http://projecteuler.net/index.php?section=problems&id=36 10進の回文数を再帰的に生成して、それが2進で回文になっているかを調べる。

Project Euler 21

F#

http://projecteuler.net/index.php?section=problems&id=21 Sequenceは遅延評価らしいです。大きなSequenceもメモリを食うことはありません。 let N = int64 1e8 printfn "%d" (Seq.sum (seq { 1L..N }))Seq.toListもListを中に持って一つずつ出していくよ…

Project Euler 35

http://projecteuler.net/index.php?section=problems&id=35 100万までの素数を求めてsetにしてすぐに素数判定ができるようにする。 回転はalgorithmのrotateを使う。

Project Euler 20

F#

http://projecteuler.net/index.php?section=problems&id=20 他の数値型から多倍長整数型への変換は次のようにします。 let n = 1 printfn "%A" (System.Numerics.BigInteger n)ただ、これだとちょっと名前が長いのが困ります。こう書けば短く済みます。 ope…

Project Euler 34

http://projecteuler.net/index.php?section=problems&id=34 これも暗黙の上限がある問題。 そこまでの整数をしらみつぶしにしても十分速いが、例えば123と213は同じ数に変換されるので、重複組合せを出すクラスを使うと非常に速い。これを自作した。

Project Euler 19

F#

http://projecteuler.net/index.php?section=problems&id=19 これはライブラリを使う問題ではなく、与えられた1900年1月1日の曜日を元に計算するものです。yieldを使うと記述しやすいでしょう。

Project Euler 32

http://projecteuler.net/index.php?section=problems&id=32 重複は数えないからsetを使う。そして和を取る。iterableでsetを引数に取れるようにしたが、よく考えたらaccumulateを使えばいいだけだった。これがnumericにあることをいつも忘れる。

Project Euler 18

F#

http://projecteuler.net/index.php?section=problems&id=18 経路を辿るときに座標と経路番号の3要素のタプルで状態を持ってunfoldしています。 2要素のタプルは簡単にアクセスできますが、 let t = (1, 2) printfn "%d" (snd t) // 23つ以上の要素のタプル…

Project Euler 31

http://projecteuler.net/index.php?section=problems&id=31 再帰で簡単にかけるので、メタプログラミングしてみた。

Project Euler 17

F#

http://projecteuler.net/index.php?section=problems&id=17 再帰的にも書けそうですが、ここでは配列を使っています。

Project Euler 30

http://projecteuler.net/index.php?section=problems&id=30 この問題は調べる範囲だけ。あとは素直に書くのみ。

Project Euler 16

F#

http://projecteuler.net/index.php?section=problems&id=16 ビット演算子は同じ記号を3つ重ねます。&&&, |||, ^^^, ~~~, >> があります。 多倍長整数もビット演算できます。 let rec digits n = if n = 0I then [] else (digits (n / 10I)) @ [int (n % 10I…

Project Euler 289(3)

http://projecteuler.net/index.php?section=problems&id=289組んでみると予想以上に難しくて、かなり雑な方法でなんとかL(2, 2)が出るようにした。しかし、L(3, 3)は間違っている。しかもかなり遅い。 やっとL(2, 3)とL(3, 2)が等しくなった。まだL(3, 3)は…

Project Euler 29

http://projecteuler.net/index.php?section=problems&id=29 この問題は、まともに計算すると大変なので、素因数分解を行う。そして、その結果をsetに入れていく。 入れていくのにF#のiterが便利なのでそれを作った。 template<typename T, typename U> void iter(T& f, U& g) { whil</typename>…

Project Euler 15

F#

http://projecteuler.net/index.php?section=problems&id=15 この問題はcombinationを計算するだけです。 let rec C n m = if m = 0 then 1L else (C n (m - 1)) * (int64 (n - m + 1)) / (int64 m) printfn "%d" (C 40 20)32ビットで収まらないので必要な部…

Project Euler 289(2)

http://projecteuler.net/index.php?section=problems&id=289午前中に一つ方法を思いついたが、これで本当に答えが出るのか、コーディングが難しそう、ということで未だに1行も書けていない。頭の中だけで考えているうちに夕食の時間になってしまった。そろ…

Project Euler 27

http://projecteuler.net/index.php?section=problems&id=27 単純に必要な分素数判定する。素数判定をするのに素数で割っていく。その素数を出すためのクラスを作った。少しずつエラトステネスのふるいをしていく。

Project Euler 14

F#

http://projecteuler.net/index.php?section=problems&id=14 コラッツの問題です。配列の要素を0にし、長さが分かるたびにそれを配列に書き込んでいきます。コラッツ列は一定の値以下なら1→2→4→1以外はループしないという実験から来る事実を使っています。 …

Project Euler 289

http://projecteuler.net/index.php?section=problems&id=289一筆書き。これは難しいような気がする。 手でやっと37通りが出た。 1時間経っても方針が立たない。誰も解けていないようだ。風呂入って寝るかな。 風呂入って考えて一つ方針立てたけど、こんなん…

primes.h

素数や素因数分解に関するライブラリ。VC10β2で先取りしたC++0xの機能を用いている。 破壊的な変更がされる場合は別にエントリーを立てる。

Project Euler 28

http://projecteuler.net/index.php?section=problems&id=28 スパイラルの座標を次々に出すクラスを作った。

Project Euler 13

F#

http://projecteuler.net/index.php?section=problems&id=13 F#には大きな整数を扱えるbigint型があります。末尾にIをつけるとbigint型になります。 let a = [ 37107287533902102798797998220837590246510135740250I; 4637693767749000971264812489697007805…

Project Euler 26

http://projecteuler.net/index.php?section=problems&id=26 本来オイラーの定理など数学を使えば速く解ける問題だが、題意通りに書いても十分速く答えが出る。

Project Euler 12

F#

http://projecteuler.net/index.php?section=problems&id=12 素因数分解すれば簡単に約数の個数を数えることができます。n+1を素因数分解して、前に求めてあるnの素因数分解とかけて2で割ります。 これ、エラーになるんですね。 let f a = a.Head printfn "%…

Project Euler 11

F#

http://projecteuler.net/index.php?section=problems&id=11 行列をリストのリストで表してもいいですが、インデックスでランダムアクセスしやすい2次元配列を使いましょう。(リストなら線形時間かかる) 2次元配列はリストのリストがあれば簡単に作れます…

Project Euler 25

http://projecteuler.net/index.php?section=problems&id=25 以前作ったlongintクラスを使ってフィボナッチ数列を出すクラスを作る。

Project Euler 10

F#

http://projecteuler.net/index.php?section=problems&id=10 これはエラトステネスのふるいを使えという問題ですね。 新たに配列を導入します。 let a1 = [| 1; 2; 3 |]範囲でも書けます。 let a2 = [| 1..3 |]内包表記もあります。 let a3 = [| for i in 1.…

Project Euler 9

F#

http://projecteuler.net/index.php?section=problems&id=9 この手の直角三角形の問題はピタゴラス数の生成式を使うのが定番です。 a = l(m2 - n2) b = 2lmn c = l(m2 + n2) a + b + c = 2lmn' n' = m + n m > n mとnは互いに素 500を3つの積で表してそれが…

Project Euler 288

http://projecteuler.net/index.php?section=problems&id=288例すらうまく動かない。 今日もあまり時間ないのに。 勘違いしていただけだった。やっとスタートラインに着いた。 どうもあっち方向の問題みたいだけど、読めないなあ。 あっち方向じゃなかったけ…

Project Euler 24

http://projecteuler.net/index.php?section=problems&id=24 この問題は本来順列を出す必要はないが、後々のために順列を出すクラスを作った。この問題の答えは出るが、あまりうまく動かない。