피보나치 수열 알고리즘


피보나치 수열이란 앞의 2수를 더한 수가 그다음 숫자가 되고 다시 2수를 더하것이 그다음 숫자게 되게 반복되는 숫자들입니다. 피보나치 공식을 보면 쉽게 이해 할 수 있습니다. 알고리즘 문제나 면접문제로 자주 나오니 외워두면 괜찮습니다. 일단 재귀함수로 피보나치를 구현하는 것이 편리합니다. 재귀 함수 없이도 구현이 가능하지만 조금 번거러울 수 있습니다.

피보나치 수열 공식


f(1) = f(2) = 1

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


피보나치 수열 C++ 소스


#include <iostream.h>


int fib(int n);
int main(int argc, char* argv[])
{
 int input;
 cout << "입력 : ";
 cin >> input;

 for(int i=1; i<=input; i++)
 {
  cout << fib(i) << "  ";
 }
  cout << "\n";
}
 
int fib(int n)
{
 if(n == 1 || n == 2)
  return 1;
 else
  return fib(n-1) + fib(n-2);
}


실행 예 : 5를 입력하면 1 1 2 3 5 의 출력값이 나옵니다.

신고
  1. Favicon of http://lalawin.com BlogIcon 라라윈비밀방문자
    2011.03.25 02:37 신고 edit/del reply

    다빈치 코드에 등장했던.. 그 수열이.. +_+

  2. Favicon of http://minimonk.tistory.com BlogIcon 구차니비밀방문자
    2011.03.27 15:43 신고 edit/del reply

    재귀(recursive)형 반복형(iterative)가 또다시 머리에서
    둥둥둥 떠다니게 하는 글이군요 ㅎ


    그러고 보니 프린지(fringe) 에서도 피보나치 수열나와요!

  3. Favicon of http://captainzone.tistory.com BlogIcon Derek.J비밀방문자
    2012.06.17 18:56 신고 edit/del reply

    하하 재미있네요. 피보나치 수열의 코드를 오랫만에 보게 되네요.