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 index of the first term in the Fibonacci sequence to contain 1000 digits?
피보나치 배열은 회귀하는 관계로 정의된다:
Fn = Fn−1 + Fn−2, F1 = 1이고 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자리 숫자가 되는 요소는 몇번째인가인가?
--------------------------------------------------------------------------
재귀함수를 배울 때 가장 많이 사용되는 예시가 피보나치 수열이다. 이 문제는 특정 피보나치 수를 구하는 것이 아니라 일정 조건을 만족하는 피보나치 수를 찾는 문제이기 때문에 재귀함수 보다는 반복문이 더 적절한 것으로 판단되었다.
계속 얘기하지만 파이썬이 큰 숫자도 간단히 다룰 수 있게 구현되어 있기 때문에, 까다롭지 않게 해결 가능했다.