ps:피보나치_수
피보나치 수 (Fibonacci numbers)
- F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) 의 형태로 정의되는 수열. 초기 몇 항의 값은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … 이다
- 여러가지 DP 문제들의 답이 피보나치 수가 되는 경우도 많고, 또한 수열 자체에도 여러가지 성질들이 많아서 그것들에 관한 문제도 많이 나온다. ko:피보나치 수 참고
- n번째 피보나치 수을 계산할때에는, 비네 공식이라고 불리는 일반항 공식을 통해서 계산하는 것은 실수오차때문에 사용하기 힘들다. 동차 선형 점화식을 푸는 방법대로 행렬의 거듭제곱을 이용해서 O(logn)에 풀수 있다. 이 방법을 좀더 정리해서 얻은 아래 점화식을 이용해서 마찬가지로 O(logn)에 풀 수도 있다.
- $$ F_{2k}=F_k(2F_{k+1}−F_k) \\ F_{2k+1} = F^2_{k+1} + F^2_{k} $$
- 구현은 teflib.combinatorics.fibonacci 을 참고.
- 피사노 주기(pisano period)를 이용하면 F(n) % mod 를 구하는 것을, mod에 대한 피사노 주기 π(mod)를 구한 다음에 F(n%π(mod))%mod 로 계산할 수 있다.
- 다만 π(mod)를 구하는 것이 보통은 쉽지 않다. mod가 2^x*5^y 형태라면 다음을 이용해서 그나마 계산이 가능하다.
- m,n이 서로소라면 π(mn) = LCM(π(m), π(n))
- n = 2^k 라면 π(n) = 3n/2
- n = 5^k 라면 π(n) = 4n
- 그리고 O(logn)이 O(log(π(mod)))로 줄어들긴 하지만, O(logn)도 어지간히 큰 n에 대해서 매우 빠르게 계산해주기 때문에 굳이 꼭 필요한 경우는 거의 없다.
관련된 성질 / 정리
급수 공식
- 위키피디아 참고
- 합: $ {\displaystyle \sum _{k=0}^{n}F_{k}=F_{n+2}-1} $
- 교대합: $ {\displaystyle \sum _{k=0}^{n}(-1)^{k+1}F_{k}=(-1)^{n+1}F_{n-1}+1} $
- 제곱합: $ {\displaystyle \sum _{k=0}^{n}F_{k}^{2}=F_{n}F_{n+1}} $
- 관련 문제: 피보나치 수의 제곱의 합
- 홀수항의 합: $ {\displaystyle \sum _{k=1}^{n}F_{2k-1}=F_{2n}} $
- 짝수항의 합: $ {\displaystyle \sum _{k=0}^{n}F_{2k}=F_{2n+1}-1} $
- 위키 링크에는 이 외에도 좀더 다양한 공식들이 적혀있다
- 위키에는 증명은 생략되어있지만 어렵지 않다. 나무위키에서도 찾을수 있다.
피보나치 수의 최대공약수
- i번째 피보나치수와 j번째 피보나치수의 최대공약수는 gcd(i,j)번째 피보나치수이다
- gcd(F(i),F(j)) = F(gcd(i,j))
- 관련 문제 : 피보나치 수와 최대공약수
Zeckendorf's theorem
- 증명이나 자세한 내용은 https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem 참고. 아래는 요약.
- 임의의 자연수를 1개 이상의 distinct하고 연속되지 않은 피보나치 수의 합으로 표현할수 있고, 이 표현은 유일하게 존재한다
- 이렇게 표현한 것을 Zeckendorf representation이라고 부르고, 이것을 바이너리 형태로 표현한것 (n번째 자리수가 n-th 피보나치 수에 해당) 을 Fibonacci coding 이라고 한다.
- Zeckendorf representation을 찾는 것은 그리디 알고리즘으로 해결 가능
- 관련 문제: Fibonacci Representation
- Zeckendorf representation은 게임 이론 (Game theory) 에서 Fibonacci Nim 게임의 필승 전략을 구하는 데에도 사용된다.
- 관련 문제: Fibonacci Game, 수학 게임
ps/피보나치_수.txt · 마지막으로 수정됨: 2023/06/15 14:41 저자 teferi
토론