重温斐波那契数列

写在前面

之前写过一个快速斐波那契python版本的，今天本来想来写个C++版本的快速斐波那契，然后又没写出来，，，，（在线卑微T_T）。所以就借着这个时间，用C++来整理一下整数快速幂，矩阵快速幂以及快速斐波那契的知识吧。

part I 整数快速幂

在之前的博客python写简单的整数快速幂和矩阵快速幂里面，我给过两个简单的例子，可以很容易看清楚算法的套路，然后具体的分析也稍微写过，在这里，分析传送门。这些用的都是python语言实现的，接下来我们换成C++语言整理一下思路。

先举个例子，假如我们计算$a^n$，在没有正负约束等情况下，比如我们要算$a^{11}$：
按照最简单的就是$a\ast a\ast a\ast a\ast a\ast a\ast a\ast a\ast a\ast a\ast a$，这样要算10次乘法运算。
$11$的二进制为$1011$
$a^{11}=a^8\ast a^2\ast a^1$
我们假设最后结果存在$res$变量里面，开始时候$res=1$
第一圈：$res=res\ast a^1=a$，把基数a变成$a^2=a^2$，因为此时1011要右移一位变成101
第二圈：$res=res\ast a^2=a^3$，把基数变成$(a^2{)}^2=a^4$，101右移一位变成10，
第三圈：由于二进制10的最后一位不是1，所以这一圈不必res*,只要把基数变为$(a^4{)}^2=a^8$,10右移一位变成1.
第四圈：$res=res\ast a^8=a^{11}$，把基数变成$(a^8{)}^2=a^{16}$，1右移一位变成0
第五圈：跳出循环
所以在计算$a^{11}$的时候，我们只算了4次，数据越庞大效果越明显。在每一圈结束的时候，一定要将基数变成基数的平方。当然这里还是没有考虑负数，大数，等问题，接下来看个题目。

我们拿剑指 Offer 16. 数值的整数次方来说，题目如下：

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）。不得使用库函数，同时不需要考虑大数问题。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：
输入：x = 2.10000, n = 3
输出：9.26100

示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2^-2 = 1/2^2 = 1/4 = 0.25

提示：
-100.0 < x < 100.0
-2^31 <= n <= 2^31-1
-10^4 <= x^n <= 10^4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析：

• 给了$x$的范围是有正有负的，包含零，需要考虑。
• $n$的范围也很大，$-2^{31}<=n<=2^{31}-1$，当$n=-2^{31}$时候，如果用整型直接取相反数会越界，会报错，所以得定义一个新的long类型变量。
• 考虑在$n$为负值的时候的幂运算是怎么实现的
  直接上代码看：

class Solution {
public:
    double myPow(double x, int n) {
        if(!n || !x) return 1;
        long num = n;
        if(n < 0) 
        {
            num = -num;//如果n是负数，那么取相反数
            x = 1/x;//x取倒数
        }
        double res = 1;//存结果
        while(num)
        {
            if(num%2)
                res*=x;//如果二进制的最后一位是1，那么结果乘上目前这个基数
            x *= x;//不管咋样，num在右移，x每一轮都得变成自身的平方
            num >>= 1;
        }
        return res;
    }
};

part II 矩阵快速幂

其实和整数快速幂是一样的，只不过把乘法运算换成了矩阵乘法运算。
在这里写个简单的快速求$2\ast 2$矩阵的$n$次方例子。

#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> fun(vector<vector<int>> M,vector<vector<int>> N)
{
	//这个意思是实现两个方阵的矩阵乘积
	int x = M.size();
	vector<vector<int>> res(2,vector<int>(2));
	for(int i = 0;i<x;i++)
	{
		for(int j = 0;j<x;j++)
		{
			for(int k = 0;k < x;k++)
				res[i][j] += M[i][k]*N[k][j];
		}
	}
	return res;
}

