[알고리즘] 피보나치 수열

피보나치 수열이란?


  • 첫 달에는 새로 태어난 토끼 한 쌍만이 존재한다.
  • 두 달 이상이 된 토끼는 번식 가능하다.
  • 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다.
  • 토끼는 죽지 않는다.

다음과 같은 조건이 있을 때, N개월 뒤에는 토끼가 얼마나 있을까?

1202년, 이탈리아의 수학자 레오나르도 피보나치가 토끼의 번식을 언급하면서 체계화 한 수열을 피보나치 수열이라고 한다. 

피보나치 수열의 점화식은 다음과 같다.

F0​=0, F1​=1, Fn+2​=Fn+1​+Fn

점화식이 다음과 같다면, 코드로 옮기는 것은 생각보다 쉽다. n = 0이라면 0을 리턴, n = 1인 경우 1을 리턴하고, 그 외의 경우에는 F(n-1)+F(n-2)를 리턴하면 된다.

코드


// 일반적인 재귀 함수 이용
int Fibonacci(int n)
{
    if(n <= 1return n;
    else return Fibonacci(n  1+ Fibonacci(n  2);
}
cs

// 반복문 이용
int FiboLoop(int n){
    int before = 0, cursor = 1, i, temp;
 
    if (n <= 1return n;
    else
    {
        for (i = 1; i < n; i++){
            temp = cursor;
            cursor = before + cursor;
            before = temp;
        }
        return cursor;
    }
}
 
cs

글쓴이: BakJH

Student of Daedeok SW Meister Highschool, in Korea.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중