C++ 程序使用矩阵指数计算斐波那契数

2024 年 8 月 29 日 | 阅读 3 分钟

在本文中，我们将讨论一个使用矩阵查找斐波那契数的 C++ 程序。

通过矩阵幂运算查找斐波那契数是一种重要技术，它利用矩阵的强大功能有效地计算斐波那契序列。与典型的递归或迭代方法相比，当处理巨大的斐波那契数时，此策略非常有利，因为它大大减少了时间复杂度。

斐波那契数

斐波那契序列是一系列数字，其中每个数字都是其前两个数字的总和。该序列从 0 和 1 开始，并按以下顺序进行：0、1、1、2、3、5、8、13、21 等。斐波那契序列在数学上定义如下

fib(0)=0, fib(1)=1

fib(n)=fib(n-1)+fib(n-2)，其中 n>1

矩阵幂运算方法

矩阵幂运算方法通过结合矩阵乘法和幂运算有效地查找斐波那契数。我们无需重复计算斐波那契数，而是可以使用矩阵方程来表达连续斐波那契数之间的关系。

算法

Begin
 Consider two two-dimensional arrays.
 Make a function and multiply the matrices
 Create a new function to determine the matrix's power.
 Create a function to calculate the Fibonacci number.
 multiplication (array1[2][2], array2[2][2])
 Consider four variables a,b,c and d:
 a = array1[0][0] * array2[0][0] + array1[0][1] * array2[1][0]
 b= array1[0][0] * array2[0][1] + array1[0][1] * array2[1][1]
 c = array1[1][0] * array2[0][0] + array1[1][1] * array2[1][0]
 d = array1[1][0] * array2[0][1] + array1[1][1] * array2[1][1]
 array1[0][0] = a 
 array1[0][1] = b 
 array1[1][0] = c 
 array1[1][1] = d
 Power(array1[2][2], taking integer num as input) if (num == 0 or num == 1) return; 
arr1 [2][2] = 1,1, 1,0 
power(array1, num / 2) 
multiply(array1, array1) 
if (num mod 2 not equal to 0) 
 multiply(array1, array2)
 fibonacci(num)
 array1[2][2] = {{1,1}, {1,0}}
 if num ==0
 return 0
 power(array1 num - 1) 
return array1[0][0]
End

示例

//A C++ program is used to find the value of fib(n), where fib(n) is defined as // Fib(n) = Fib(n-1) + Fib(n-2) + Fib(n-3), n >= 3
// Fib(0) = 0, Fib(1) = 1, Fib(2) = 1
#include<bits/stdc++.h>
using namespace std;
// A function for multiplying two matrices 
// arr[][] and brr[][]. The result of multiplication is returned to brr[][]
void multiplyMatrix(int arr[3][3], int brr[3][3])
{
	// reating an auxiliary multiplier to store multiplying matrix elements
	int mulx[3][3];
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			mulx[i][j] = 0;
			for (int k = 0; k < 3; k++)
				mulx[i][j] += arr[i][k]*brr[k][j];
		}
	}

	// array for storing the result
	for (int i=0; i<3; i++)
		for (int j=0; j<3; j++)
			arr[i][j] = mulx[i][j]; // matrix values are updated
}

// function to compute the power
int powerFun(int Fib[3][3], int num)
{
	int Mat[3][3] = {{1,1,0}, {1,0,0}, {0,1,0}};

	// declaring the initial values and then multiplying them
	if (num==1)
		return Fib[0][0] + Fib[0][1];

	powerFun(Fib, num/2);

	multiplyMatrix(Fib, Fib);

	if (num%2 != 0)
		multiplyMatrix(Fib, Mat);

	//declaring the initial values and then multiplying them
	return Fib[0][0] + Fib[0][1] ;
}

// Return the term of a sequence defined by the recurrence relation shown below.
// fib(n) has been defined as 
// fib(num) = fib(num-1) + fib(num-2) + fib(num-3), num>=3
// fib(0) = 0, fib(1) = 1, fib(2) = 1
int findNthTermis(int num)
{

	int Fib[3][3] = {{1,1,0}, {1,0,0}, {0,1,0}} ;
 
 //base conditions
	if(num==0)
		return 0;
	if(num==1 || num==2)
		return 1;

	return powerFun(Fib, num-2);
}

// Driver code
int main()
{
int num = 7;

cout << "Fib(7) is " << findNthTermis(num);

return 0;
}

输出

Fib(7) is 13

复杂度

时间复杂度： O(logN)

辅助空间： O(logN)

下一主题C++ 程序：使用矩阵乘法执行消息编码

C++ 程序使用矩阵指数计算斐波那契数

斐波那契数

矩阵幂运算方法

示例

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 程序使用矩阵指数计算斐波那契数

斐波那契数

矩阵幂运算方法

示例

相关帖子

使用 Kruskal 算法的最小生成树（C++）

C++ 对象创建

C++ std::adjacent_difference

C++ unordered_multimap max_load_factor() 函数

C++ ios::rdstate() 函数

C++ iota()

C++ 转换运算符

C++ 二叉堆

C++ 程序为从单链表中选择随机节点

不同的 C++ 编译器

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器