您的位置:

c语言矩阵快速幂,快速幂算法c语言代码

c语言矩阵快速幂,快速幂算法c语言代码

更新:

本文目录一览:

矩阵的幂怎么算?

有下面三种情况:

1、如果你所要求的是一般矩阵的高次幂的话,是没有捷径可走的,只能够一个个去乘出来。

至于低次幂,如果能够相似对角化,即:存在简便算法的话,在二阶矩阵的情况下简便算法未必有直接乘来得快,所以推荐直接乘。

2、如果你要求的是能够相似对角化的矩阵的高次幂的话,是存在简便算法的。

设要求矩阵A的n次幂,且A=Q^(-1)*Λ*Q,其中Q为可逆阵,Λ为对角阵。

即:A可以相似对角化。那么此时,有求幂公式:A^n=Q^(-1)*(Λ)^n*Q,而对角阵求n次方,只需要每个对角元素变为n次方即可,这样就可以快速求出二阶矩阵A的的高次幂。

3、如果矩阵可以相似对角化,求相似对角化的矩阵Q的具体步骤为:

求|λE-A|=0 (其中E为单位阵)的解,得λ1和λ2(不管是否重根),这就是Λ矩阵的对角元素。

依次把λ1和λ2带入方程(如果λ是重根只需代一次,就可求得两个基础解)[λE-A][x]=[0],求得两个解向量[x1]、[x2],从而矩阵Q的形式就是[x1 x2]。

接下来的求逆运算是一种基础运算,这里不再赘述。

下面可以举一个例子:

二阶方阵:

1 a

0 1

求它的n次方矩阵

方阵A的k次幂定义为 k 个A连乘: A^k = AA...A (k个)

一些常用的性质有:

1. (A^m)^n = A^mn

2. A^mA^n = A^(m+n)

一般计算的方法有:

1. 计算A^2,A^3 找规律, 然后用归纳法证明

2. 若r(A)=1, 则A=αβ^T, A^n=(β^Tα)^(n-1)A

注: β^Tα =α^Tβ = tr(αβ^T)

3. 分拆法: A=B+C, BC=CB, 用二项式公式展开

适用于 B^n 易计算, C的低次幂为零矩阵: C^2 或 C^3 = 0.

4. 用对角化 A=P^-1diagP

A^n = P^-1diag^nP

扩展资料:

幂等矩阵的主要性质:

1.幂等矩阵的特征值只可能是0,1;

2.幂等矩阵可对角化;

3.幂等矩阵的迹等于幂等矩阵的秩,即tr(A)=rank(A);

4.可逆的幂等矩阵为E;

5.方阵零矩阵和单位矩阵都是幂等矩阵;

6.幂等矩阵A满足:A(E-A)=(E-A)A=0;

7.幂等矩阵A:Ax=x的充要条件是x∈R(A);

8.A的核N(A)等于(E-A)的列空间R(E-A),且N(E-A)=R(A)。考虑幂等矩阵运算后仍为幂等矩阵的要求,可以给出幂等矩阵的运算:

1)设 A1,A2都是幂等矩阵,则(A1+A2) 为幂等矩阵的充分必要条件为:A1·A2 =A2·A1=0,且有:R(A1+A2) =R (A1) ⊕R (A2);N(A1+A2) =N(A1)∩N(A2);

2)设 A1, A2都是幂等矩阵,则(A1-A2) 为幂等矩阵的充分必要条件为:A1·A2=A2·A1=A2,且有:R(A1-A2) =R(A1)∩N (A2);N (A1- A2) =N (A1)⊕R (A2);

3)设 A1,A2都是幂等矩阵,若A1·A2=A2·A1,则A1·A2为幂等矩阵,且有:R (A1·A2) =R(A1) ∩R (A2);N (A1·A2) =N (A1) +N (A2)。

如何用c语言中的函数递归调用算法实现n阶矩阵的n次幂的求解?

/*用c语言中的函数递归调用算法实现n阶矩阵的n次幂*/

#include stdio.h

#include stdlib.h

#include time.h

#include string.h

//创建矩阵,矩阵用一维数组存储

