首页 > > 程序设计 > C/C++ >

矩阵（+ - *）

2018-07-17 03:56:29来源：博客园阅读 ()

前言：用数组描述矩阵，下标可以从0开始，也可以从1开始，根据需要来定。

PS:矩阵的本质就是线性方程式！

下面我们来介绍几种矩阵类型：

N阶矩阵（同型矩阵）：横纵个数相同

行矩阵：一行的那种

列矩阵：一列的那种

单位矩阵（高斯消元法中体现）：如同乘法中的单位1（如下所示）

1 0 0

0 1 0

0 0 1

一、矩阵加法（必须是同型矩阵）

满足

a+b=b+a

（a+b）+c=a+(b+c)

例：

二、矩阵减法（同样必须是同型矩阵，基本上和矩阵加法相同）

本质就是矩阵的对应的位置相加减即可。是不是很容易呢？哈哈，别高兴，这只是一个开端......

三、矩阵乘法（必须是同型矩阵）

诡异的意义：

试想这样一个场景,你坐在空调屋里，吃着西瓜，玩着手机，你妈见状，非常无语，就让你下楼买酱油。

你领了钱，屁颠屁颠的踏上了一条“不归路”.......

走进一家商店，你发现这里的酱油搞促销，2块5瓶，1块3瓶，你决定采用矩阵的形式进行计算。

算完后你觉得不能在一条树上吊死，那就脚踏两条船吧！qwq.....

你去了隔壁老王家的店，老王不在家，只有他的儿子在店里，小王告诉你2块1瓶，3块2瓶，身为公认的小天才的你同样运用矩阵的形式进行计算。

计算后，你发现老王家的店太坑了，互为邻居也不便宜点儿，你气急败坏的转身欲走，这时老王回来了，你告诉了他小王的“所作所为”，老王大为头痛，并且告诉你，全都是泡沫，一切都是假象，你愤怒的告诉了老王第一家店的价钱，老王对你非常无语，因为第一家店正是老王家的分店，为了维护好邻里关系，老王决定，你可以根据这两家店的优惠活动来决策出一种最便宜的方案。身为小天才的你，轻松找到了最便宜的方案。看着小王拿酱油的身影，你身心畅快（毕竟剩下的钱你可以为所欲为）。

回到家后，你原以为你妈会表扬你的勤俭节约。但是母上大人却大发脾气，此时委屈的你发现带回来的竟然是——老陈醋！！！（真是日了狗了）

我们管这种从材料的数量及价格转换为总花费的过程叫做一个线性映射。

看到这里，相信你对矩阵乘法已经有了初步的一个认识。

矩阵乘法规则：

矩阵的第m行与第n列交叉位置的那个值，等于第一个矩阵第m行与第二个矩阵第n列，对应位置的每个值的乘积之和。

通俗点来讲就是：第一个矩阵第一行的每个数字，各自乘以第二个矩阵第一列对应位置的数字，然后将乘积相加，得到的结果即为矩阵左上角的那个值。

为什么要这样计算呢？详细讲解：

http://www.ruanyifeng.com/blog/2015/09/matrix-multiplication.html

（毕竟这是关于数学上的证明，跟信息学本身并没有多大关系，可不掌握，记住结论即可）

让我们看一个完整的矩阵乘法计算吧！

因数交换一下可以吗？

答案是不可以！！矩阵乘法必须是第一个矩阵的行与第二个矩阵的列的乘积，上面的式子不满足这一点，所以错误。（只有两个矩阵相乘时）

所以乘法并不满足交换律~

又到了代码实现时间了，“铛铛铛铛”......

#include<iostream>
using namespace std;
int a[20][20],b[20][20],c[20][20];
int main()
{
    int m,n,s;
    cin>>m>>s>>n;
    for(int i=0;i<m;i++)
        for(int j=0;j<s;j++)
            cin>>a[i][j];
    for(int i=0;i<s;i++)
        for(int j=0;j<n;j++)
            cin>>b[i][j];
    for(int i=0;i<m;i++)
    {    
        for(int k=0;k<n;k++)
        {
            for(int j=0;j<s;j++)
            {
                c[i][k]+=a[i][j]*b[j][k];
            }
        }
    }
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(j!=n-1)
                cout<<c[i][j]<<" ";
            else
                cout<<c[i][j]<<endl;
        }
    }    
    return 0;
        
}

三层for循环，你值得拥有！

PS;矩阵没有除法

矩阵快速幂推荐博客：

https://www.cnblogs.com/cmmdc/p/6936196.html

https://blog.csdn.net/flushhip/article/details/80068888

高斯消原法推荐博客：

https://blog.csdn.net/pengwill97/article/details/77200372

https://www.luogu.org/problemnew/solution/P3389

https://wenku.baidu.com/view/5b1ab0e40066f5335b812188.html

Happy ending！

TIP

高斯消元法可以求得n元一次方程的解。
整数快速幂的时间复杂度是O（log2N），而矩阵快速幂的时间复杂度是O（log（n））

特别注意：

满足 $A$

$A$

$A$ $A$

$A$

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int M = 1e9+7;
struct Matrix {
    long long a[2][2];
    Matrix() {
        memset(a, 0, sizeof(a));
    }
    Matrix operator * (const Matrix y) {
        Matrix ans;
        for(int i = 0; i <= 1; i++)
            for(int j = 0; j <= 1; j++)    
                for(int k = 0; k <= 1; k++)    
                    ans.a[i][j] += a[i][k]*y.a[k][j];
        for(int i = 0; i <= 1; i++)
            for(int j = 0; j <= 1; j++)
                ans.a[i][j] %= M;
        return ans;
    }
    void operator = (const Matrix b) {
        for(int i = 0; i <= 1; i++)
            for(int j = 0; j <= 1; j++)
                a[i][j] = b.a[i][j];
    }
};
 
