매일 알고리즘 시리즈 (19) (n 을 입력 하고 가장 빠 른 방법 으로 이 수열 의 n 항 을 구하 십시오)

제목:
정의 Fibonacci 수열 은 다음 과 같 습 니 다: f (n)  = 0 (n=0) f(n)  = 1 (n=1, 2) f(n)  =  f(n-1)+f(n-2)  (n > 2) n 을 입력 하고 가장 빠 른 방법 으로 이 수열 의 n 항 을 구하 십시오.
사고방식 1:
나 는 많은 프로그래머 들 이 이 문 제 를 보면 재 귀적 인 방법 으로 이 문 제 를 풀 생각 을 하기 쉽다 고 믿는다. 그러나 너 는 이것 이 결코 가장 빠 른 방법 이 아니 라 는 것 을 알 고 있다.또 다른 방법 은 하나의 For (While) 순환 으로 이 문 제 를 풀 수 있 고 시간 복잡 도 는 O (n) 로 재 귀 하 는 방법 보다 좋 으 며 다음 에 이 두 가지 방법의 코드 를 먼저 제시 하 는 것 이다.
 
코드 는 다음 과 같 습 니 다:

/*------------------------------------
  Fibonacci    N  .
Copyright by yuucyf.		2011.07.22
-------------------------------------*/
long long FibNItemValue(int i32NItem)
{
	if (i32NItem <= 0)	return 0;
	if (i32NItem >= 1 && i32NItem <= 2)	return 1;

	return FibNItemValue(i32NItem - 1) + FibNItemValue(i32NItem - 2);
}


long long FibNItemValue_2(int i32NItem)
{
	long long int llFirst = 1, llSecond = 1, llNItemValue = 0;
	if (i32NItem <= 0)	return 0;
	if (i32NItem >= 1 && i32NItem <= 2)	return 1;

	for (int i32I = 3; i32I <= i32NItem; i32I++)
	{
		llNItemValue = llFirst + llSecond;
		llFirst = llSecond;
		llSecond = llNItemValue;
	}

	return llNItemValue;
}