double *matCreate(unsigned int m, unsigned int n)

{

double *p = (double *)malloc(sizeof(double) * m * n);

if (p == NULL) printf("创建矩阵失败!\n");

return p;

}

//输入矩阵元素

void matInput(double *a, unsigned int m, unsigned int n)

{

for (int i = 0; i m; ++i)

{

for (int j = 0; j n; ++j)

{

scanf("%f ", a[i * n + j]);

}

}

return;

}

//随机产生矩阵元素,均匀分布于[from to]

void matInitRand(double *a, unsigned int m, unsigned int n, double from, double to)

{

if (a == NULL || m = 0 || n = 0) return;

double x;

srand(time(NULL));

for (int i = 0; i m; ++i)

{

for (int j = 0; j n; ++j)

{

x = (1.0 * rand() / RAND_MAX) * (to - from) + from;

a[i * n + j] = x;

}

}

return;

}

//转置

void matTranspose(double *a, double *b, unsigned int m, unsigned int n)

{

for (int i = 0; i m; ++i)

{

for (int j = 0; j n; ++j)

{

b[j*n +i]=a[i * n + j] ;

}

}

}

//输出矩阵

void matPrint(double *a, unsigned int m, unsigned int n)

{

for (int i = 0; i m; ++i)

{

for (int j = 0; j n; ++j)

{

printf("%8.4f ", a[i * n + j]);

}

putchar('\n');

}

return;

}

//矩阵乘法c=a*b

void matMul(double *a, double *b, double *c, unsigned int m, unsigned int n, unsigned int k)

{

if (a == NULL || b == NULL || c == NULL || m = 0 || n = 0 || k = 0) return;

double x = 0.0f;

for (int i = 0; i m; ++i)

{

for (int u = 0; u k; ++u)

{

x = 0.0f;

for (int j = 0; j n; ++j)

{

x += a[i * n + j] * b[j * k + u];

}

c[i * k + u] = x;

}

}

return;

}

//b=a^n, a:m*m阶矩阵

void matFac(double *a, double *b, unsigned int n, unsigned int m)

{

double *c = (double *)malloc(sizeof(double) * m * m); //保存临时结果

if (n 1)

{

matFac(a, c, n - 1, m);

matMul(a, c, b, m, m, m);

}

else

memcpy(b, a, sizeof(double)*m * m);

// printf("%d:\n",n);

// matPrint(b, m,m);

free(c); //回收内存

return ;

}

#define M 3

#define N 4

#define K N

int main(int argc, char const *argv[])

{

double *A, *B, *B1,*BT, *C;

A = matCreate(M, N);

B = matCreate(N, K);

B1 = matCreate(N, K);

BT = matCreate(K,N);

C = matCreate(M, K);

if (!A || !B || !B1 || !BT || !C) return -1;

matInitRand(A, M, N, 0.0f, 1.0f);

printf("A=\n");

matPrint(A, M, N);

matInitRand(B, N, K, 0.0f, 1.0f);

printf("B=\n");

matPrint(B, N, K);

matTranspose(B,BT,N,K);

printf("B'=\n");

matPrint(BT, K,N);

matMul(A, B, C, M, N, K);

printf("C=A*B\n");

matPrint(C, M, N);

matFac(B, B1, 4, N);

printf("B^4\n");

matPrint(B1, N, K);

return 0;

}

c语言,快速幂代码是什么,怎么用?

所谓的快速幂,实际上是快速幂取模的缩写,简单的说,就是快速的求一个幂式的模(余)。在程序设计过程中,经常要去求一些大数对于某个数的余数,为了得到更快、计算范围更大的算法,产生了快速幂取模算法。

用递归

x^y可如下实现

unsigned long pow(int x, unsigned y)

{

unsigned long tmp;

if(!y) return 1;

tmp = pow(x, y / 2);

if(y % 2 == 0) return (tmp * tmp);

else return (tmp * tmp * x);

}

用C/C++如何实现矩阵的幂运算,求高手作答~

#includestdio.h

#includestring.h

#includestdlib.h

#includetime.h

