프로 그래 밍 의 아름다움 2.9: 신기 한 피 보 나치 수열

재 귀 를 들 어 본 사람 이 라면 데이터 구 조 를 조금 배 운 사람 은 모두 이 수열 을 들 어 본 적 이 있다.사실 고등학교 2 학년 수학 시간 에 도 있 었 지만 그때 나 는 마르크스주의 의 영향 을 받 아 프로 그래 밍 이 무엇 인지 몰 랐 다.자, 이 수열 은 번식 능력 이 매우 놀 라 운 토끼 한 쌍 에서 기원 되 었 다 고 합 니 다.사실 이것 은 바로 전달 공식 이다.
F(n)=⎧⎩⎨01F(n−1)+F(n−2)n = 0;n = 1;n>=2
보통 학교 에 서 는 재 귀 할 때 이 를 예 로 들 면 좋 지.면접 문제 도 이 문 제 를 볼 수 있 고 페 이 스 북 은 한 번 기대 고 있 었 다.하지만 재 귀적 으로 쓰 면 다음 면접 을 볼 필요 가 없다.이 유 는 하나 야, 너무 느 려!!반복 계산 이 너무 많아!!
보 세 요. F (5) 를 요구 하면 F (4) 와 F (3) 를 계산 하고 F (4) 를 계산 해 야 합 니 다. F (3) 를 다시 계산 해 야 합 니 다. 물론 느 립 니 다.그리고 함수 호출 은 스 택 포인터, 전달 매개 변수 등 을 저장 해 야 합 니 다.
좀 좋 은 사람 은 1 차원 배열 을 생각 할 수도 있 습 니 다.이렇게 하면 복잡 도 를 낮 출 수 있다.
O (n) 됐어, 나 도 여기 서 추 태 를 보 였 어.나의 실현 을 써 라.
스크롤 배열

#include <stdio.h>
int arr[3]={0,1};
int main(void){
  int index=0;
  printf("Enter the index:
");
  scanf("%d",&index);
  if(index<=2){
    printf("%d
",arr[index-1]);
    return 0;
  }else{
    for(int i=3;i<=index;++i){
      arr[2]=arr[1]+arr[0];
      arr[0]=arr[1];
      arr[1]=arr[2];
    }
  }
  printf("%d
",arr[2]);
  return 0;
}

자, 이것 이 바로 전설의 복잡 도가 O (N) 인 방법 입 니 다. 예전 의 재 귀 보다 좋 습 니 다.면접 때 이 걸 쓰 는 것 도 평균 수준 에 이 를 뻔 했다.이론 적 으로 는 가능 하지만 다음 방법 도 있다.수열 을 구 하 는 통항 공식 이지 만 이 는 무리 수 를 도입 했다.그래서 사실은 안 돼.다음은 가장 난폭 하고 수준 있 는 방법 이다.복잡 도 는 O (Log2N) 에 도달 할 수 있다. 전략 은 당연히 내 가 베 낀 것 이다.행렬 을 쓰다.피 보 나치 가 2 단계 푸 시 수열 이기 때문에 행렬 에 걸 맞 은 공식 으로 얻 을 수 있다.2 ＊ 2 의 행렬 A 가 존재 한다.이로써 (FnFn - 1) = (Fn - 1Fn - 2) ∗ A 구 해 를 얻 을 수 있다.
A=(1110)
위 에서 내 놓 을 수 있 습 니 다:
(FnFn−1)=(Fn−1Fn−2)∗A=(Fn−2Fn−3)∗A2=....=(F1F0)An−1
봤 어, 지금 은 구 할 수 있 기만 하면 돼.
An - 1, 그리고 행렬 곱셈 을 하면 됩 니 다.
그래서 우리 가 해 야 할 일 은 행렬 작업 의 클래스 나 함 수 를 실현 하 는 것 이다.OK, 나 는 B 를 담 고 간단 한 실현 을 쓰 고 있다.

#include <iostream>
#include <cassert>
using namespace std;
const int N=4;
class Martix{
public:
  unsigned int size;
  long long int data[N*N];
};
//Multi bewteen martix and martix
Martix  martixMulti(const Martix A,const Martix B,Martix result){
  assert(A.size==B.size);
  result.size=A.size;
  for(int i=0;i<result.size;++i)
    for(int j=0;j<result.size;++j){
      result.data[i*result.size+j]=0;
      for(int k=0;k<result.size;++k)
    result.data[i*result.size+j]+=A.data[i*A.size+k]*B.data[k*B.size+j];
    }
  return result;
}
//Compute the n-1 of exp
Martix martixPow(Martix &A,int index){
  if(index==0)
    exit(0);
  --index; //compute n-1 exp
  Martix IdenMartix;
  IdenMartix.size=2;
  IdenMartix.data[0]=1,IdenMartix.data[1]=0;
  IdenMartix.data[2]=0,IdenMartix.data[3]=1;
  Martix result=IdenMartix;
  for(;index;index>>=1){
    if(index&1)
      result=martixMulti(result,A,result);
    A=martixMulti(A,A,A);
  }
  return result;
}
int Fib(int n){
  Martix A;
  A.size=2;
  A.data[0]=1,A.data[1]=1;
  A.data[2]=1,A.data[3]=0;
  Martix an=martixPow(A,n);
  return an.data[0];
}
int main(int agrc,char **argv){
  unsigned int index;
  cout<<"Input index:";cin>>index;
  cout<<Fib(index)<<endl;
  return 0;
}

상술 한 것 은 간단 한 실현 이지 만 코드 에 약간의 문제 가 있다.하, 너희들 스스로 알 아서 해라.다음 글 은 대수 계산 을 쓸 것 으로 추정 된다.마침 그 계약 수열 의 항수 가 너무 많 을 때 표시 할 수 없 는 상황 이 었 다.참고 자료: < 프로 그래 밍 의 아름다움 > 서적 프로 그래 밍 의 아름다움 2.9