Problem #2. Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.
변역: 피보나치 수열 중 4000만이 넘지 않은 짝수의 합을 구하시오.
문제를 보는 순간 헉...
예전에 다른 언어 열심히 풀어본 문제랑 너무 비슷하다는거...
[Python] Infinite Streams in Python
[C++] Infinite Streams in C++
일단 답을 빨리 구해보려고, 이전 python소스를 약간 고쳐서 만들었다.
from itertools import *
def fibs():
yield 1;
yield 1;
h, t = tee(fibs())
t.next()
for i in imap(lambda (a,b):a+b, izip(h, t)):
yield i
def fibs():
yield 1;
yield 1;
h, t = tee(fibs())
t.next()
for i in imap(lambda (a,b):a+b, izip(h, t)):
yield i
print sum(takewhile(lambda x: x<=4000000, ifilter(lambda x: x%2==0, fibs())))
결과가 매우 잘 나왔다.
개인적으로 이런 스타일이 좋아서 ...
이와 비슷한 fibs() 코드를 F#으로 만들 방법을 찾았다.
let rec fibs = seq { yield! [1; 1]; for (x, y) in Seq.zip fibs (Seq.skip 1 fibs) -> x + y}
printfn "Problem #2 = %d" (fibs
|> Seq.take_while (fun x -> x <= 4000000)
|> Seq.filter (fun x -> x%2 = 0)
|> Seq.sum) ;;
위 Python 코드와 크게 다를게 없는 코드다.
문제는 답은 나올 거 같은데 1000만년이 걸릴 것 같다는 ;;;;
어쩔 수 없이 fibs 함수를 수정할 수 밖에 없었다.
let fibs = (1,1) |> Seq.unfold (fun (a, b) -> Some(a, (b, a+b)))
printfn "Problem #2 = %d" (fibs
|> Seq.take_while (fun x -> x <= 4000000)
|> Seq.filter (fun x -> x%2 = 0)
|> Seq.sum) ;;
뭐.. 속편하게 만드는 방법은...
아래와 같이 Iterative하게 만드는 방법도 있다.
let rec even_fibs_sum a b sum =
if (a <= 4000000) then
(even_fibs_sum b (a+b) (sum+a-(a%2)*a))
else
sum
printfn "Problem #2 = %d" (even_fibs_sum 1 1 0)
'내 생산물' 카테고리의 다른 글
| F#, Project Euler - Problem #5 (0) | 2009/05/11 |
|---|---|
| F#, Project Euler - Problem #4 (2) | 2009/05/11 |
| F#, Project Euler - Problem #1 (2) | 2009/05/10 |
| F#, Project Euler - Problem #2 (0) | 2009/05/10 |
| 테터 데스크 설치 - 미투데이 최근글 표시하기. (2) | 2007/06/11 |
| Popfly로 만든 축제 자료집 (6) | 2007/06/06 |
| Silverlight에서 한글 쉽고, 가볍게 사용하기 (13) | 2007/05/23 |
