使用矩阵指数查找斐波那契数的 C++ 程序
c++server side programmingprogramming
斐波那契数，通常表示为 Fn，形成一个序列，称为斐波那契数列，即每个数字都是前两个数字的总和，从 0 和 1 开始。即 −
F0 = 0 和 F1 = 1 并且 Fn = Fn-1 + Fn-2 对于 n > 1。
算法
Begin
取两个二维数组
创建一个函数并执行矩阵乘法
创建另一个函数来找出矩阵的幂
创建一个函数然后找出斐波那契数
乘法(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] = a
arr1[0][1] = b
arr1[1][0] = c
arr1[1][1] = d
Power(arr1[2][2], 以整数 n 作为输入)
if (n == 0 或 n == 1)
return;
arr1 [2][2] = {{1,1}, {1,0}}
power(arr1, n / 2)
multiply(arr1, arr1)
if (n mod 2 不等于 0)
multiply(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 <iostream>
using namespace std;
void multiply(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];
int d = F[1][0] * M[0][1] + F[1][1] * M[1][1];
F[0][0] = a;
F[0][1] = b;
F[1][0] = c;
F[1][1] = d;
}
void power(int F[2][2], int n) {
if (n == 0 || n == 1)
return;
int M[2][2] = {{1,1},{1,0}};
power(F, n / 2);
multiply(F, F);
if (n % 2 != 0)
multiply(F, M);
}
int fibonacci_matrix(int n) {
int F[2][2] = {{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n - 1);
return F[0][0];
}
int main() {
int n;
while (1) {
cout<<"输入整数 n 来查找第 n 个斐波那契数。(输入 0 退出):";
cin>>n;
if (n == 0)
break;
cout<<fibonacci_matrix(n)<<endl;
}
return 0;
}
输出
输入整数 n 来查找第 n 个斐波那契数。(输入 0 退出): 2 1 输入整数 n 来查找第 n 个斐波那契数。(输入 0 退出): 6 8 输入整数 n 来查找第 n 个斐波那契数。(输入 0 退出): 7 13 输入整数 n 来查找第 n 个斐波那契数。(输入 0 退出): 0