int ** alloc2d(int m) {

int **array,i;

array=(int **)malloc(m*sizeof(int *));

if(array==NULL) return NULL;

for(i=0;im;i++) {

array[i]=(int *)malloc(m*sizeof(int));

if(array[i]==NULL) {for(;i=0;i--) {free(array[i]);} free(array);return NULL;}

}

return array;

}

void autoinput(int **a,int m) {

int i,j;

srand(time(0));

for(i=0;im;i++)

for(j=0;jm;j++)

*(*(a+i)+j)=rand()%3;

}

void out(int **a,int m) {

int i,j;

for(i=0;im;i++) {

for(j=0;jm;j++)

printf("%4d",*(*(a+i)+j));

printf("\n");

}

}

int **mltply(int **a,int **b,int **c,int m) {

int i,j,k;

for(i=0;im;i++)

for(j=0;jm;j++)

for(*(*(c+i)+j)=0,k=0;km;k++)

*(*(c+i)+j)+=*(*(a+i)+k)*(*(*(b+k)+j));

return c;

}

int main() {

int i,m,times,j,n=0;

int **ops[3];

printf("input乘法方阵规模m*m几次幂:\n");

scanf("%d%d",m,times);

for(i=0;i3;i++) {

ops[i]=alloc2d(m);

if(i=0) {autoinput(ops[i],m);printf("矩阵%d\n",i+1);out(ops[i],m);printf("\n");}

}

for(int h=1;h=2;h++)

for(i=0;im;i++)

for(j=0;jm;j++)

*(*(ops[h]+i)+j)=0;

printf("\n乘法\n");

mltply(ops[0],ops[0],ops[1],m);

times-=2;

while(times) {

if(n++%2==0) mltply(ops[1],ops[0],ops[2],m);

else mltply(ops[2],ops[0],ops[1],m);

--times;

}

if(n%2==0) out(ops[1],m);

else out(ops[2],m);

return 0;

}

//矩阵输入用的随机

//可能麻烦了点 要不你优化一下

用C语言编写程序求矩阵的n次方

这要看具体情况 一般有以下几种方法 1. 计算A^2,A^3 找规律, 然后用归纳法证明 2. 若r(A)=1, 则A=αβ^T, A^n=(β^Tα)^(n-1)A 注: β^Tα =α^Tβ = tr(αβ^T) 3. 分拆法: A=B+C, BC=CB, 用二项式公式展开 适用于 B^n 易计算, C的低次幂为零: C^2 或 C^3.

C语言有关快速幂的问题

type

arrty=array[1..10000] of longint;

var

n,mn,len,lenm,i,mnl:longint;

a,m:arrty;

procedure mxm;

var

c:arrty;

i,j:longint;

begin

fillchar(c,sizeof(c),0);

for i:=1 to lenm do

for j:=1 to lenm do

begin

inc(c[i+j-1],m[i]*m[j]);

inc(c[i+j],c[i+j-1] div 10);

c[i+j-1]:=c[i+j-1] mod 10;

end;

lenm:=lenm+lenm+1;

while (lenm1) and (c[lenm]=0) do

dec(lenm);

for i:=1 to lenm do

m[i]:=c[i];

end;

procedure axm;

var

c:arrty;

i,j:longint;

begin

fillchar(c,sizeof(c),0);

for i:=1 to len do

for j:=1 to lenm do

begin

inc(c[i+j-1],a[i]*m[j]);

inc(c[i+j],c[i+j-1] div 10);

c[i+j-1]:=c[i+j-1] mod 10;

end;

len:=len+lenm+1;

while (len1) and (c[len]=0) do

dec(len);

for i:=1 to len do

a[i]:=c[i];

end;

begin

fillchar(a,sizeof(a),0);

readln(mn,n);

mnl:=mn;

len:=0;

while mnl0 do

begin

inc(lenm);

m[lenm]:=mnl mod 10;

mnl:=mnl div 10;

end;

a[1]:=1;

len:=1;

while n0 do

begin

if n mod 2=1 then

axm;

n:=n div 2;

mxm;

end;

for i:=len downto 1 do

write(a[i]);

writeln;

end.