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

相关文章