矩陣相乘

一般會(huì)用O(n^3)的方法。。。配合剪枝【添?xiàng)l件，設(shè)門(mén)檻。。。】

//O(n^3)算法 #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> using namespace std; #define LL __int64 #define MOD 1000 typedef struct MATRIX { int mat[50][50]; }MATRIX; MATRIX mat_multiply (MATRIX a,MATRIX b,int n) { MATRIX c; //c[i][j]= Σ a[i][k]*b[k][j] memset(c.mat,0,sizeof(c.mat)); /* for(int i=0;i<n;i++) //a矩陣一行一行往下 for(int j=0;j<n;j++) //b矩陣一列一列往右 for(int k=0;k<n;k++) //使a矩陣 第i行第k個(gè)元素 乘以 b矩陣 第j列第k個(gè)元素 if(a[i][k] && b[k][j]) //剪枝（添?xiàng)l件，設(shè)門(mén)檻），提高效率，有一個(gè)是0，相乘肯定是0 c.mat[i][j]+=a.mat[i][k]*b.mat[k][j]; */ //上面也是可以的，但是下面的剪枝更好一些，效率更高一些，但是運(yùn)算順序有點(diǎn)難想通，，， //上面就是C[i][j]一次就求出來(lái)，下面就是每次c[i][j]求出一項(xiàng)【就是上面紅體字，每次各求一列】 for(int k=0;k<n;k++) //這個(gè)可以寫(xiě)到前面來(lái)， for(int i=0;i<n;i++) if(a.mat[i][k]) //剪枝：如果a.mat[i][k]是0，就不執(zhí)行了 for(int j=0;j<n;j++) if(b.mat[k][j]) //剪枝：如果b.mat[i][k]是0，就不執(zhí)行了 { c.mat[i][j]+=a.mat[i][k]*b.mat[k][j]; if(c.mat[i][j]>=MOD) //這個(gè)看實(shí)際需求，要不要取模 c.mat[i][j]%=MOD; //取模的復(fù)雜度比較高，所以盡量減少去模運(yùn)算，添加條件，只有當(dāng)大于等于MOD的時(shí)候才取余 } return c; } int main()<span style="white-space:pre"> </span>//這個(gè)只是用來(lái)測(cè)試用的。。。 { int n; MATRIX A,B,C; memset(A.mat,0,sizeof(A.mat)); memset(B.mat,0,sizeof(B.mat)); memset(C.mat,0,sizeof(C.mat)); scanf("%d",&n); //矩陣規(guī)模，這里是方陣，行數(shù)等于列數(shù) for(int i=0;i<n;i++) //初始化A矩陣 for(int j=0;j<n;j++) scanf("%d",&A.mat[i][j]); for(int i=0;i<n;i++) //初始化B矩陣 for(int j=0;j<n;j++) scanf("%d",&B.mat[i][j]); C=mat_multiply (A,B,n); for(int i=0;i<n;i++) //打印C矩陣 { for(int j=0;j<n;j++) printf("%3d",C.mat[i][j]); printf("\n"); } return 0; }

矩陣快速冪

//矩陣快速冪 #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> using namespace std; #define LL __int64 #define MOD 1000 typedef struct MATRIX { int mat[50][50]; }MATRIX; MATRIX mat_multiply (MATRIX a,MATRIX b,int n) { MATRIX c; //c[i][j]= Σ a[i][k]*b[k][j] memset(c.mat,0,sizeof(c.mat)); /* for(int i=0;i<n;i++) //a矩陣一行一行往下 for(int j=0;j<n;j++) //b矩陣一列一列往右 for(int k=0;k<n;k++) //使a矩陣 第i行第k個(gè)元素 乘以 b矩陣 第j列第k個(gè)元素 if(a[i][k] && b[k][j]) //剪枝（添?xiàng)l件，設(shè)門(mén)檻），提高效率，有一個(gè)是0，相乘肯定是0 c.mat[i][j]+=a.mat[i][k]*b.mat[k][j]; */ //上面也是可以的，但是下面的剪枝更好一些，效率更高一些，但是運(yùn)算順序有點(diǎn)難想通，，， //上面就是C[i][j]一次就求出來(lái)，下面就是每次c[i][j]求出一項(xiàng)【就是上面紅體字，每次各求一列】 for(int k=0;k<n;k++) //這個(gè)可以寫(xiě)到前面來(lái)， for(int i=0;i<n;i++) if(a.mat[i][k]) //剪枝：如果a.mat[i][k]是0，就不執(zhí)行了 for(int j=0;j<n;j++) if(b.mat[k][j]) //剪枝：如果b.mat[i][k]是0，就不執(zhí)行了 { c.mat[i][j]+=a.mat[i][k]*b.mat[k][j]; if(c.mat[i][j]>=MOD) //這個(gè)看實(shí)際需求，要不要取模 c.mat[i][j]%=MOD; //取模的復(fù)雜度比較高，所以盡量減少去模運(yùn)算，添加條件，只有當(dāng)大于等于MOD的時(shí)候才取余 } return c; } MATRIX mat_quick_index(MATRIX a,int N,int n) { MATRIX E; //單位矩陣，就像數(shù)值快速冪里，把代表乘積的變量初始化為1 // memset(E.mat,0,sizeof(E.mat)); //置零，單位矩陣除了主對(duì)角線都是1，其他都是0 // for(int i=0;i<n;i++) //初始化單位矩陣【就是主對(duì)角線全是1】 // E.mat[i][i]=1; for(int i=0;i<n;i++) for(int j=0;j<n;j++) E.mat[i][j]=(i==j); //酷炫*炸天的初始化！！！ while(N>0) { if(N & 1) E=mat_multiply(E,a,n); N>>=1; a=mat_multiply(a,a,n); } return E; } int main() { int n,N; //n為矩陣（方陣）規(guī)模，幾行，N為指數(shù) MATRIX A,C; memset(A.mat,0,sizeof(A.mat)); memset(C.mat,0,sizeof(C.mat)); scanf("%d",&n); //矩陣規(guī)模，這里是方陣，行數(shù)等于列數(shù) for(int i=0;i<n;i++) //初始化A矩陣 for(int j=0;j<n;j++) scanf("%d",&A.mat[i][j]); scanf("%d",&N); C=mat_quick_index(A,N,n); for(int i=0;i<n;i++) //打印C矩陣 { for(int j=0;j<n;j++) printf("%3d",C.mat[i][j]); printf("\n"); } return 0; }

總結(jié)

以上是生活随笔為你收集整理的矩阵乘法和快速幂的一些优化和剪枝的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。