HaskellでProject Euler(Problem 1～3)
Haskellでプロジェクトオイラーに挑んでみる。おいら頑張るよ。
きっとおいらの数学力やHaskell力が低いせいだろうけど、
何だかロジックは正しいはずだけど値を大きくすると処理時間がクソ遅いから
速くなるよう部分的に書き直すことに苦労した印象が。
Problem 1. Multiples of 3 and 5
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
10未満の自然数のうち、3 または 5 の倍数のものは 3, 5, 6, 9 でがあり、これらの合計は 23 になる。
1000 未満の 3 または 5 の倍数の合計を求めよ。
少し汎用性を持たせたつもりで、何の倍数かも渡せるようにしてみた。
リスト内包表記で muls に渡した値のいずれかで割り切れる値のみのリストを作り、foldl1 で畳み込む。
もっといいやり方があるかもしれないけど、あまり悩まずすんなり解けた、かな。
Problem 2. Even Fibonacci numbers
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
フィボナッチ数列の項は前の2つの項の和である。
最初の2項を 1, 2 とすれば、最初の10項は以下の通りである。
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
数列の項が400万を超えない範囲で、偶数の項の総和を求めよ。
まず、そもそもフィボナッチ数列を求める関数を作るのに苦労した。
はじめ何も考えずに
fib 0 = 1 fib 1 = 2 fib n = fib (n-2) + fib (n-1)
としていたが、これだと数が大きくなりにつれ遅くなり、400万はとてもじゃないけど無理そうだった。
一旦諦めてHaskellのフィボナッチ数列生成関数をこの辺りを参考にしたコピペ版がこちら。
期待通り動いてくれてはいるが、これは自力では思いつかなそう。
何とか自分で考えて書いたバージョンがこちら。
fibList 関数を再帰的に呼び出して、逆順のフィボナッチ数列のリストを作っている。
リストの先頭2要素(fstElem,sndElem)を足して次項の値を求めて、それをリストの先頭に足していく。
引数のパターンマッチで、リストの先頭要素・第二要素・リスト全体を使いたかったのでasパターンを用いている。
作られたリストの先頭を取ると、その項のフィボナッチ数となる。
実行はほぼ一瞬で完了する。
Problem 3. Largest prime factor
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
13195 の素因数は 5, 7, 13, 29 である。
600851475143 の素因数のうち最大のものを求めよ。
少し考えたけどものすごく時間がかかるものしか書けなかった…ので
検索して見つけた高速な因数分解を使用したバージョンをまず書いてみた。
(まず書いてみたも何も、ほぼコピペだけど…)
もう少し考えて自力で書いたバージョンがこちら。
primeFactors 関数を再帰的に呼び出している。 nが目的の値、mが2から始めてnまで再帰呼び出し中にインクリメントする値、listが素因数のリスト。
isPrimeFactor 関数で素因数かどうかを検査する。
mがすでに追加されている素因数のリストのいずれでも割り切れず、
nを割り切れる値なら素因数としている。
最初、8行目を「isPrimeFactor = primeFactors n (m + 1) (m:list)」と
nの値を変化させずに再帰呼び出しするようにしていたが、
それでは処理が非常に遅く(2から600851475143まで1ずつインクリメントして全ての値を検査しないと再帰終了条件とならない)
euler3-1.hsからヒントを得てmが素因数なら n / m の値を新しいnとして
再帰呼び出しするようにしてみた。
