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

フィボナッチ数列

C++

フィボナッチ数列を適当に作ります。 class cFib : public cIterable<int> { int a; int b; public: cFib() : a(1), b(1) { } bool exists_next() { int tmp = b; b += a; a = tmp; return true; } int value() const { return a; } }; shared_ptr<cIterable<int>> fib() { retur</citerable<int></int>…

count

C++

Pythonのcountは指定した数から順に整数を出していきます。ここでは、引数で公差も指定できるようにしました。 class cCount : public cIterable<int> { int current; int delta; public: cCount(int s, int d) : current(s - d), delta(d) { } bool exists_next(</int>…

takewhile

C++

takewhileは、叙述関数がtrueである限り値があれば出し続けます。 template<typename T, typename U> class cTakeWhile : public cIterable<T> { U pred; shared_ptr<cIterable<T>> gen; public: cTakeWhile(U p, shared_ptr<cIterable<T>> g) : pred(p), gen(g) { } bool exists_next() { return gen->exists_next</citerable<t></citerable<t></t></typename>…

catch

C++

失敗した話。 #include <string> int main() { try { throw(""); } catch(std::string e) { ; } } こんなコードで例外を捕えられませんでした。実際にはこれほど単純なコードではなかったのですが。無意識のうちにこういうコードから連想していたようです。 #include <string></string></string>…

map

C++

リストに対して写像を施して別のリストを作ります。 template<typename T, typename U, typename V> class cMap : public cIterable<T> { U func; shared_ptr<cIterable<V>> gen; public: cMap(U f, shared_ptr<cIterable<V>> g) : func(f), gen(g) { } bool exists_next() { return gen->exists_next(); } T value() const { r</citerable<v></citerable<v></t></typename>…

reduce

C++

sumを作りたいのですが、その前にPythonでreduceと言ったり、Haskellでfoldと言ったりするものを作ります。リストなどに関数を次々に適用してスカラー値にするものです。(1, 2, 3)にf(x, y) = 10x + yを適用していくと、初期値を0として、 10 * 0 + 1 -> 1 1…

filter

C++

Pythonのifilterを作ります。叙述関数を適用してtrueになる要素だけ出します。 以下は、3の倍数だけ出力するコードです。 template<typename T, typename U> class cFilter : public cIterable<T> { U pred; shared_ptr<cIterable<T>> gen; public: cFilter(U p, shared_ptr<cIterable<T>> g) : pred(p), gen(g) { </citerable<t></citerable<t></t></typename>…

range

C++

Pythonのitertoolsを使ったような書き方がC++でもできるようにライブラリを作っていきます。具体的には、例えば、1から10の和を求めるときにこう書けるようにします。 cout << sum(range(1, 11)) << endl; Pythonのxrangeやtakewhileをクラスを使って実現し…

Project Euler 150

http://projecteuler.net/index.php?section=problems&id=150 Pythonってこういう書き方ができたんですね。知らなかった。 for (i, j), s in izip(gen_index(N), gen_pseudo_random()): これとの連想で、ラムダでもこういう書き方ができます。 lambda (i, j)…

Project Euler 149(2)

http://projecteuler.net/index.php?section=problems&id=149 よく考えたら、これって左から順に考えたほうが簡単ですね。そうすると、全体の和、最大の和、右端を含む最大の和の3つを考えれば済みます。こうするとコードがすっきりした上、46秒でした。再帰…

Project Euler 149

http://projecteuler.net/index.php?section=problems&id=149 整数の列に対して部分列の和の最大を求める問題です。 列の長さをnとすると、部分列の決め方でO(n2)、和を取ってO(n3)の計算量になります。和は重複を避けるとO(n2)となります。しかし、これでも…

Project Euler 148

http://projecteuler.net/index.php?section=problems&id=148 数学的にはよくわかりませんが、実際に数えてみるとわかります。1行で7で割れない数えてみると、明らかな法則性が見えてきます。7進数で考えるとわかりやすいでしょう。その和は、7のべき乗まで…

Project Euler 147

http://projecteuler.net/index.php?section=problems&id=147 水平の長方形の個数の計算は電卓レベルなので、斜めの長方形について考えます。 この問題はよく考えると、同じ長方形がいくつあるかという数え方と、点を固定してそれを頂点とする長方形はいくつ…

Project Euler 146

http://projecteuler.net/index.php?section=problems&id=146 すぐにn2は30で割って余りが10でなければならないとわかるでしょう。すなわち、nは30で割って余りが10か20です。しかし、このnに対してまともに素数判定をやっていてはいくら時間があっても足り…

Project Euler 145

http://projecteuler.net/index.php?section=problems&id=145 題意どおりに書くと、数時間かかりそうです。 def digits(n): while n: yield n % 10 n /= 10 def reverse(n): return reduce(lambda x, y: x * 10 + y, digits(n)) def is_reversible(n): retur…

Project Euler 144

http://projecteuler.net/index.php?section=problems&id=144 反射ベクトルvは、入射ベクトルv0、鏡の法線ベクトルをnとすると、 v = v0 + k n (v + v0)・n = 0 が成り立ちます。

Project Euler 143

http://projecteuler.net/index.php?section=problems&id=143 ∠BTC = ∠CTA = ∠ATB = 120°より、 a2 = q2 + qr + r2 b2 = p2 + pq + q2 c2 = r2 + rp + p2 が成り立ちます。個々の整数解はピタゴラス数と同じように求められます。 x = q / a y = r / a と置き…

Project Euler 142

http://projecteuler.net/index.php?section=problems&id=142 (x - y) + (y - z) = x - z で、3つとも平方数なのでピタゴラス数であることがわかります。あとはzを決めればx, yが決まりますが、単にzの必要な範囲について調べると、20分くらいかかりました。…

Project Euler 141

http://projecteuler.net/index.php?section=problems&id=141 rがdとqの間のとき、公差をaとして、 n = r + r/a * ra = r + r2 これは平方数になり得ないので、rが一番小さいということになります。そうすると、 n = r + ra * ra2 = r + r2a3 aをs/t(sとtは…