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

发布时间：2023-12-08

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

更新：2023-01-08 19:38

本文目录一览：

1、矩阵的幂怎么算？ 2、如何用c语言中的函数递归调用算法实现n阶矩阵的n次幂的求解？ 3、c语言，快速幂代码是什么，怎么用？ 4、用C/C++如何实现矩阵的幂运算，求高手作答~ 5、用C语言编写程序求矩阵的n次方 6、C语言有关快速幂的问题

矩阵的幂怎么算？

有下面三种情况： 1、如果你所要求的是一般矩阵的高次幂的话，是没有捷径可走的，只能够一个个去乘出来。 至于低次幂，如果能够相似对角化，即：存在简便算法的话，在二阶矩阵的情况下简便算法未必有直接乘来得快，所以推荐直接乘。 2、如果你要求的是能够相似对角化的矩阵的高次幂的话，是存在简便算法的。 设要求矩阵A的n次幂，且A=Q^(-1)ΛQ，其中Q为可逆阵，Λ为对角阵。 即：A可以相似对角化。那么此时，有求幂公式：A^n=Q^(-1)(Λ)^nQ，而对角阵求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) 一般计算的方法有：
  3. 计算A^2,A^3 找规律, 然后用归纳法证明
  4. 若r(A)=1, 则A=αβ^T, A^n=(β^Tα)^(n-1)A 注: β^Tα =α^Tβ = tr(αβ^T)
  5. 分拆法: A=B+C, BC=CB, 用二项式公式展开 适用于 B^n 易计算, C的低次幂为零矩阵: C^2 或 C^3 = 0.
  6. 用对角化 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++如何实现矩阵的幂运算，求高手作答~

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
int ** alloc2d(int m) {
    int **array,i;
    array=(int **)malloc(m*sizeof(int *));
    if(array==NULL) return NULL;
    for(i=0;i<m;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;i<m;i++)
        for(j=0;j<m;j++)
            *(*(a+i)+j)=rand()%3;
}
void out(int **a,int m) {
    int i,j;
    for(i=0;i<m;i++) {
        for(j=0;j<m;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;i<m;i++)
        for(j=0;j<m;j++)
            for(*(*(c+i)+j)=0,k=0;k<m;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;i<3;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;i<m;i++)
            for(j=0;j<m;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 (lenm>1) 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 (len>1) 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 mnl>0 do
    begin
        inc(lenm);
        m[lenm]:=mnl mod 10;
        mnl:=mnl div 10;
    end;
    a[1]:=1;
    len:=1;
    while n>0 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.
推荐文章