피보나치 수열 알고리즘
피보나치 수열이란 앞의 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 의 출력값이 나옵니다.
다빈치 코드에 등장했던.. 그 수열이.. +_+
답글
네 수열계산하는 알고리즘을 코드로 구현한거에요. 이런 알고리즘 시험이 가끔 나와서 정리해봤어요
재귀(recursive)형 반복형(iterative)가 또다시 머리에서
둥둥둥 떠다니게 하는 글이군요 ㅎ
그러고 보니 프린지(fringe) 에서도 피보나치 수열나와요!
답글
하하 재미있네요. 피보나치 수열의 코드를 오랫만에 보게 되네요.
답글
D이거 오류뜨는데요?
답글