vector<vector<int>> quickMa(vector<vector<int>> M,int n)
{
	vector<vector<int>>e = {{1,0},{0,1}};
	//下面开始和整数快速幂一样的操作
	while(n)
	{
		if(n%2)
			e = fun(e,M);
		M = fun(M,M);
		n >>= 1;
	}
	return e;
}


int main()
{
	//定义一个二维数组
	vector<vector<int>>a = {{1,2},{3,4}};
	//求平方
	vector<vector<int>>ans = quickMa(a,2);
	for(int i = 0;i<2;i++)
	{
		for(int j = 0;j<2;j++)
			cout<<ans[i][j]<<endl;
	}
	return 0;
}

矩阵快速幂就多了一个写矩阵相乘的子函数，一定要记住快速幂的套路！

part III 快速斐波那契

以力扣509.斐波那契数为例

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。

示例 1：
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：
输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：
输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
 
提示：
0 <= n <= 30
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fibonacci-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析：
其实这个写个递归写个迭代，都可以过，大可不必花这么多功夫写矩阵快速幂。所以仅仅是借题目重温知识点。
迭代做法：

class Solution {
public:
    int fib(int n) {
        if(!n )return 0;
        if(n==1)return 1;
        int a = 0,b = 1;
        for(int i = 2;i<=n;i++)
        {
            int temp = a+b;
            a = b;
            b = temp;        
        }
        return b;
    }
};

下面使用矩阵快速幂来做：
假设一个矩阵
$A=[\begin{array}{cc}1& 1\\ 1& 0\end{array}]$

$[\begin{array}{cc}f(2)& f(1)\\ 0& 0\end{array}]$$\ast$ $[\begin{array}{cc}1& 1\\ 1& 0\end{array}]$$=$ $[\begin{array}{cc}f(3)& f(2)\\ 0& 0\end{array}]$
如此迭代，第n个斐波那契数便是
$[\begin{array}{cc}f(2)& f(1)\\ 0& 0\end{array}]$$\ast$ $[\begin{array}{cc}1& 1\\ 1& 0\end{array}{]}^{(n-2)}$$=$ $[\begin{array}{cc}f(n)& f(n-1)\\ 0& 0\end{array}]$

做完矩阵快速幂之后取[0][0]位置的数即可得到第n个斐波那契。
所以先对
$[\begin{array}{cc}1& 1\\ 1& 0\end{array}]$
求$(n-2)$次幂，再去做一下矩阵相乘即可。

class Solution {
public:
    vector<vector<int>> fun(vector<vector<int>> M,vector<vector<int>> N)
    {
        //这个意思是实现两个方阵的矩阵乘积
        int x = M.size();
        vector<vector<int>> res(2,vector<int>(2));
        for(int i = 0;i<x;i++)
        {
            for(int j = 0;j<x;j++)
            {
                for(int k = 0;k < x;k++)
                    res[i][j] += M[i][k]*N[k][j];
            }
        }
        return res;
    }
    vector<vector<int>> quickMa(vector<vector<int>> M,int n)
    {
        //求M矩阵的n次幂
        vector<vector<int>>e = {{1,0},{0,1}};
        //下面开始和整数快速幂一样的操作
        while(n)
        {
            if(n%2)
                e = fun(e,M);
            M = fun(M,M);
            n >>= 1;
        }
        return e;
    }
    int fib(int n) {
        if(!n) return 0;
        if(n == 1 || n == 2)return 1;
        vector<vector<int>>a = {{1,1},{0,0}};
	    vector<vector<int>>b = {{1,1},{1,0}};
        //求b矩阵的n-2次幂
        vector<vector<int>>res1 = quickMa(b,n-2);
        //俩矩阵相乘
        vector<vector<int>>res2 = fun(a,res1);
        return res2[0][0];
    }
};

这个做法开了很多的空间，只有在遇到极大极大的数 的时候才会体现出优势。

总结

整数快速幂、矩阵快速幂、斐波那契数的矩阵求法复习了一下。
如有不当之处，欢迎批评指正~