快速幂+矩阵优化斐波那契数列(超详细教程)前言一、快速幂二、矩阵优化斐波那契数列三、全部实现代码

78 阅读 0 评论 52 点赞

我是靠谱客的博主隐形水蜜桃，这篇文章主要介绍快速幂+矩阵优化斐波那契数列(超详细教程)前言一、快速幂二、矩阵优化斐波那契数列三、全部实现代码，现在分享给大家，希望可以做个参考。

文章目录

前言
一、快速幂
二、矩阵优化斐波那契数列
- 1.矩阵相关知识
- 2.斐波那契数列用矩阵表示
- 3.O(log2n)的斐波那契数列
三、全部实现代码

前言

我们首先讲解快速幂,然后利用快速幂优化矩阵乘法,将O(n)算法变为O(log2n),紧接着我们用矩阵实现斐波那契数列!

一、快速幂

通常我们算一个数a的n次幂,我们需要计算n次,也就是n个a相乘,这样难免太过缓慢,于是有了快速幂,即不需要n次操作就可以算出!
举例:计算A的9次幂
在这里插入图片描述

通过上述操作想必大家明白,快速幂的思想也就是二分的思想!

代码实现:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
int base,ans;//base为底数
//快速幂
void qpow(int n)
{
    //传入n次幂
    while(n)
    {
        if(n&1)ans=ans*base;//n为奇数
        base=base*base;
        n>>=1;// n/=2
    }
}
这里插入代码片

下面是使用递归实现快速幂代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
 int qpow(int a,int n){
	if(n == 0){//递归到底情况
		return 1;
	}
	if(n%2 == 1){//当n为奇数的时候
		return qpow(a, n/2)*qpow(a, n/2)*a;
	}else{
		return qpow(a,n/2)*qpow(a, n/2);
	}
}

(使用递归要慢于非递归)

代码阐释:

复制代码

1
2
 if(n&1)ans=ans*base;//n为奇数

这段代码中n&1是位运算,判断n是否为奇数,我举个例子给大家
7的二进制为 :111
1的二进制为 :001
&的含义是,0与0得0,1与0得0,1与1得1,所以7&1得001,转换为十进制为1,执行if语句所以7是奇数!

复制代码

1
2
 n>>1;// n/=2

这个也是位运算,我们接着举例
6的二进制为:110
“>>1” 1代表所有位向右侧移动1位,所以变为011,011对应十进制位3,所以">>1" 代表(➗=)2,同理"<<1"左移代表乘以等于(✖=)2!

二、矩阵优化斐波那契数列

1.矩阵相关知识

矩阵乘法:
在这里插入图片描述

矩阵乘法相关性质:

nxm的矩阵,乘以mxn的矩阵得到nxn的矩阵,中间m消去
矩阵乘法满足结合律:axbxc=(axc)xb

代码:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
 Matrix operator*(const Matrix &b) const
    {
        Matrix res;
        for(int i=1; i<=2; i++)
            for(int j=1; j<=2; j++)
                for(int k=1; k<=2; k++)
                {   //第i行乘以第j列的和
                    res.a[i][j]=res.a[i][j]+a[i][k]*b.a[k][j];
                }
        return res;
    }

2.斐波那契数列用矩阵表示

在这里插入图片描述

通过上图可以知道,前fn-2,fn-1可以通过乘一个矩阵得到fn
那么以此类推:

3.O(log2n)的斐波那契数列

由于斐波那契数列能用矩阵来推导出,又由于矩阵满足乘法结合律,需要n-2个上图的矩阵相乘,所以我们对这n-2个相乘的矩阵进行快速幂运算,即可得出O(log2n)的斐波那契数列!!

三、全部实现代码

复制代码

#include <bits/stdc++.h>
using namespace std;

//定义矩阵结构体
struct Matrix
{
    int a[3][3];
    Matrix()
    {
        memset(a,0,sizeof(a));
    }
    //矩阵乘法
    Matrix operator*(const Matrix &b) const
    {
        Matrix res;
        for(int i=1; i<=2; i++)
            for(int j=1; j<=2; j++)
                for(int k=1; k<=2; k++)
                {
                    res.a[i][j]=res.a[i][j]+a[i][k]*b.a[k][j];
                }
        return res;
    }
};

Matrix base,ans;

//初始化base,ans
void init()
{
    //矩阵
    //[0，1]
    //[1，1]
    base.a[1][1]=0;//这个11位置一定要初始化
    base.a[2][2]=base.a[1][2]=base.a[2][1]=1;
    //初始斐波那契数列f1=1,f2=1
    ans.a[1][1]=1;
    ans.a[1][2]=1;

}
//快速幂
void qpow(int n)
{
    //传入n次幂
    while(n)
    {
        if(n&1)ans=ans*base;//n为奇数
        base=base*base;
        n>>=1;// n/=2
    }
}

int main()
{

int n;
    while(scanf("%d",&n)!=EOF)
    {
        init();//每次初始化矩阵
        qpow(n-2);//快速幂优化
        cout<<ans.a[1][2]<<endl;
    }

return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;

//定义矩阵结构体
struct Matrix
{
    int a[3][3];
    Matrix()
    {
        memset(a,0,sizeof(a));
    }
    //矩阵乘法
    Matrix operator*(const Matrix &b) const
    {
        Matrix res;
        for(int i=1; i<=2; i++)
            for(int j=1; j<=2; j++)
                for(int k=1; k<=2; k++)
                {
                    res.a[i][j]=res.a[i][j]+a[i][k]*b.a[k][j];
                }
        return res;
    }
};

Matrix base,ans;

//初始化base,ans
void init()
{
    //矩阵
    //[0，1]
    //[1，1]
    base.a[1][1]=0;//这个11位置一定要初始化
    base.a[2][2]=base.a[1][2]=base.a[2][1]=1;
    //初始斐波那契数列f1=1,f2=1
    ans.a[1][1]=1;
    ans.a[1][2]=1;

}
//快速幂
void qpow(int n)
{
    //传入n次幂
    while(n)
    {
        if(n&1)ans=ans*base;//n为奇数
        base=base*base;
        n>>=1;// n/=2
    }
}

int main()
{

    int n;
    while(scanf("%d",&n)!=EOF)
    {
        init();//每次初始化矩阵
        qpow(n-2);//快速幂优化
        cout<<ans.a[1][2]<<endl;
    }

    return 0;
}