테페리넷

사용자 도구

사이트 도구

현재 위치: 테페리넷 » Problem Solving » 피보나치 수 (Fibonacci numbers)
ps:피보나치_수

목차

피보나치 수 (Fibonacci numbers)

n번째 피보나치 수를 구하기

  • 비네의 공식(Binet's formula) 이라고 불리는 클로즈드 폼으로 된 일반항 공식이 있기는 하지만, 이 공식을 이용해서 계산하는 것은 실수오차때문에 사용하기 힘들다.
  • 피보나치 수의 점화식도 동차 선형 점화식이므로, 행렬의 거듭제곱을 이용해서 O(logn)에 푸는 것이 효율적인 방법이다.
  • 행렬 거듭제곱 형태를 좀 더 정리하면, 아래 점화식을 얻을 수 있고 이것을 이용해서 풀 수도 있다. 시간복잡도는 역시 O(logn)이지만, 계산이 살짝 더 최적화된다.
    • $$ F_{2k}=F_k(2F_{k+1}−F_k) \\ F_{2k+1} = F^2_{k+1} + F^2_{k} $$
      • 이 식은, 다음의 도가뉴 항등식(d'Ocagne's identity) 으로부터도 쉽게 유도된다
        • $ F_{m+n}=F_{m-1}F_{n}+F_{m}F_{n+1} $
    • 구현은 teflib.combinatorics.fibonacci 을 참고.
  • 관련 문제

m=2^x*5^y 일때, F(n) % m 을 구하기

  • 피사노 주기(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
  • 이렇게 피사노 주기를 이용하면, n번째 피보나치수 대신에, n%π(mod) 번째 피보나치수를 구하면 되므로, 시간복잡도가 O(logn)에서 O(log(π(mod)))로 줄어들기는 한다. 하지만, 그냥 O(logn)으로 구하더라도 어지간히 큰 n에 대해서도 매우 빠르게 계산해주기 때문에 굳이 꼭 필요한 경우는 거의 없다.
  • 관련 문제

관련된 성질 / 정리

  • 피보나치 수열의 급수와 변형된 급수들은 대부분 더 큰 피보나치수를 이용해서 표현이 가능하다
    • k번 항까지의 합, 교대합, 홀수항의 합 등등은 다 피보나치 수로 변환되고, 따라서 O(logn)에 계산 가능하다
  • 피보나치 수들의 최대공약수도 피보나치수로 표현된다. 두 피보나치 수의 서로소 여부도 쉽게 알수 있다

급수 공식

  • 위키피디아 참고
  • 합: $ {\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))
    • 여기서 피보나치 수를 세는 것은 1에서 부터 시작한다. 1,2,3,4번째 피보나치 수는 1,1,2,3 이다
  • 증명은 https://mono-cake.coffee/2019-08-02-GCD-of-fibonacci/ 참고
  • 파생되는 유용한 성질들
    • i번째 피보나치수와 j번째 피보나치수가 서로소가 되려면, gcd(i,j)가 1 또는 2이면 된다
    • nk번째 피보나치수는 n번째 피보나치수의 배수이다.
  • 관련 문제

Zeckendorf's theorem

  • 증명이나 자세한 내용은 https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem 참고. 아래는 요약.
  • 임의의 자연수를 1개 이상의 distinct하고 연속되지 않은 피보나치 수의 합으로 표현할수 있고, 이 표현은 유일하게 존재한다
    • 이렇게 표현한 것을 Zeckendorf representation이라고 부르고, 이것을 바이너리 형태로 표현한것 (n번째 자리수가 n-th 피보나치 수에 해당) 을 Fibonacci coding 이라고 한다.
  • Zeckendorf representation을 찾는 것은 그리디 알고리즘으로 해결 가능
  • Zeckendorf representation은 게임 이론 (Game theory) 에서 Fibonacci Nim 게임의 필승 전략을 구하는 데에도 사용된다.

토론

댓글을 입력하세요:
J L V I N
 
ps/피보나치_수.txt · 마지막으로 수정됨: 2024/04/09 14:55 저자 teferi