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

2011. 3. 23. 09:38 개발언어/C++

피보나치 수열 알고리즘

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