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

2023-07-28 17:17:28

全文线索：

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

 

一、来解题

字符串只由'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;
}

 

三、快速幂

快速幂的使用场景——除了初始项之外，其余项都有要个递归式的问题，可以使用快速幂进行求解。那种有if ，else的这种不能用快速幂，快速幂要求严格的递推式。

铺垫

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

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

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

因此可以得到递推式——|f(n)-f(n-1)|=|f(2)-f(1)| * 来啃硬骨头——费波纳茨（Fibonacci）矩阵快速幂 c++的（n-2）次幂

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

下图所示，差6阶则变成 n-6：

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

 

 

 

 

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

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

第一步：将75拆成二进制，即1001011

第二步：两个辅助变量，t=10，res=1（用于res记录结果）

上伪代码（时间复杂度O(logn)=O(logn)(即t=t*t的次数)+O(logn)（即75的二进制为1的项与t相乘的次数））：

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次幂的计算结果。

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

矩阵的高次幂计算同理。

 

 

矩阵乘法

咋算？

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

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

一步一步来，先看一下矩阵乘法用c++怎么实现

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

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<m1[0].size(); k++){
				res[i][j]+=m1[i][k]*m2[k][j];
			}
		}
	}
	return res;
}

int main(){
	vector<vector<int>>m1={
		{1, 2, 3,  4},
		{6, 7, 8,  9},
		{11,12,13,14}};
	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>>answer=Matrix_multi(m1,m2);
	for(auto i :answer){
		for(auto j :i)
			cout<<j<<" ";
		cout<<endl;
	}

	return 0;
}

运行结果：

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

 

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;
	}

 

矩阵快速幂的实现代码

//矩阵乘法
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;
}

//p为幂次，base是事先计算出的费波纳茨对应的矩阵。矩阵的计算方法在上方
vector<vector<int>> matrixPower(vector<vector<int>>&base, int p){
	vector<vector<int>>res=
		{base.size(),vector<int>(base[0].size())};
	for(int i=0; i<res.size(); i++){
		res[i][i]=1;
	}	
	vector<vector<int>>tmp=base;
	//依次查看p的二进制位
	for(; p!=0; p>>=1){
		//如果当前二进制位为1
		if((p & 1)!=0){
			res=Matrix_multi(res, tmp);
		}
		tmp=Matrix_multi(tmp, tmp);
	}
	return res;
}

 

 

完整代码

/*
字符串只由'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;
}

//p为幂次，base是事先计算出的费波纳茨对应的矩阵。矩阵的计算方法在上方
vector<vector<int>> matrixPower(vector<vector<int>>&base, int p){
	vector<vector<int>>res=
		{base.size(),vector<int>(base[0].size())};
	for(int i=0; i<res.size(); i++){
		res[i][i]=1;
	}	
	vector<vector<int>>tmp=base;
	//依次查看p的二进制位
	for(; p!=0; p>>=1){
		//如果当前二进制位为1
		if((p & 1)!=0){
			res=Matrix_multi(res, tmp);
		}
		tmp=Matrix_multi(tmp, tmp);
	}
	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>>base={{1,1},{1,0}};
	//计算出最终的矩阵结果
	vector<vector<int>>res=matrixPower(base, n - 2);
	//因为结果是|f(n),f(n-1)|=|f(2),f(1)|*base矩阵，
	//|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，小牛三岁后开始生牛，牛十岁就会死，这可以构成一个什么递推式？见下图

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

 

 

费波纳茨适用于

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

 

 

补充一个费波纳茨的题

 

在迷迷糊糊的大草原上，小红捡到了n根木棍，第 i 根木棍的长度为 i，小红现在很开心。想选出其中的三根木棍组成美丽的三角形。但是小明想捉弄小红，想去掉一些木棍，使得小红任意选三根木棍都不能组成三角形。

请问小明最少去掉多少根木棍呢？
给定N，返回至少去掉多少根？

 

思考：

这题就是求1~n中有多少个费波纳茨数。因为组不成三角形的条件是Y+Z<X，我们让每个Y+Z=X就是最经济的做法了。要拿走的木根根数，就是前n个数中的非费波纳茨数啊。

 

上代码

#include<iostream>
using namespace std;

void calculate(int n){
	if(n<3) return;

	//因为第i根木棍的长度为i，因此要保留的数字为：
	//第一个数是1，第二个数是2，第三个数是3，第四个数是5
	int num=2;
	int f_1=1, f_2=2;
	while(f_2+f_1<=n){
		num++;
		f_2=f_1+f_2;
		f_1=f_2-f_1;
	}
	cout<<n-num<<endl;
}

int main(){
	int n=0;
	cin>>n;
	calculate(n);
	return 0;
}

 

 

 

上一篇：【LeetCode每天一题】Fibonacci Number(斐波那契数列)


下一篇：2018-2019-2 20175211 实验一《Java开发环境的熟悉》实验报告