int _tmain(int argc, _TCHAR* argv[])
{
	_tprintf(_T("N item value is %u.
"), FibNItemValue(40));

	return 0;
}

사고방식 2:
상기 두 가지 방법 은 모두 이 문 제 를 풀 수 있 지만 가장 빠 른 것 이 아니다. 다음은 시간 복잡 도가 O (logn) 인 방법 을 소개 한다. 이런 방법 을 소개 하기 전에 수학 공식 을 소개 한다.
{ f(n),  f(n-1), f(n-1),  f(n-2) }  = {1, 1, 1, 0}n-1
(알림: {f (n + 1), f (n), f (n), f (n - 1)} 은 행렬 을 표시 합 니 다. 행렬 에서 첫 번 째 줄 의 첫 번 째 열 은 f (n + 1) 이 고 첫 번 째 줄 의 두 번 째 열 은 f (n) 이 며 두 번 째 줄 의 첫 번 째 열 은 f (n - 1) 입 니 다.)
이 공식 이 있 으 면 f (n) 의 값 을 원 합 니 다. 우 리 는 행렬 {1 만 구 해 야 합 니 다. 1,  1, 0} 의 n - 1 차방, 행렬 {1,  1,  1, 0} 의 n - 1 차방 결과 의 첫 줄 첫 번 째 열 은 f (n) 입 니 다.이 수학 공식 은 수학 귀납법 으로 증명 하기 어렵 지 않 으 니 관심 있 는 친 구 는 스스로 증명 해 보 는 것 도 좋다.현재 문 제 는 행렬 {1 로 바 뀌 었 습 니 다. 1,  1,  0} 의 곱셈 은 간단하게 0 부터 순환 하면 n 제곱 은 n 차 연산 이 필요 하 며 앞의 방법 보다 빠 르 지 않 습 니 다.그러나 우 리 는 곱셈 의 다음 과 같은 성질 을 고려 할 수 있다.
        /  an/2*an/2                      짝수        \  a(n-1)/2*a(n-1)/2            홀수
n 제곱 을 요구 하면 우 리 는 먼저 n / 2 제곱 을 구하 고 n / 2 의 결 과 를 제곱 한다. 만약 에 n 제곱 을 구 하 는 문 제 를 큰 문제 로 보면 n / 2 를 구 하 는 것 을 작은 문제 로 본다.이런 큰 문 제 를 하나 또는 여러 개의 작은 문제 로 분해 하 는 사고방식 을 우 리 는 그것 을 분 치 법 이 라 고 부른다.이렇게 n 제곱 을 구하 면 logn 차 연산 만 필요 합 니 다.
이런 방식 을 실현 하려 면 먼저 2 를 정의 해 야 한다.×2 의 행렬, 그리고 행렬 의 곱셈 과 곱셈 연산 을 정의 합 니 다.이 연산 들 이 정 의 된 후에 남 은 일 은 매우 간단 해 졌 다.
 

#include "stdafx.h"
#include <assert.h>

/*------------------------------------
  Fibonacci    N  .
Copyright by yuucyf.		2011.07.22
-------------------------------------*/
///////////////////////////////////////////////////////////////////////
// A 2 by 2 matrix
///////////////////////////////////////////////////////////////////////
typedef struct tagMatrix2By2
{
      tagMatrix2By2(long long m00 = 0, long long m01 = 0, long long m10 = 0, long long m11 = 0)
      :m_00(m00), m_01(m01), m_10(m10), m_11(m11) 
      {}

      long long m_00;
      long long m_01;
      long long m_10;
      long long m_11;
}S_Matrix2By2;



///////////////////////////////////////////////////////////////////////
// Multiply two matrices
// Input: sMatrix1 - the first matrix
//        sMatrix2 - the second matrix
//Output: the production of two matrices
///////////////////////////////////////////////////////////////////////
S_Matrix2By2 MatrixMultiply(const S_Matrix2By2& sMatrix1, const S_Matrix2By2& sMatrix2)
{
      return S_Matrix2By2(
            sMatrix1.m_00 * sMatrix2.m_00 + sMatrix1.m_01 * sMatrix2.m_10,
            sMatrix1.m_00 * sMatrix2.m_01 + sMatrix1.m_01 * sMatrix2.m_11,
            sMatrix1.m_10 * sMatrix2.m_00 + sMatrix1.m_11 * sMatrix2.m_10,
            sMatrix1.m_10 * sMatrix2.m_01 + sMatrix1.m_11 * sMatrix2.m_11);
}

///////////////////////////////////////////////////////////////////////
// The nth power of matrix 
// 1  1
// 1  0
///////////////////////////////////////////////////////////////////////
S_Matrix2By2 MatrixPower(int i32N)
{
      assert(i32N > 0);

      S_Matrix2By2 sMatrix;
      if(i32N == 1)
	  {
            sMatrix = S_Matrix2By2(1, 1, 1, 0);
	  }
      else if(i32N % 2 == 0)
      {
            sMatrix = MatrixPower(i32N / 2);
            sMatrix = MatrixMultiply(sMatrix, sMatrix);
      }
      else if(i32N % 2 == 1)
      {
            sMatrix = MatrixPower((i32N - 1) / 2);
            sMatrix = MatrixMultiply(sMatrix, sMatrix);
            sMatrix = MatrixMultiply(sMatrix, S_Matrix2By2(1, 1, 1, 0));
      }

      return sMatrix;
}


long long FibNItemValue_3(int i32NItem)
{
      int aryRes[2] = {0, 1};
      if(i32NItem < 2)
            return aryRes[i32NItem];

      S_Matrix2By2 sPowerNMinus2 = MatrixPower(i32NItem - 1);
      return sPowerNMinus2.m_00;
}



int _tmain(int argc, _TCHAR* argv[])
{
	_tprintf(_T("N item value is %u.
"), FibNItemValue_3(50));

	return 0;
}