来啃硬骨头——费波纳茨(Fibonacci)矩阵快速幂 c++

简介: 全文线索:解题引出费波纳茨——>费波纳茨递归解法——>费波纳茨动态规划解法——>矩阵快速幂解法 一、来解题字符串只由'0'和'1'两种字符构成,当字符串长度为1时,所有可能的字符串为"0"、"1";当...

全文线索:

解题引出费波纳茨——>费波纳茨递归解法——>费波纳茨动态规划解法——>矩阵快速幂解法

 

一、来解题

字符串只由'0'和'1'两种字符构成,
当字符串长度为1时,所有可能的字符串为"0"、"1";
当字符串长度为2时,所有可能的字符串为"00"、"01"、"10"、"11";
当字符串长度为3时,所有可能的字符串为"000"、"001"、"010"、"011"、"100"、
"101"、"110"、"111"
...
如果某一个字符串中,只要是出现'0'的位置,左边就靠着'1',这样的字符串叫作达
标字符串。
给定一个正数N,返回所有长度为N的字符串中,达标字符串的数量。
比如,N=3,返回3,因为只有"101"、"110"、"111"达标。

 

思路:

对于位置 i,假定 i 前面是1,则 i 有两种情况

i=0 时,i+1位必为1,剩下的就是 f(i-2)

i=1 时,i+1位可以是1,也可以是0,因此剩下的是 f(i-1)

f(i)= f(i-2)+ f(i-1) 因此本题可以使用费波纳茨来解。

 

二、递归解费波纳茨

int process(int i, int n){
    if(i==n) return 1;
    if(i==n-1) return 2;
    return process(i+1, n) + process(i+2, n);
}

int getNum1(int n){
	if(n<1) return 0;
	return process(1,n);
}

int main(){
	int n=30;
	//普通费波纳茨
	int normal=getNum1(n);
	cout<<normal<<endl;
	return 0;
}

 

三、动态规划

int dp(int n){
	if(n<1) return 0;
	if(n==1) return 1;
	
	vector<int>num(n+1);
	num[1]=1;
	num[2]=2;
	//第2到第n位的值
	for(int i=3; i<n+1; i++)
		num[i]=num[i-1]+num[i-2];
	cout<<num[n]<<endl;
	return num[n];
}

int main(){
	int n=30;
	//动态规划
	int dynamic=dp(n);	
	return 0;
}

 

动态规划空间优化

int dp2(int n){
	if(n<1) return 0;
	if(n==1) return 1;

	int temp=0, cur=1, pre=1;
	for(int i=2; i<n+1; i++){
		temp=cur;
		cur+=pre;
		pre=temp;
	}
	return cur;
}

 

三、快速幂

铺垫

对于数列 f(n)=f(n-1)+f(n-2),被减数最大值为2,因此我们的矩阵是2阶的

数学公式输入不友好,直接上图吧

因此可以得到递推式——|f(n)-f(n-1)|=|f(2)-f(1)| * (n-2)次幂

a,b,c,d的值需要自行计算。亮点在于高次幂的计算,如何减少高次幂的乘积次数。

 

先来看看整数高次幂是如何做的

如何提高高次幂运算速度,比如10的75次幂。

第一步:将75拆成二进制,即1001011

第二步:两个辅助变量,t=10,res=1(用于res记录结果)

上伪代码:

int t=10, res=1;
vector<int>flag={1,0,0,1,0,1,1};
for(int i=0; i<flag.size(); i++){
    if(flag[i]==1)
        res*=t;
    t*=t;
}

只有二进制位为1的t才会与res进行相乘,时间复杂度为O(logN)

res为10的75次幂的计算结果。

 

矩阵的高次幂计算同理。

先将(n-2)转成二进制数。上代码:

void turn(int n) {
	vector<int>num;
	while (n) {
		if (n % 2 == 1)
			num.push_back(1);
		else
			num.push_back(0);
		n /= 2;
	}
}

vector中存的是n的二进制,不过是从后往前存的,不过对于从低位到高位依次取出元素来计算,却是方便的(好吧,我就这么村存了,来打我呀)

 

矩阵乘法

咋算?

用代码表示矩阵乘法就是玩矩阵了

一步一步来,先看一下矩阵乘法用c++怎么实现(main函数中的m1和m2的位置写反了,见谅)

#include<iostream>
#include<vector>
using namespace std;

