http://projecteuler.net/index.php?section=problems&id=80 昔習った平方根を1桁ずつ求める計算法をシミュレートする。 square_rootは平方根の精度が1桁ずつよくなるリスト。例えば、 square_root = [1, 14, 141, 1414, 14142, …] その中のaは、余りと答え…

ちょっといじったら正解になった。 n = 5以上は数学的にはよくわからんが、マジックで比較的簡単。n = 3以下は手作業で求められる。結局、n = 4のときが問題だが、これもそんなに難しくない。 間違えた。4以上なら同程度だが、5以上の場合マジックが効く。 …

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=282 6時前に目が覚めて問題見たんだが。 Ackermann関数ってm = 4までなら比較的簡単なんだよね。 今日は時間がない。 あれ、どっか違ってるらしい。そんなに難しい問題だとは思…

http://projecteuler.net/index.php?section=problems&id=79 ものすごくいい加減な解法。数字が右にあるか左にあるか、各ペアで調べる。50個のリストでそれがすべて分かるので、順番が付けられる。

http://projecteuler.net/index.php?section=problems&id=4 Pythonでこう書くのを真似したい。 from itertools import ifilter, product def gen_digits(n): if n > 0: for d in gen_digits(n / 10): yield d yield n % 10 def to_number(a): return reduce(…

http://projecteuler.net/index.php?section=problems&id=78 まともに計算すると遅いので、メモ化する。 コンパイルするときは --makeをつける。それでもPython並みに遅い。 import Data.Map (Map, (!), empty, insert, lookup) n = 10^6 f m 0 = (insert 0 …

http://projecteuler.net/index.php?section=problems&id=3 素因数分解をする。 C++ではタプルが使えるのでこれを使う、pairでもいいが。 #include <iostream> #include <tuple> using namespace std; typedef tuple<int,int> Fact; int main() { Fact f = Fact(2, 3); cout << get<0>(</int,int></tuple></iostream>…

http://projecteuler.net/index.php?section=problems&id=77 Haskellなら簡単に書ける。 n = 5000 is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes) primes = 2:(filter is_prime [3,5..]) mul f p = [ g f k 0 | k <- [0..] ]…

takewhileもfilterと同じように定義する。

http://projecteuler.net/index.php?section=problems&id=76 分割数は母関数を使えば簡単。 n = 100 mul f n = [ g f k 0 | k <- [0..] ] where g (x:xs) k m | k < m = 0 | otherwise = (if mod (k - m) n == 0 then x else 0) + (g xs k (m + 1)) p = fold…

cGeneratorクラスを作って、next()で値を返すクラスはこれを継承することにする。 template<typename T> class cGenerator { public: virtual ~cGenerator() { } virtual T next() = 0; }; 本当はポインタなんか使いたくない。いちいちdeleteしなければならないのが嫌。</typename>…

http://projecteuler.net/index.php?section=problems&id=75 ピタゴラスの数の生成式を使って周囲の長さをリストにする。例えば60までなら、 [12,24,36,48,60,30,60,40,56] これをMapに入れようとしたが、メモリが足りない。 import qualified Data.Map as M…

http://projecteuler.net/index.php?section=problems&id=2 Haskellならこう。 fib = 1:2:[ a + b | (a, b) <- zip fib (tail fib) ] main = print (sum (filter even (takeWhile (<= 4 * 10^6) fib))) filterと同様にtakewhileを作る。 template<typename T, typename U, typename V> class take</typename>…

http://projecteuler.net/index.php?section=problems&id=74 チェーンにパターンがあるのがややこしい。

考え方変えたら割と簡単な漸化式が出てきて解けた。 対称性で考える。 なんとかの補題ってので簡単になるらしい。

http://projecteuler.net/index.php?section=problems&id=73 速くなる書き方もあるが、ここは題意を素直に表現。 count_numerator d = length (filter (\n -> gcd d n == 1) [(div d 3)+1..div (d-1) 2]) main = print (sum (map count_numerator [1..12000]…

http://projecteuler.net/index.php?section=problems&id=72 エラトステネスのふるいがなぜこんなに遅いのか。 import Data.Array make_primes n = filter (a!) [2..n] where a = sieve (array (2, n) [ (k, True) | k <- [2..n] ]) 2 sieve a p | a!p = sie…

Pythonでisum,ifilter,irangeを自作して、 def isum(a): s = 0 for e in a: s += e return s def ifilter(f, a): for e in a: if f(e): yield e def irange(begin, end): n = begin while n < end: yield n n += 1 print isum(ifilter(lambda n: n % 3 == 0 …

プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=281 まず、f(3,2) = 16が手でなかなか出てこなかった。 雑なコードは割とすぐ書けた。 手がかりはあるのだが、あと1時間できる自信がない。

http://projecteuler.net/index.php?section=problems&id=71 分数を使ってみた。Haskellでの分数の使い方はこんな感じ。 import Ratio a = 2 % 4 -- 1 % 2 n = numerator a -- 1 d = denominator a -- 2 b = 1 / a -- 2 % 1 分母は最後の7つだけ調べればよい…

http://projecteuler.net/index.php?section=problems&id=70 pが大きい方から、素数の組(p, q) (p ≤ q)に対し、調べていく。 import Data.List is_prime n = all (\p -> mod n p /= 0) (takeWhile (\p -> p * p <= n) primes) primes = 2:(filter is_prime […

そろそろC++の復習でもしようというのとVC10（C++0x）の機能の予習を兼ねてProject Eulerの問題を解いていく。 http://projecteuler.net/index.php?section=problems&id=1何も考えずに書くとこんな感じだろうか。 #include <iostream> using namespace std; const int </iostream>…

http://projecteuler.net/index.php?section=problems&id=60Setが自由に使うのが難しい。しかたがないので、上限を倍々していく。とても遅い。

Problem 100 もし箱の中に21個の色がついたディスクがあり、それが15個の青いディスクと6個の赤いディスクからなっており、2つのディスクをランダムに取ったとすると、2つの青いディスクを取る確率は、P(BB) = (15/21)×(14/20) = 1/2であることがわかる。 ラ…

http://projecteuler.net/index.php?section=problems&id=68 ライブラリのpermutationsでは降順に並べられないので、自作。 やたらにメモリを食って帰ってこなくなるので、コンパイルしたらすぐに返ってくるようになった。順列を出す途中で枝刈りしているん…

Problem 98 CAREという単語の文字をそれぞれ1,2,9,6に置き換えることにより、平方数1296 = 362を成す。注目すべきことは、同じ数字の置き換えによって、アナグラムのRACEもまた平方数9216 = 962を成すことである。CARE（とRACE）を平方アナグラム語と呼び、…