C++ 피보나치 수열 여러 구현 방법 (Fibonacci C++ )

Fibonacci

 

/* 피보나치수열 구현방법 종류 - 2020/01/01 xtar.tistory */
#include <iostream>
#include <stack>
using namespace std;

// 상수
const double pi = (1 + sqrt(5)) / 2;

//일반적인 재귀호출 피보나치
int Recursion_FIB(int n)
{
	if (n <= 1)
		return n;
	return Recursion_FIB(n - 1) + Recursion_FIB(n - 2);
}
//스택을 이용
int Stack_FIB(int n)
{
	int sum = 0;
	stack<int> _stack;
	_stack.push(n);
	int a = 0;
	while (!_stack.empty())
	{
		a = _stack.top();
		_stack.pop();
		if (a == 1)
			sum += 1;
		else
		{
			if (a != 0)
			{
				_stack.push(a - 1);
				_stack.push(a - 2);
			}
		}
	}
	return sum;
}
//동적프로그래밍 사용한 피보나치(점화식 도출)
int Dynamic_FIB(int n)
{
	int *arr = new int[n + 1];

	arr[0] = 0;
	arr[1] = 1;

	for (int i = 2; i <= n; i++)
	{
		arr[i] = arr[i - 1] + arr[i - 2];
	}
	return arr[n];
}
// 피보나치 공식사용
int Formula_FIB(int n)
{
	return round(pow(pi, n) / sqrt(5));
}

int main()
{
	int n = 0;
	cin >> n;
	cout << " " << Recursion_FIB(n) << " " << Stack_FIB(n) << " " << Dynamic_FIB(n)<<" "<<Formula_FIB(n);
	return 0;
}