使用矩阵指数查找斐波那契数的 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