일반적으로 Fn으로 표시되는 피보나치 수는 피보나치 수열, 즉, 피보나치 수열이라고 하는 수열을 형성합니다. 각 숫자는 0과 1에서 시작하는 앞의 두 숫자의 합입니다. 즉 -
F0 =0 및 F1 =1AndFn =Fn-1 + Fn-2 n> 1에 대해.
알고리즘
시작 두 개의 2차원 배열 취하기 함수 생성 및 행렬 곱셈 수행 행렬의 거듭제곱을 구하는 다른 함수 생성 후 피보나치 수를 구하는 함수 생성 Multiply(arr1[2][2], arr2[2][ 2]) 4개의 변수 a, b, c, d를 취합니다. a =arr1[0][0] * arr2[0][0] + arr1[0][1] * arr2[1][0] b=arr1[0 ][0] * arr2[0][1] + arr1[0][1] * arr2[1][1] c =arr1[1][0] * arr2[0][0] + arr1[1] [1] * arr2[1][0] d =arr1[1][0] * arr2[0][1] + arr1[1][1] * arr2[1][1] arr1[0][0 ] =arr1[0][1] =b arr1[1][0] =c arr1[1][1] =d Power(arr1[2][2], 정수 n을 입력으로 사용) if (n ==0 또는 n ==1) 반환; arr1 [2][2] ={{1,1}, {1,0}} power(arr1, n / 2) 곱하기(arr1, arr1) if (n mod 2가 0이 아님) 곱하기(arr1, arr2 ) fibonacci_matrix(n) arr1[2][2] ={{1,1}, {1,0}} if n ==0 return 0 power(arr1 n - 1) return arr1[0][0]End 예시 코드
#include 네임스페이스 std;void 곱하기(int F[2][2], int M[2][2]) { int a =F[0][0] * M[0][ 0] + F[0][1] * M[1][0]; int b=F[0][0] * M[0][1] + F[0][1] * M[1][1]; int c =F[1][0] * M[0][0] + F[1][1] * M[1][0]; 정수 d =F[1][0] * M[0][1] + F[1][1] * M[1][1]; F[0][0] =에이; F[0][1] =b; F[1][0] =c; F[1][1] =d;} 무효 전력(int F[2][2], int n) { if (n ==0 || n ==1) return; 정수 M[2][2] ={{1,1},{1,0}}; 전력(F, n/2); 곱하기(F, F); if (n % 2 !=0) 곱하기(F, M);}int fibonacci_matrix(int n) { int F[2][2] ={{1,1},{1,0}}; if (n ==0) 반환 0; 전력(F, n - 1); 반환 F[0][0];}int main() { int n; while (1) { cout<<"n번째 피보나치 번호를 찾으려면 정수 n을 입력하십시오. (종료하려면 0을 입력하십시오):"; 신>>n; if (n ==0) 중단; cout<<피보나치_행렬(n)< 출력
n번째 피보나치 수를 찾으려면 정수 n을 입력합니다. (종료하려면 0 입력):21n번째 피보나치 수를 찾으려면 정수 n을 입력합니다. (종료하려면 0 입력):68n번째 피보나치 수를 찾으려면 정수 n을 입력합니다. (종료하려면 0 입력):713n번째 피보나치 수를 찾으려면 정수 n을 입력하세요. (종료하려면 0 입력):0