Fibonacci Sequence   피보나치 수열

(2023-10-04)

Fibonacci Numbers, 피보나치 수


1. 피보나치 수열

  ㅇ 연속한 두 수의 합이 그 다음 수가 되는 수열
     -  {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... } 

  ㅇ 표현식 : 재귀적으로 표현 가능              ☞ 점화식 참조
     -  Fn = Fn-1 + Fn-2  또는  Fn+1 = Fn + Fn-1
        . 단, F0 = 0, F1 = 1

  ㅇ 특징
     - 커지는 속도가 거의 2n(지수시간)으로 커짐 : Fn ≒ 20.694n


2. 피보나치 수열을 구하는 알고리즘 例)

  ㅇ (재귀수학적 정의 그 자체를 그대로 구현한 비 효율적인 방법)
      
function fib(n)
    if (n < 1) return 0 
    else if (n == 1) return 1 
    return fib(n-1) + fib(n-2)

수열
   1. 수열   2. 수열 용어   3. 수열 종류   4. 점화식   5. 피보나치 수열   6. 하노이의 탑  


Copyrightⓒ written by 차재복 (Cha Jae Bok)       기술용어해설후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"