12345678999(123억...)과 99987654321(999억...) 사이의 피보나치 수를 모두 더하면 얼마인가 에 대한 풀이를 해보았다. (원문 )
수의 범위가 매우 크기 때문에 루프 대신 generator를 사용했다. (루프로 코드를 짜보았지만 Quad Core에서도 오랜 시간 계산이 끝나지 않아서 포기했다)
import cProfile
import itertools
def Fibonacci_generator():
""" 피보나치 수를 구하는 generator """
yield 0
yield 1
prev1 = 0 # n-2
prev2 = 1 # n-1
result = 0
while True:
try:
result = prev1 + prev2
yield result
prev1 = prev2
prev2 = result
except OverflowError:
break
def solve(start, end):
""" star ~ end 사이의 피보나치 수의 합을 구하는 함수."""
total = 0L
for fib in Fibonacci_generator():
if fib >= end:
break
if fib > start:
total += fib
return total
def solve2(start, end):
""" star ~ end 사이의 피보나치 수의 합을 구하는 함수."""
return sum(itertools.takewhile(
lambda fib: fib < end,
itertools.dropwhile(lambda fib: fib > start,
Fibonacci_generator())))
start = 12345678999L
end = 99987654321L
cProfile.run('solve(%d, %d)' % (start, end))
print solve(start, end)
cProfile.run('solve2(%d, %d)' % (start, end))
print solve2(start, end)결과는 아래와 같다.
$python fibo.py
60 function calls in 0.000 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 fibonachi.py:25(solve)
57 0.000 0.000 0.000 0.000 fibonachi.py:9(Fibonacci_generator)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
205486422643
118 function calls in 0.000 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 fibonachi.py:35(solve2)
6 0.000 0.000 0.000 0.000 fibonachi.py:37(<lambda>)
51 0.000 0.000 0.000 0.000 fibonachi.py:38(<lambda>)
57 0.000 0.000 0.000 0.000 fibonachi.py:9(Fibonacci_generator)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 0.000 0.000 {sum}
205486422643
