TOP

矩阵乘法(七):其它一些典型应用(一)
2019-09-07 07:09:09 】 浏览:60
Tags:矩阵 乘法 其它 一些 典型 应用

? ? ? 前面几篇随笔中介绍了利用矩阵乘法(特别是应用快速幂运算)解决递推快速求值、置换和几何变换等问题的方法。实际上矩阵乘法的应用远不止这些,下面通过几个实例来介绍下矩阵乘法的其它一些典型的应用。

【例1】多少条道。

? ? ? 给定一个有向图,问从A点恰好走k步(允许重复经过边)到达B点的方案数mod p的值。

? ? ? (1)yabo体育app下载思路。

? ? ? 本题是矩阵乘法应用在图论中的一个典型方法。
? ? ? 给定了有向图,可以得到该图的邻接矩阵A,在邻接矩阵A中,A(i,j)=1当且仅当存在一条边i->j。若i->j不存在直接相连接的边,则A(i,j)=0。

? ? ? 令C=A*A,那么 C(i,j)= ΣA(i,k)*A(k,j),实际上就等于从点i到点j恰好经过2条边的路径数(k为中转点)。

? ? ? 类似地,C*A =A*A*A的第i行第j列就表示从i到j经过3条边的路径数。同理,如果要求经过k步的路径数,只需要采用快速幂运算求出A^k即可。

?

? ? ? (2)源程序。

#include
#include
#define MOD 1000
struct Matrix
{
? ? ? int mat[21][21]; // 存储矩阵中各元素
};
Matrix matMul(Matrix a ,Matrix b,int n,int m)
{
? ? ? Matrix c;
? ? ? memset(c.mat,0,sizeof(c.mat));
? ? ? int i,j,k;
? ? ? for (k = 1; k<=n ; k++)
? ? ? ? ? for (i=1 ;i<=n ; i++)
? ? ? ? ? ? ? ?if (a.mat[i][k]!=0)
? ? ? ? ? ? ? ? ? ? for (j = 1 ;j<=n ;j++)
? ? ? ? ? ? ? ? ? ? ? ? c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % m;
? ? ? return c;
}
Matrix quickMatPow(Matrix a ,int n,int b,int m) // n阶矩阵a快速b次幂
{
? ? ? Matrix c;
? ? ? memset(c.mat ,0 ,sizeof(c.mat));
? ? ? int i;
? ? ? for (i = 1 ;i <= n ;i++)
? ? ? ? ? ?c.mat[i][i] = 1;
? ? ? while (b!=0)
? ? ? {
? ? ? ? ? ? if (b & 1)
? ? ? ? ? ? ? ? c = matMul(c ,a ,n,m); // c=c*a;
? ? ? ? ? ? a = matMul(a ,a ,n,m); // a=a*a
? ? ? ? ? ? b /= 2;
? ? ? }
? ? ? return c;
}
int main()
{
? ? ? int n,m,s,t,nCase,a,b,k,i;
? ? ? Matrix p,ans;
? ? ? while (scanf("%d%d",&n,&m) && n+m!=0)
? ? ? {
? ? ? ? ? ? memset(p.mat,0,sizeof(p.mat));
? ? ? ? ? ? for (i=1;i<=m;i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? ?scanf("%d%d",&s,&t);
? ? ? ? ? ? ? ? ?p.mat[s+1][t+1]=1;
? ? ? ? ? ? }
? ? ? ? ? ? scanf("%d",&nCase);
? ? ? ? ? ? for (i=1;i<=nCase;i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? scanf("%d%d%d",&a,&b,&k);
? ? ? ? ? ? ? ? ? ans=quickMatPow(p,n,k,MOD);
? ? ? ? ? ? ? ? ? printf("%d\n" ,ans.mat[a+1][b+1]);
? ? ? ? ? ? ?}
? ? ? }
? ? ? return 0;
}

将此源程序提交给 HDU 2157 “How many ways??”,可以Accepted。

?

? ? ? ?我们知道,构造好平移、缩放或旋转的转换矩阵后,可以实现几何变换;构造好置换矩阵后,可以实现置换操作。这样,在一些问题中,我们也可以根据状态变化的情况,构造一个状态转移矩阵,来解决一些状态变换
矩阵乘法(七):其它一些典型应用(一) https://www.cppentry.com/bencandy.php?fid=49&id=250291

首页 上一页 1 2 3 下一页 尾页 1/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇IEEE浮点表示 (原发布 csdn 2018.. 下一篇c++ map容器使用及问题

kafka-
kafka ? Partit
解决android studio
Kafka史上最详细原理
Error while fetchin
【Kafka】安装与快速
? ? &
flume读取日志数据写
Authentication plug
Flume 自定义source
flume ? 三大核
ICC副本>>>
愚公移山 ?
Hbase架构 ? Hb
5 hbase-shell + &
Hbase ? MapRed
MetaException(messa
Exception in thread
HIVE metastore Dupl
-->