HaskellでProject Eulerに挑戦してみた
- 2008-08-24
- カテゴリ: その他のプログラミング
- タグ: アルゴリズム Haskell
id:gomi-boxに触発されて、Project Eulerに挑戦してみた。
Project Eulerみたいな、アルゴリズム的なものを書いて一人でくねくねする遊びは、Haskellとの相性が良すぎる。
コードは続きで。
Problem 1
1,000 未満の 3 か 5 の倍数になっている数字の合計を求めよ。
prob1 = sum [x | x <- [1..999], (mod x 3 == 0) || (mod x 5 == 0)]
Ans. 233168
リスト内包表記が便利すぎる。
Problem 2
(フィボナッチ) 数列の項が400万を超えない範囲で、偶数の項の総和を求めよ。
prob2 = sum [x | x <- takeWhile (< 4000000) fib, even x]
where fib = 1:2:[x + y | (x, y) <- zip fib (tail fib)]
Ans. 4613732
内包表記++。相変わらずフィボナッチ数列の書きやすさは半端ない。
Problem 3
600851475143 の素因数のうち最大のものを求めよ。
prob3 = maximum $ factorize 600851475143 (2:[3,5..])
where factorize n (x:xs) | n < x * x = [n]
| mod n x == 0 = x:factorize (div n x) (x:xs)
| otherwise = factorize n xs
Ans. 6857
素因数分解してから最大値を取得するだけの簡単なお仕事。
Problem 4
3桁の数の積で表される回文数のうち最大のものはいくらになるか。
prob4 = maximum [x * y | x <- [100..999], y <- [100..999], isPalindrome $ show (x * y)]
where isPalindrome [] = True
isPalindrome [x] = True
isPalindrome [x,y] = x == y
isPalindrome (x:xs) = (x == last xs) && (isPalindrome $ init xs)
Ans. 906609
3桁の数の積を総当りして、回文になっているものの最大値を取り出すだけの簡単なお仕事。ただし、重い。
Problem 5
1 から 20 までの整数全てで割り切れる数字の中で最小の値はいくらになるか。
prob5 = foldl1 lcm [2..20]
Ans. 232792560
20までの整数の最小公倍数を求める。簡潔すぎて感動。
Problem 6
最初の100個の自然数について和の二乗と二乗の和の差を求めよ。
prob6 = (sum [1..100]) ^ 2 - (sum $ map (^ 2) [1..100])
Ans. 25164150
これも簡潔。
Problem 7
10001 番目の素数を求めよ。
prob7 = primes !! 10000
where primes = f [2..] where f (x:xs) = x:f (filter (\n -> mod n x /= 0) xs)
Ans. 104743
エラトステネスの篩を使って素数の無限リストを得る。しかし、重い。
Problem 8
以下の1000桁の数字から5つの連続する数字を取り出してその積を計算する。そのような積の中で最大のものの値はいくらか
import List
prob8 = maximum $ map f $ tails "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
where f ss = product $ map (read . (: [])) $ take 5 ss
Ans. 40824
重そうな処理に見えて、一瞬で答えが出る。take 5 ssが必ずしも5要素返さないから、最小値を求めようとするとうまくいかないかも。Char型をInt型に変換する関数ってないのかな？(read . (: []))とかやってて少し気持ち悪い。
まとめ
Haskell楽しすぎるー
トラックバックURL
- http://liosk.blog103.fc2.com/tb.php/138-c5dd8cbc