int solve(long long x) {
    Matrix ans, trs;
    ans.a[0][0] = ans.a[1][1] = 1;
    trs.a[0][0] = trs.a[1][0] = trs.a[0][1] = 1;
    while(x) {
        if(x&1) 
            ans = ans*trs;
        trs = trs*trs;
        x >>= 1;
    }
    return ans.a[0][0];
}
 
int main() {
    int n;
    scanf("%d", &n);
    cout << solve(n-1) << endl;
    return 0;
}

//高斯消元法解方程组(Gauss-Jordan elimination).
// (-2表示有浮点数解，但无整数解，-1表示无解，0表示唯一解，大于0表示无穷解，并返回自由变元的个数)
//增广矩阵行数为equ,分别为0到equ-1,列数为var+1,分别为0到var.
    #include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    using namespace std;
    const int MAXN=50;
    int a[MAXN][MAXN];//增广矩阵
    int x[MAXN];//解集
    bool free_x[MAXN];//标记是否是不确定的变元
    int gcd(int a,int b)//求最大公因数 
    {
        if(b==0) 
        return a;
        else 
        return gcd(b,a%b);
    }
    inline int lcm(int a,int b)//求出最小公倍数 
    {
        return a/gcd(a,b)*b;//先除后乘防溢出
    }
    int Gauss(int equ,int var){
        int i,j,k;
        int max_r;// 当前这列绝对值最大的行.
        int col;//当前处理的列
        int ta,tb;
        int LCM;
        int temp;
        int free_x_num;
        int free_index;
        for(int i=0;i<=var;i++)
        {
            x[i]=0;
            free_x[i]=true;
        }//转换为阶梯阵.
        col=0; // 当前处理的列
        for(k=0;k<equ&&col<var;k++,col++)//上面有解释 
        {
        // 枚举当前处理的行.
        // 找到该col列元素绝对值最大的那行与第k行交换.(为了在除法时减小误差)
            max_r=k;
            for(i=k+1;i<equ;i++)
            {
                if(abs(a[i][col])>abs(a[max_r][col])) 
                max_r=i;
            }
            if(max_r!=k)
            {// 与第k行交换.
                for(j=k;j<var+1;j++) 
                swap(a[k][j],a[max_r][j]);
            }
            if(a[k][col]==0)
            {// 说明该col列第k行以下全是0了，则处理当前行的下一列.
                k--;
                continue;
            }
            for(i=k+1;i<equ;i++)
            {// 枚举要删去的行.
                if(a[i][col]!=0)
                {
                    LCM=lcm(abs(a[i][col]),abs(a[k][col]));
                    ta=LCM/abs(a[i][col]);
                    tb=LCM/abs(a[k][col]);
                    if(a[i][col]*a[k][col]<0)tb=-tb;//异号的情况是相加
                    for(j=col;j<var+1;j++)
                    {
                        a[i][j]=a[i][j]*ta-a[k][j]*tb;
                    }
                }
            }
        }
// 1. 无解的情况: 化简的增广阵中存在(0, 0, ..., a)这样的行(a != 0).
        for (i=k;i<equ;i++)
        { 
// 对于无穷解来说，如果要判断哪些是自由变元，那么初等行变换中的交换就会影响，则要记录交换.
            if (a[i][col]!=0) 
            return -1;
        }
// 2. 无穷解的情况: 在var * (var + 1)的增广阵中出现(0, 0, ..., 0)这样的行，即说明没有形成严格的上三角阵.
// 且出现的行数即为自由变元的个数.
        if (k<var)
        {
            return var-k; // 自由变元有var - k个.
        }
// 3. 唯一解的情况: 在var * (var + 1)的增广阵中形成严格的上三角阵.
// 计算出Xn-1, Xn-2 ... X0.
        for (i=var-1;i>=0;i--)
        {
            temp=a[i][var];
            for (j=i+1;j<var;j++)
            {
                if (a[i][j]!=0) temp-=a[i][j]*x[j];
            }
            if (temp%a[i][i]!=0) 
            return -2; // 说明有浮点数解，但无整数解.上面提到过 
            x[i]=temp/a[i][i];
        }
        return 0;
    }
    int main(void)
    {
    //    freopen("in.txt", "r", stdin);
    //    freopen("out.txt","w",stdout);
        int i, j;
        int equ,var;//有equ个方程，var个变元。
        while (scanf("%d %d",&equ,&var)!=EOF)
        {
            memset(a,0,sizeof(a));
            for (i=0;i<equ;i++)
            {
                for (j=0;j<var+1;j++)
                {
                    scanf("%d",&a[i][j]);
                }
            }
            int free_num=Gauss(equ,var);
            if (free_num==-1) 
            printf("无解!\n");
            else if (free_num == -2) 
            printf("有浮点数解，无整数解!\n");
            else if (free_num > 0)
            {
                printf("无穷多解! 自由变元个数为%d\n", free_num);
                for (i=0;i<var;i++)
                {
                    if (free_x[i]) printf("x%d 是不确定的\n", i + 1);
                    else printf("x%d: %d\n",i+1,x[i]);
                }
            }else
            {
                for (i=0;i<var;i++)
                {
                    printf("x%d: %d\n",i+1,x[i]);
                }
            }
            printf("\n");
        }
        return 0;
    }