problem2
2008/04/10
昨日の続きで、Project Eulerの問題をpythonで
#! /usr/bin/python # -*- coding: cp932 -*- ''' フィボナッチ数列の項は前の2つの項の和である。最初の2項を 1, 2 とすれば、最初 の10項は以下の通りである。 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 数列の項が400万を超えない範囲で、偶数の項の総和を求めよ。 ''' fibdic = {1: 1, 2: 2} def fib(n): global fibdic if n < 1: raise Exception, "arg is not plus value." if not fibdic.has_key(n): fibdic[n] = fib(n - 1) + fib(n - 2) return fibdic[n] def genFibTo(max_size): '''フィボナッチ数列を引数で指定した数を超えない範囲で求めるイテレータジェネレータ''' n, value = 0, 0 while value <= max_size: n += 1 value = fib(n) yield value answer = sum(filter(lambda(x): x % 2 == 0, genFibTo(4000000))) print answer
追記:少し修正。ジェネレータの関数名など
思ったことなど
- 例外は、raiseで投げる。
- 例外クラスツリーは、調べてない。Exceptionが基底クラスかな?
- n++のようなインクリメント用の構文は無い? n += 1 と書く必要があるみたい。
- 関数コメントは、lispと同じように関数の最初の文として文字列を書けばいい。
- yieldを使ってみた。
- なんか遅い気がするけど、単純に計算量が多いからかな?
- 否定は、! じゃなくて not
- 辞書が、他の言語でいう連想配列
- 遅かったのでメモ化した。
- メモ(fibdic)をレキシカル環境に置きたい。スコープについてちゃんと調べないと。
- global文を消しても動くみたい。スコープについてちゃんと調べないと。
- perlみたいな、4_000_000とうような大きい数値リテラルの書き方はできなかった。