遞歸演算法矩陣

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;
}