Daily Algorithm - Day 24

$1000$-digit Fibonacci Number

The Fibonacci sequence is defined by the recurrence relation:
$F_n = F_{n - 1} + F_{n - 2}$, where $F_1=1$ and $F_2=1$.
Hence the first $12$ terms will be:

$F_1 = 1\\ F_2 = 1\\ F_3 = 2\\ F_4 = 3\\ F_5 = 5\\ F_6 = 8\\ F_7 = 13\\ F_8 = 21\\ F_9 = 34\\ F_{10} = 55\\ F_{11} = 89\\ F_{12} = 144$

The $12$th term, $F_{12}$, is the first term to contain three digits.
What is the index of the first term in the Fibonacci sequence to contain $1000$ digits?

피보나치 수열에서 처음으로 1000자리가 되는 것은 몇 항인지 구하는 문제이다.
내가 생각한 구현 방식은 다음과 같다.

1. 피보나치 수열의 n번째 항을 구해서 string으로 출력해주는 함수를 작성.
2. 피보나치 수열의 length가 1000 이상이 될때까지 반복문을 거친다.

간단하니 한번에 작성해보자.

//Python

# 피보나치 수열 n번째 항을 string으로 변환해 출력
def fibonacci(n):
    if n == 1:
        return '1'
    elif n == 2:
        return '1'
    elif n > 2 and n % 1 == 0:
        x, y = 1, 1
        for i in range (3, n + 1):
            x, y = y, x + y
        return str(y)
    else:
        return "out of range"

# 자릿수가 n자리가 되는 피보나치 수열의 첫 항을 출력
def solution(n):
    i = 0
    while len(fibonacci(i)) < n:
        i += 1
    return i

print(solution(1000))

>>> 4782   # correct

오늘은 여기까지.
-2025.01.14-