加载中…
个人资料
微博
  • 博客等级：
  • 博客积分：
  • 博客访问：
  • 关注人气：
  • 获赠金笔：0支
  • 赠出金笔：0支
  • 荣誉徽章：
正文 字体大小：大 中 小

求n阶矩阵的k次方

(2013-08-14 20:48:04)
标签：

矩阵的n次方

 分类： 编程算法
（一）慢速的算法 O(N^3)
#include <stdio.h>
#include <stdlib.h>

//动态分配二维数组
//相当于 int t[][]
int **malloc2d(int r, int c)
{
    int i;
    int **t = malloc(r * sizeof(int *));
    for (i = 0; i < r; ++i)
        t[i] = malloc(c * sizeof(int));
    return t;
}

// src -- 源矩阵
// size -- 矩阵的阶
// xpower -- 次方
int **MatrixPower(int **src, int size, int xpower)
{
    int i, j, id, count, sum;
    int **mat = malloc2d(size, size);
    int **tmp = malloc2d(size, size);
    for (i = 0; i < size; ++i)
        for (j = 0; j < size; ++j)
            mat[i][j] = src[i][j];

    for (count = 1; count < xpower; ++count)
    {
        for (i = 0; i < size; ++i)
            for (j = 0; j < size; ++j)
                tmp[i][j] = mat[i][j];
        for (i = 0; i < size; ++i)
        {
            for (j = 0; j < size; ++j)
            {
                sum = 0;
                for (id = 0; id < size; ++id)
                    sum += tmp[i][id] * src[id][j];
                mat[i][j] = sum;
            }
        }
    }
    return mat;
}

int main()
{
    int n, k, i, j; // 求n阶矩阵的k次方
    while (scanf("%d%d", &n, &k) != EOF)
    {
        //int a[n][n];
        int **a = malloc2d(n, n);
        for (i = 0; i < n; ++i)
            for (j = 0; j < n; ++j)
scanf("%d", &a[i][j]);
                        
printf("a[n][n]:\n");
for(i=0; i
{
for(j=0; j
printf("%d ",a[i][j]);
printf("\n");
}
        
        int **result = MatrixPower(a, n, k);// 结果
        printf("result[n][n]:\n");
for(i=0; i
{
for(j=0; j
printf("%d ",result[i][j]);
printf("\n");
}
        printf("\n");
    }

    return 0;
}

运行结果：

（二）二分法 O(logE * N^3
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 50

typedef struct Matrix
{
int s[MAXN][MAXN];
}M;

//矩阵 a*b
M Multiply(M a, M b, int size)
{
int i,j,id;
M c;
memset(c.s,0,sizeof(c.s));
for(i=0; i<size; ++i)
for(j=0; j<size; ++j)
for(id=0; id<size; ++id)
c.s[i][j] += a.s[i][id] * b.s[id][j];
return c;
}

// src -- 源矩阵
// size -- 源矩阵阶数
// t -- t次方
M Pow(M src, int size, int t)
{
M d;
int i;
if(t==0)
{
memset(d.s, 0, sizeof(d.s));
for(i=0; i<size; ++i)
d.s[i][i]=1;
return d;
}
else
{
M des=Pow(src,size,t/2);
if(t&1) //t是奇数
return Multiply(Multiply(des,des,size),src,size);
else
return Multiply(des,des,size);
}
}


int main()
{
// 求n阶矩阵的k次方
int n,k,i,j;
while(scanf("%d%d",&n,&k) != EOF)
{
M a;
for(i=0; i<n; ++i)
for(j=0; j<n; ++j)
scanf("%d",&a.s[i][j]);
printf("a[n][n]:\n");
for(i=0; i<n; ++i)
{
for(j=0; j<n; ++j)
printf("%d ",a.s[i][j]);
printf("\n");
}
M matpow = Pow(a, n, k);
printf("matpow[n][n]:\n");
for(i=0; i<n; ++i)
{
for(j=0; j<n; ++j)
printf("%d ",matpow.s[i][j]);
printf("\n");
}
}
return 0;
}

运行结果：


喜欢

0

阅读┊ 收藏 ┊ 喜欢▼ ┊打印┊举报/Report
  

新浪BLOG意见反馈留言板　欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

Copyright © 1996 - 2022 SINA Corporation, All Rights Reserved

新浪公司 版权所有