본문 바로가기
개발언어/C++

[피보나치 수열 소스] 피보나치 수열 알고리즘 C++ 소스

by 엔돌슨 2011. 3. 23.
반응형

피보나치 수열 알고리즘


피보나치 수열이란 앞의 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 의 출력값이 나옵니다.