递归算法矩阵

A. 求矩阵A的N次方

1. 直接计算：A^n=A＊A^(n-1)
2. 折半计算：A^(2k)=(A^k)*(A^k)，A^(2k+1)=(A^k)*(A^k)*A
用递归实现算法2：
Matrix pow(Matrix A, int n) //求A^n
{
Matrix B;
if(n==1) return A;
else if(n % 2 == 0) {
B = pow(A, n/2);
return mul(B, B);
} else {
B = pow(A, n/2);
return mul(A, mul(B, B));
}
}
其中 mul(A,B)为普通矩阵乘法A*B

B. 如何用C++编程求矩阵的逆

#define N 5 /*[注]：修改6为你所要的矩阵阶数*/
#include "stdio.h"
#include "conio.h"

/*js()函数用于计算行列式,通过递归算法实现*/
int js(s,n)
int s[][N],n;
{int z,j,k,r,total=0;
int b[N][N];/*b[N][N]用于存放，在矩阵s[N][N]中元素s[0]的余子式*/
if(n>2) {for(z=0;z<n;z++)
{for(j=0;j<n-1;j++)
for(k=0;k<n-1;k++)
if(k>=z) b[j][k]=s[j+1][k+1];
else b[j][k]=s[j+1][k];
if(z%2==0) r=s[0][z]*js(b,n-1); /*递归调用*/
else r=(-1)*s[0][z]*js(b,n-1);
total=total+r;
}
}
else if(n==2) total=s[0][0]*s[1][1]-s[0][1]*s[1][0];
return total;
}

/*n_1()函数用于求原矩阵各元素对应的余子式，存放在数组b[N][N]中，定义为float型*/
void n_1(s,b,n)
int s[][N],n;
float b[][N];
{int z,j,k,l,m,g,a[N][N];
for(z=0;z<n;z++)
{l=z;
for(j=0;j<n;j++)
{ m=j;
for (k=0;k<n-1;k++)
for(g=0;g<n-1;g++)
{ if(g>=m&&k<l) a[k][g]=s[k][g+1];
else if(k>=l&&g<m) a[k][g]=s[k+1][g];
else if(k>=l&&g>=m) a[k][g]=s[k+1][g+1];
else a[k][g]=s[k][g];
}
b[z][j]=js(a,n-1);
}
}
}

main()
{int a[N][N];
float b[N][N];
int r,z,j;
float temp;
//clrscr();
printf("Input original data:\n");
for(z=0;z<N;z++) /*输入所需要的数据，为整型数据*/
for(j=0;j<N;j++)
scanf("%d",&a[z][j]);
printf("\nPress Enter continue......");
getchar();
//gotoxy(1,1);
printf("The original matrix is:\n");
for(z=0;z<N;z++)/*打印原矩阵*/
{for(j=0;j<N;j++)
printf("%5d",a[z][j]);
printf("\n");
}
r=js(a,N); /*调用js()函数计算原矩阵的行列式值*/
printf("\nThe original matrix hanglieshi is:|A|==%d\n",r);
if (r==0) printf("Because |A|==0,the original matrix have no nijuzhen!"); /*判断条件:若|A|==0，则原矩阵无逆矩阵，反之则存在逆矩阵*/
else
{n_1(a,b,N); /*调用n_1()函数，得到原矩阵各元素对应的"余子式",存放在数组b[N][N]中*/
for(z=0;z<N;z++) /*求代数余子式，此时b[N][N]中存放的为原矩阵各元素对应的"代数余子式"*/
for(j=0;j<N;j++)
if((z+j)%2!=0 && b[z][j]!=0) b[z][j]=-b[z][j];
for(z=0;z<N;z++) /*对b[N][N]转置,此时b[N][N]中存放的为原矩阵的伴随矩阵*/
for(j=z+2;j<N;j++)
{temp=b[z][j];
b[z][j]=b[j][z];
b[j][z]=temp;
}
printf("Because |A|!=0,the original matrix have nijuzhen!\n");
printf("The bansuijuzhen A* is:\n");
for(z=0;z<N;z++)/* 打印伴随矩阵A* */
{for(j=0;j<N;j++)
printf("%4.0f\t",b[z][j]);
printf("\n");
}

for(z=0;z<N;z++) /*求逆矩阵，此时b[N][N]中存放的是原矩阵的逆矩阵*/
for(j=0;j<N;j++)
b[z][j]=b[z][j]/r;
printf("\nThe nijuzhen is:(A*)/|A|(|A|=%d)\n",r); /*打印逆矩阵*/
for(z=0;z<N;z++)
{for(j=0;j<N;j++)
printf("%8.3f",b[z][j]);
printf("\n");
}
}
}

C. 如何用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;
}