큰 숫자의 fibonacci 번호 찾기

Question

큰 피보나치 수의 모듈러스를 찾기 위해 다음 프로그램을 작성했습니다. 이것은 많은 수를 해결할 수 있지만 fibo_dynamic(509618737,4602,229176339)과 같은 경우에는 계산하지 못합니다. 여기서 a = 509618737, b = 4602 및 N = 229176339입니다. 이 일을하도록 도와주세요.

long long fibo_dynamic(long long x,long long y,long long n, long long a[]){ 
    if(a[n]!=-1){ 
     return a[n]; 
    }else{ 
     if(n==0){ 
      a[n]=x; 
      return x; 
     }else if(n==1){ 
      a[n]=y; 
      return y; 
     }else { 
      a[n]=fibo_dynamic(x,y,n-1,a)+fibo_dynamic(x,y,n-2,a); 
      return a[n]; 
     } 
    } 
} 

Answer 1

피보나치 수가 매우 빠르게 증가하기 때문에 값이 오버 플로우됩니다. 원래의 fibonacci 시리즈 (f(0) = 0 및 f(1) = 1)의 경우에도 f(90)의 값은 20 자릿수를 초과하여 C++의 기본 데이터 형식에 저장할 수 없습니다. (당신이 당신의 질문에 언급하기 때문에) 당신은 아마 다음과 같은 범위 내에서 값을 유지하는 계수 연산자를 사용한다 :

a[n] = (fibo_dynamic(x,y,n-1,a) + fibo_dynamic(x,y,n-2,a)) % MOD; 

그것은 모든 단계에서의 값은 mod에 안전하기 때문에 mod 연산자 다음 규칙이 있습니다

를

if a = b + c, then: 
a % n = ((b % n) + (c % n)) % n 

또한 재귀 버전을 사용하여 피보나치 수를 계산했습니다 (더 작은 하위 문제의 결과를 메모했지만). 이것은 추가 오버 헤드를 추가하는 많은 재귀 호출이 있음을 의미합니다. 가능한 경우 반복 버전을 사용하는 것이 좋습니다.

다음으로 변수 n을 사용하여 배열의 색인을 생성합니다. 그래서 배열 a의 크기는 최소한 n이라고 가정합니다. 질문에서 언급 한 n의 값은 매우 큽니다. 로컬 컴퓨터에서 이러한 큰 크기의 배열을 선언 할 수는 없습니다 (정수는 4 bytes이고 배열의 크기는 a은 약 874 MB).

마지막으로 프로그램의 복잡도는 O(n)입니다. O(log(n)) 시간에 n_th 피보나치 수를 계산하는 기술이 있습니다. 그것은 "행렬 지수를 사용하여 되풀이 관계를 해결하는 것"입니다.

f(n) = f(n-1) + f(n-2) for n >= 2 

이 기술을 이해하는 this 읽기 : 피보나치 수는 다음과 같은 선형 점화식을 따릅니다.