vector<vector<int>> Matrix_multi(vector<vector<int>>m1,
		vector<vector<int>>m2){
	int temp=0;
	//m1的行,m2的列,就是结果矩阵的尺寸
	vector<vector<int>>res(m1.size(),vector<int>(m2[0].size()));
	for(int i=0; i<res.size(); i++){
		for(int j=0; j<res[0].size(); j++){
			for(int k=0; k<m2.size(); k++){
				res[i][j]+=m1[i][k]*m2[k][j];
			}
		}
	}
	return res;
}

int main(){
	vector<vector<int>>m2={
		{1, 2, 3,  4, 5},
		{6, 7, 8,  9,10},
		{11,12,13,14,15},
		{16,17,18,19,20}};

	vector<vector<int>>m1={
		{1, 2, 3,  4},
        {6, 7, 8,  9},
        {11,12,13,14}};

	vector<vector<int>>answer=Matrix_multi(m1,m2);
	for(auto i :answer){
		for(auto j :i)
			cout<<j<<" ";
		cout<<endl;
	}
	return 0;
}

Java的实现版本

public static int[][] muliMatrix(int[][] m1, int[][] m2) {
		int[][] res = new int[m1.length][m2[0].length];
		for (int i = 0; i < m1.length; i++) {
			for (int j = 0; j < m2[0].length; j++) {
				for (int k = 0; k < m2.length; k++) {
					res[i][j] += m1[i][k] * m2[k][j];
				}
			}
		}
		return res;
	}

 

 

终于可以来实现我们的快速幂了(这段代码有个bug,抓不到啊,哭)

//矩阵乘法
vector<vector<int>>Matrix_multi(vector<vector<int>>m1,
		vector<vector<int>>m2){
	//数组初始化
	vector<vector<int>>res(m1.size(),vector<int>(m2[0].size()));
	//行
	for(int i=0; i<m1.size(); i++){
		//列
		for(int j=0; j<m2[0].size(); j++){
			for(int k=0; k<m2.size(); k++){
				res[i][j]+=m1[i][k]+m2[k][j];
			}
		}
	}
	return res;
}

//计算传入参数的二进制
vector<int>calculate_binary(int n){
	vector<int>res;
	while(n>0){
		if(n%2)
			res.push_back(1);
		else
			res.push_back(0);		
		n/=2;
	}
	return res;
}

//快速幂,不会打英文,皮一下也很开心
int QuickMi(int n){
	/*
	快速幂心法:
	f(n)=f(n-1)+f(n-2),则矩阵就是2阶的(几阶看被减的最大的数)
	n阶,则需要解n*n个变量
	*/
	if(n<1) return 0;
	if(n==1) return 1;
	if(n==2) return 2;
	vector<vector<int>>res={{1,0},{0,1}};
	vector<vector<int>>tool={{1,1},{1,0}};
	//计算n-2的二进制是多少
	vector<int>binary=calculate_binary(n-2);
	for(int i=0; i<binary.size(); i++){
		if(binary[i]){
			res=Matrix_multi(res, tool);
		}
		tool=Matrix_multi(tool, tool);
	}
	//因为结果是|f(n),f(n-1)|=|f(2),f(1)|*res矩阵,|f(2),f(1)|=|2,1|,因此f(n)=2*res[0][0] + res[1][0]
	return 2*res[0][0] + res[1][0];
}

int main(){
	int n=30;
	//快速幂
	int answer=QuickMi(n);
	cout<<answer<<endl;
	return 0;
}

 

 

完整代码(快速幂处有一个没抓到的bug)

/*
字符串只由'0'和'1'两种字符构成,
当字符串长度为1时,所有可能的字符串为"0"、"1";
当字符串长度为2时,所有可能的字符串为"00"、"01"、"10"、"11";
当字符串长度为3时,所有可能的字符串为"000"、"001"、"010"、"011"、"100"、
"101"、"110"、"111"
...
如果某一个字符串中,只要是出现'0'的位置,左边就靠着'1',这样的字符串叫作达
标字符串。
给定一个正数N,返回所有长度为N的字符串中,达标字符串的数量。
比如,N=3,返回3,因为只有"101"、"110"、"111"达标。
*/

//思路——费波纳茨
#include<iostream>
#include<vector>
using namespace std;

int process(int i, int n){
    if(i==n) return 1;
    if(i==n-1) return 2;
    return process(i+1, n) + process(i+2, n);
}

int getNum1(int n){
	if(n<1) return 0;
	return process(1,n);
}

int dp(int n){
	if(n<1) return 0;
	if(n==1) return 1;
	
	vector<int>num(n+1);
	num[1]=1;
	num[2]=2;
	//第2到第n位的值
	for(int i=3; i<n+1; i++)
		num[i]=num[i-1]+num[i-2];
	cout<<"dp1="<<num[n]<<endl;
	return num[n];
}

