[Project Euler] Problem 25

원문: Problem 25
The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

피보나치 수열은 순환 관계에 의해서 정의된다:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

그래서 처음부터 12개의 항은 다음이 될 것이다:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
12번째 항인 F12는 3자리 숫자를 포함하는 첫 번째 항이다.

피보나치 수열에서 1000자리 숫자를 포함하는 첫 번째 항은 무엇인가?

가능하다면 재귀로 풀지 않는 것이 더 빠르게 풀 수 있을 것이다. 재귀로 풀게 되면 1000개의 함수가 호출이 되는데, 파이썬에서는 1000개 호출은 불가능할 뿐더러 C에서는 가능하더라도 시스템에 부하가 많이 걸릴 것이다.

Python
F1 = 1 
F2 = 1 
F3 = 2 
n = 2 
while F3 < 10**(1000-1):
    n += 1
    F3 = F1 + F2
    F1 = F2
    F2 = F3

print(n)
접기

댓글 없음:

댓글 쓰기