welcome
0%

c-矩阵的快速幂算法

发表于 更新于 分类于

1.主要思想快速幂的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
int fastPower(int base, int exponent) {
    int sum = 1;
    while (exponent != 0)
     {
        if ((exponent & 1) != 0) 
        {
            sum *= base;
        }
        exponent = exponent >> 1;  // 对指数进行移位
        base *= base;               // 让base的次幂以2的倍数增长
    }
    return sum;
}

代码说明：

对于(exponent & 1) != 0语句如果exponent是奇数则exponent&1等于1，否则如果exponent为偶数则exponent&1等于0；

关键思想是用二进制来计算指数

2.衍生出矩阵的快速幂算法

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
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	int Array[n][n],unit[n][n],temp[n][n];
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
		cin>>Array[i][j];
	
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	if(i==j) unit[i][j]=1;
	else unit[i][j]=0;
	//计算 
while(m!=0)
{
	if((m&1)!=0)
	{
		for(int i=0;i<n;i++)
    	{
		for(int j=0;j<n;j++)
		{
			int sum=0;//标记
			for(int k=0;k<n;k++)
			{
				sum+=unit[i][k]*Array[k][j];
			} 
			temp[i][j]=sum;	//利用temp暂时储存第一次计算结果 
		}
    	}
    	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
	    unit[i][j]=temp[i][j];
	}
	
	m=m>>1;
	for(int i=0;i<n;i++)
    	{
		for(int j=0;j<n;j++)
		{
			int sum=0;//标记
			for(int k=0;k<n;k++)
			{
				sum+=Array[i][k]*Array[k][j];
			} 
			temp[i][j]=sum;	//利用temp暂时储存第一次计算结果 
		}
    	
		}
    	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
	    Array[i][j]=temp[i][j];
}
for(int i=0;i<n;i++)
{
		for(int j=0;j<n;j++)
		cout<<unit[i][j]<<" ";
		cout<<endl;
}
return 0;
}