Fibonacci Sequence   피보나치 수열

(2021-05-15)

Fibonacci Numbers, 피보나치 수


1. 피보나치 수열

  ㅇ 연속한 두 수의 합이 그 다음 수가 되는 수열
     -  {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 = 0
        return 0
    if n = 1
        return 1
    return fib(n-1) + fib(n-2)



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