2010-02-01から1ヶ月間の記事一覧
Problem 67 http://projecteuler.net/index.php?section=problems&id=67 上から順に計算していく。上に前と後ろどちらかに0を付加して加算する。 3 3 0 0 3 7 4 7 4 7 4 -> 11 4 7 7 11 7 add a b = [ m + n | (m, n) <- zip a b ] next a b = [ max m n | (…
Problem 65 http://projecteuler.net/index.php?section=problems&id=65 連分数の計算法を適用する。最初に1を付加すると計算しやすい。 digits 0 = [] digits n = (mod n 10):(digits (div n 10)) a = 2:1:2:1:[ if n == 1 then 1 else n + 2 | n <- tail a…
プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=280 問題の意味を理解するのに5分。正しく理解したのかは不明。 the lower row, the upper rowの解釈に自信がない。 2×2マスの場合はできたと思うんだけど、それ以上はどうして…
Problem 63 http://projecteuler.net/index.php?section=problems&id=63 9までで考えればよい。 num_digits n = length (takeWhile (>0) a) where a = n:[ div n 10 | n <- a ] count d = length (takeWhile (\(e,n) -> n == e) [ (e, num_digits (d^e)) | e …
Problem 97 最初に知られた100万桁を超える素数は1999年に発見された。そしてそれは26972593-1というメルセンヌ素数である。2098960桁である。その後、さらに多くの桁数の2p-1という形のメルセンヌ素数が見つかった。 しかしながら、2004年に2357207桁の巨大…
http://projecteuler.net/index.php?section=problems&id=62 Haskellで辞書は次のように使う。 import qualified Data.Map as M m = M.insert 1 2 M.empty n = m M.! 1 -- 2 b = M.member 1 m -- True 3乗して各桁の数字を降順に並べて数にする。同じ数にな…
Problem 95 真約数はその数自信を除いた約数全てである。例えば、28の真約数は1,2,4,7,14となる。その和は28となるので、これを完全数と呼ぶ。 面白いことに220の真約数の和は284で284の真分数の和は220であり、これは2つの数から成るチェーンを成す。これよ…
http://projecteuler.net/index.php?section=problems&id=61 Arrayで有向グラフを作る。
Problem 94 辺の長さが整数で面積も整数の正三角形が存在しないことは簡単に示される。しかし、「ほぼ正三角形」の5-5-6という三角形は12平方単位の面積を持つ。 「ほぼ正三角形」を2つの辺の長さが等しく第三の辺はそれと1単位より違わない三角形と定義しよ…
http://projecteuler.net/index.php?section=problems&id=59 3分割して、それぞれ最頻の数を選んで、それはスペースだとみて、キーを作る。
Problem 93 集合{1, 2, 3, 4}から一度ずつ数字を使って4つの演算子(+, -, *, /)とカッコを使って、違う正の整数を成すことができる。 例えば、 8 = (4 * (1 + 3)) / 2 14 = 4 * (3 + 1 / 2) 19 = 4 * (2 + 3) - 1 36 = 3 * 4 * (2 + 1) 12 + 34のような数…
Problem 57 http://projecteuler.net/index.php?section=problems&id=57 時間がかかるのは桁数のカウント。 num_digits 0 = 0 num_digits n = 1 + (num_digits (div n 10)) a = take 1000 ((1,1):[ (p + q * 2, p + q) | (p, q) <- a ]) main = print (lengt…
Problem 92 前に出てきた数になるまで新しい数を作るよう数のチェーンが数の各桁の平方和を連続的に加えることにより作られる。 例えば、 44 → 32 → 13 → 10 → 1 → 1 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89 ゆえに1か89に到達するどのチェーンも…
Problem 55 http://projecteuler.net/index.php?section=problems&id=55 特になにもない。 digits 0 = [] digits n = (digits (div n 10)) ++ [mod n 10] numerize a = foldl1 (\x y -> x * 10 + y) a rev = numerize . reverse . digits is_palindromic n =…
Problem 91 点P(x1, y1)とQ(x1, y2)が格子点上にあり、これらに原点O(0, 0)を加えて△OPQを形成する。 どの座標も0と2の間にある場合、14個の直角三角形がある(中略)。 0 ≤ x_1, y_1, x_2, y_2 ≤ 50のとき、直角三角形はいくつあるか。 http://projecteuler…
http://projecteuler.net/index.php?section=problems&id=54 カスタムのソートはsortByを使う。 import Data.List a = [ 3, 1, 4, 1, 5 ] b = sort a -- [1,1,3,4,5] c = zip [1..] a d = sortBy cmp c -- [(2,1),(4,1),(1,3),(3,4),(5,5)] cmp (n1,m1) (n2,…
プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=279 こういう問題文が短いものは難しいにちがいない。時間もあまりないしゆっくりやろう。 すぐにいつものパターンであることがわかった。しかし、なかなかうまくいかない。結…
Problem 52 http://projecteuler.net/index.php?section=problems&id=52 6倍しても桁が上がらないことを利用する。 import Data.List digits 0 = [] digits n = (digits (div n 10)) ++ [mod n 10] normalize = sort . digits is_valid n = f n 2 where m = …
Problem 88 自然数Nが少なくとも2つの自然数の集合{a1, a2, ... , ak}の和と積で書けるとき、これを積和数と呼ぶ:N = a1 + a2 + ... + ak = a1 × a2 × ... × ak。 例えば、6 = 1 + 2 + 3 = 1 × 2 × 3。 与えられた大きさkとの集合に対して、この性質を持つ…
Problem 50 http://projecteuler.net/index.php?section=problems&id=50 2から始まる系列、3から始まる系列、をリストにして、長いものから調べていく。遅い。 import Data.Array sieve a p | a!p == True = sieve (a // [ (m, False) | m <- b, a!m ]) (p +…
Problem 86 蜘蛛Sが直方体で大きさが6×5×3の部屋の一つの角に座っており、蝿Fが反対側の角に座っている。部屋の表面を進んでSからFの最短の「直線」距離は10(中略)。 どの与えられた直方体にも「最短」経路候補が3つまであり、その最短ルートはいつも整数…
Problem 48 http://projecteuler.net/index.php?section=problems&id=48 剰余を取らなくても瞬時に答えが出た。 n = 1000 s = show (sum [ k^k | k main = print(reverse (take 10 (reverse s))) Problem 49 http://projecteuler.net/index.php?section=prob…
Problem 82 下の5×5の行列の左の列の要素のどこかから出発して右の列のマスのどこかに到着して、進む方向は上下右の経路で和が最小のものは、下に赤と太字で示される。その和は994である。 .path { font-weight:bold; color:red } 131 673 234 103 18 201 96…
http://projecteuler.net/index.php?section=problems&id=47 順に素因数分解すれば答えは出る。 is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes) primes = 2:(filter is_prime [3,5..]) div_pow n p | mod n p /= 0 = (n, 0) …
Problem 80 自然数の平方根が整数でなければ、無理数であることが知られている。このような平方根の小数の展開は無限で繰り返しはない。 2の平方根は1.41421356237309504880...で、最初の100桁の各桁の和は475である。 最初の100個の自然数に対して、無理数…
Problem 45 http://projecteuler.net/index.php?section=problems&id=45 六角数は三角数なので、三角数は無視できる。五角数と六角数を並べて比較していくだけ。 polygonal p = [ div (n * ((p - 2) * n - (p - 4))) 2 | n equal (p:ps) (h:hs) | p == h = […
Problem 77 10は素数の和に5つの方法で書ける。 7 + 3 5 + 5 5 + 3 + 2 3 + 3 + 2 + 2 2 + 2 + 2 + 2 + 2 素数の和で書く方法が5000を超える最初の値はいくつか。 http://projecteuler.net/index.php?section=problems&id=77 分割数の素数版とも言うべきもの…
http://projecteuler.net/index.php?section=problems&id=44 まず、できるだけ数学を使わない方法で書いた。Plをlが小さいほうから調べ、Pkとの和が五角数であるものを探す。ただし、kはPk+1-Pk ≤ Plを満たす限り。その中でPl + 2Pkが五角数であるものを探す…
Problem 76 5は6つの違う方法で和に書ける。 4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 100を少なくとも2つの和に書く方法は何通りあるか。 http://projecteuler.net/index.php?section=problems&id=76 これは分割数と言われるもの…
http://projecteuler.net/index.php?section=problems&id=43 ライブラリで順列を出して判定すると非常に遅い。 import Data.List primes = [2,3,5,7,11,13,17] numerize a = foldl (\x y -> x * 10 + y) 0 a is_valid a [] = True is_valid a (p:ps) = if mo…