//空间优化之后的动态规划
int dp2(int n){
	if(n<1) return 0;
	if(n==1) return 1;

	int temp=0, cur=1, pre=1;
	for(int i=2; i<n+1; i++){
		temp=cur;
		cur+=pre;
		pre=temp;
	}
	cout<<"dp2="<<cur<<endl;
	return cur;
}

//矩阵乘法
vector<vector<int>>Matrix_multi(vector<vector<int>>m1,
		vector<vector<int>>m2){
	//数组初始化
	vector<vector<int>>res(m1.size(),vector<int>(m2[0].size()));
	//行
	for(int i=0; i<m1.size(); i++){
		//列
		for(int j=0; j<m2[0].size(); j++){
			for(int k=0; k<m2.size(); k++){
				res[i][j]+=m1[i][k]+m2[k][j];
			}
		}
	}
	return res;
}

//计算传入参数的二进制
vector<int>calculate_binary(int n){
	vector<int>res;
	int temp=0;
	while(n>0){
		if(n%2)
			temp=1;
		else
			temp=0;
		res.push_back(temp);
		n/=2;
	}
	return res;
}

//快速幂,不会打英文,皮一下也很开心
int QuickMi(int n){
	/*
	快速幂心法:
	f(n)=f(n-1)+f(n-2),则矩阵就是2阶的(几阶看被减的最大的数)
	n阶,则需要解n*n个变量
	*/
	if(n<1) return 0;
	if(n==1) return 1;
	if(n==2) return 2;
	vector<vector<int>>res={{1,0},{0,1}};
	vector<vector<int>>tool={{1,1},{1,0}};
	//计算n-2的二进制是多少
	vector<int>binary=calculate_binary(n-2);
	for(int i=0; i<binary.size(); i++){
		if(binary[i]){
			res=Matrix_multi(res, tool);
		}
		tool=Matrix_multi(tool, tool);
	}
	//因为结果是|f(n),f(n-1)|=|f(2),f(1)|*res矩阵,|f(2),f(1)|=|2,1|,因此f(n)=2*res[0][0] + res[1][0]
	return 2*res[0][0] + res[1][0];
}

int main(){
	int n=30;
	//普通费波纳茨
	int normal=getNum1(n);
	cout<<"normal="<<normal<<endl;
	//动态规划
	int dynamic=dp(n);
	//优化空间之后不的动态规划
	dp2(n);
	//快速幂
	int answer=QuickMi(n);
	cout<<answer<<endl;
	return 0;
}

 

 

扩展——费波纳茨适用题型

牛,每年生一个niu,小牛三岁后开始生牛,牛十岁就会死,这可以构成一个什么递推式?见下图

 

 

费波纳茨适用于

那些除了初始项之外,其余项都有严格递推式的题,有if,else的,就不适合用费波纳茨,因为他有条件转移。

相关文章
|
6月前
|
算法 测试技术 C++
【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II
【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II
|
6月前
|
算法 测试技术 C#
【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II
【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II
|
3月前
|
C++
C++ PCL 计算多个RT矩阵变换后的变换矩阵
C++ PCL 计算多个RT矩阵变换后的变换矩阵
45 0
|
5月前
|
C++
C++解决线性代数矩阵转置 小实践
【6月更文挑战第3天】C++解决线性代数矩阵转置
72 2
|
6月前
|
算法 测试技术 Serverless
【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素
【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素
|
6月前
|
人工智能 小程序 BI
矩阵的转置、加和乘法写入C++
矩阵的转置、加和乘法写入C++
55 0
|
6月前
|
算法 Java Go
Rust每日一练(Leetday0018) N皇后II、最大子数组和、螺旋矩阵
Rust每日一练(Leetday0018) N皇后II、最大子数组和、螺旋矩阵
47 1
Rust每日一练(Leetday0018) N皇后II、最大子数组和、螺旋矩阵
|
6月前
|
算法 测试技术 C++
【字符串】【 LCP】【C++算法】2573找出对应 LCP 矩阵的字符串
【字符串】【 LCP】【C++算法】2573找出对应 LCP 矩阵的字符串
|
6月前
|
算法 C++
【动态规划】【矩阵】C++算法329矩阵中的最长递增路径
【动态规划】【矩阵】C++算法329矩阵中的最长递增路径
|
6月前
|
传感器 人工智能 算法
掌握C++中的状态-事件回调矩阵:打造强大的有限状态机
掌握C++中的状态-事件回调矩阵:打造强大的有限状态机
128 0