피보나치 수열(Fibonacci Numbers)

피보나치 수열은 앞의 두 수를

더하며 나아가는 수열이다.

f(n)을 n번째 피보나치 수라고 한다면

f(n) = f(n-2) + f(n-1)

라는 식으로 표현가능하다.

※단, 피보나치 수열을 계산 하기 위해선, f(1) & f(2) (첫번째 & 두번째)는 주어져야 한다.

f(1) = 0

f(2) = 1

일때, 피보나치 수열은

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 84....

이 된다.

피보나치 수열의 대표적인 문제는 계단 문제다.

문제

계단을 한번에 1개 or 2개를 올라갈 수 있다.

n개의 계단을 올라 갈 수 있는 방법의 수는 몇 개인가?

해설

계단을 올라가는 방법은

계단을 마지막에 계단을 1개 올라가는 방법(주황색 선) 

계단을 마지막에 계단을 2개 올라가는 방법(파란색 선)

이 두 방식의 합이다.

f(n)방식으로 표현하면 아래와 같다.

f(n-1) : 마지막에 1개 올라가는 방법

f(n-2) : 마지막에 2개 올라가는 방법

즉, 

f(n) = f(n - 1) + f(n - 2)

(계단 n개를 올라가는 방법 = 마지막에 1개 올라가는 방법 + 마지막에 2개 올라가는 방법)

피보나치 수열이 성립한다는 것을 알 수 있다.

이제 f(1)과 f(2)만 구하면 된다.

계단 1개 : 1개(1개로 한번에)

계단 2개 : 2개(1개씩, 2개로 한번에)

계단 n개를 올라가는 방법은

1, 2, 3, 5, 8, 13, 21, 34, 55, 84....

이렇게 된다.

• 재귀함수 이용
  

int Algorithm::Fibonacci(int length)

{

       

        if (length < 1)

               return 0;

 

        if (length < 3)

               return 1;

 

        return Fibonacci(length - 2) + Fibonacci(length - 1);

}

• 반복문 이용

int Algorithm::Fibonacci(int length)

{

        int prev = 1;

        int now = 0;

        int sum = 0;

 

        for (int i = 0; i < length; i++)

        {

               sum = prev + now;

 

               prev = now;

               now = sum;

        }

       

        return sum;

}