피보나치(Fibonacci) 수를 구하는 방법

다음은 재귀 호출을 이용해 피보나치 수를 구하는 소스 코드입니다.

int compute_fibonacci_number(int n)
{
	if (n == 0)
		return 0;
	if (n == 1)
		return 1;
	return compute_fibonacci_number(n - 1) + compute_fibonacci_number(n - 2);
}

다음은 위의 소스 코드를 동적 계획법의 한 방법인 memoization을 이용해 더 빠르게 개선한 소스 코드입니다.

int compute_fibonacci_number(int n)
{
	if (n == 0)
		return 0;
	if (n == 1)
		return 1;

	static const int maximum_fibonacci_number_count = 10000;
	static int fibonacci_numbers[maximum_fibonacci_number_count];
	if (fibonacci_numbers[n] > 0)
		return fibonacci_numbers[n];
	fibonacci_numbers[n] = compute_fibonacci_number(n - 1) + compute_fibonacci_number(n - 2);
	return fibonacci_numbers[n];
}

다음은 반복문을 이용해 피보나치 수를 구하는 C++ 소스 코드입니다.

int compute_fibonacci_number(int n)
{
	if (n == 0)
		return 0;
	if (n == 1)
		return 1;

	int previous_fibonacci_number = 0;
	int current_fibonacci_number = 1;
	for (int i = 2; i <= n; ++n)
	{
		int temporary = current_fibonacci_number;
		current_fibonacci_number += previous_fibonacci_number;
		previous_fibonacci_number = temporary;
	}
	return current_fibonacci_number;
}

참고:

Advertisements

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중