\(n\)번째 피보나치 수를 \(f(n)\) 이라고 했을 때, 이를 구하는 점화식은 \(f(n) = f(n-1) + f(n-2)\)입니다. (\(f(1) = f(2) = 1\)
\(n-1\)번째 피보나치 수는 \(f(n-1) = f(n-2) + f(n-3)\) 이고요
그럼 이것을 행렬로 나타낼 수 있습니다.
\[\begin{pmatrix} f(n) \\ f(n-1) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f(n-1) \\ f(n-2) \end{pmatrix} \]
\[\begin{pmatrix} f(n-1) \\ f(n-2) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f(n-2) \\ f(n-3) \end{pmatrix} \]
\[\begin{pmatrix} f(n) \\ f(n-1) \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} ^{2} \begin{pmatrix} f(n-2) \\ f(n-3) \end{pmatrix}\]
그럼, 앞의 행렬을 적절히 제곱을 한 다음에, 뒤의 행렬에 \(f(2)\)와 \(f(1)\)를 넣어주면 \(f(n)\)의 값을 빠르게 구할 수 있습니다.
yukariko 2년 전
식을 정리해본결과 a~b 항의 합은
f(b+2) - f( a +1) 항으로 구할수있다는것 까진 알아냈는데
저 범위를 충당할 방법이 떠오르질 않네요..
피보나치의 일반항을 이용해서 double형 + great pow로 해결해보려했지만 이것도 힘든것같고..
어떻게 해야할까요?