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

全文线索：

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

 

一、来解题

字符串只由'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的，就不适合用费波纳茨，因为他有条件转移。