牛客网

编程初学者入门训练

BC105 矩阵相等判定

思路：

分为四步。根据题意我们知道两个矩阵的行和列都是一样的，所以第一步定义所需的变量，分别是两个二维数组（因为n和m最大值为10，所以二维数组的行和列都为10），输入的行和列数，以及循环要用的两个变量，和标记变量（初值我赋为1）；第二步为实现输入第一个二维数组的变量，两个循环的条件分别是小于行和列；第三步为实现输入第二个二维数组的变量，两个循环的条件分别也是小于行和列，但是我们要随便判断下是否跟第一个二维数组一样，如果在输入并判断的过程中出现不同，则将标记变量改为0；第四步就是根据上面的标记变量作出判断输出，引用if,else语句，如果标记变量还是1就输出Yes，不然就是No。

代码实现如下：

备注：上述题目来源于牛客网，网址是https://www.nowcoder.com/ta/beginner-programmers，本人才疏学浅，如有问题，欢迎各位大佬们指证改出。感谢各位老铁们的支持！

题目链接：

上三角矩阵判定_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/f5a29bacfc514e5a935723857e1245e4?tpId=107&difficulty=&judgeStatus=&tags=&title=106&gioEnter=menu

解题思路：

1.要用到嵌套 for 循环

2. 内层循环的判断条件是外层循环的层数

3. 注意外层循环的初始值

答案代码：

#include <stdio.h>
int main ()
{
    int data = 0;
    scanf("%d\n",&data);
    int arr[10][10] = {0};
    int i = 0;
    for (i = 0;i < data;i++)
    {
        int j = 0;
        for (j = 0;j < data;j++)
        {
            scanf("%d ",&arr[i][j]);
        }
    }                 //数据输入
    
    int m = 0;
    int change = 0;
    for (m = 1;m < data;m++) //注意m的初始值
    {
            int n = 0;
        for (n = 0;n < m;n++)
        {
            if (arr[m][n] != 0)
            {
                printf("NO");
                return 0; 
            }
            else
                change = 1;
        }
     }
        if (change == 1)  //这一段代码必须在外层循环的外面
        printf("YES");    
        
    
    
    return 0;
}

前言：

        上一篇文章中，我们探讨了矩阵的秩与可逆矩阵的判定方法，我提到将说出下一种判断矩阵是否可逆的方法，这篇文章就跟大家探讨一下。

一、线性代数知识回顾：

1.  排列：由1,2,···,n 这n个数组成的有序的数组就是一个 n 阶排列

2.  逆序数：在一个排列中，如果有两个数 a 和 b,若满足 a 在 b 的前面，且 a 大于 b ，那么它称为一个逆序，一个排列的所有逆序的个数称为逆序数。

记 为一个 n 阶排列，记 为该排列的逆序数

3.  行列式：对于一个 n 阶方阵  ，记  或  为  的行列式，它的定义如下：

 等于所有取自不同行不同列的 n 个元素的乘积

的代数和，记  是 1,2,···,n 的一个排列，行列式的定义可写为：

 

 有了定义后，我们固然是可以写出代码计算行列式的，我们可以看到行列式的计算需要找到所有的取自不同行不同列的元素乘积，如果需要代码实现，那么我们需要找到 n 阶排列的所有情况（n   阶全排列），而 n 阶全排列总共有 n ! 个，当矩阵比较大时，我们的程序就需要执行很多次，相当耗费时间。因此，我们不这样求解行列式。我们给出另外一种方法求解行列式，这需要以下线性代数知识：

4.  定理：

交换行列式两行，行列式反号

把一行的倍数加到另一行，行列式不变

5.  上三角行列式：主对角线以下元素为 0 的行列式，上三角行列式的值等于主对角线元素的成绩。设   为上三角行列式，则：

也就是说，将行列式通过上面第 4 条定理所说的两条化为上三角行列式，记录交换行列式两行的次数，然后通过第 5 条就可以求解出行列式的值了，这样做可以处理较大阶的行列式！下面再给出一个定理说明可逆与行列式的关系：

6.  定理：

矩阵可逆的充要条件是它的行列式不等于零

有了这个定理，我们就可以给出第二个判断矩阵是否可逆的方法了！

二、算法设计：

1.  求解行列式：（与我写的第二篇文章将矩阵化为上三角矩阵十分相似，没看过第二篇文章的伙伴们可以点击这个链接：

线性代数代码实现（二）上三角矩阵（C++）_AI研究者的博客-CSDN博客）

在将矩阵化为上三角矩阵的算法中增加三条：

1）令 result = 1，每次交换不同的两行时，执行 result = -result

2）在外层循环最后执行 result*=mat[i][i]，计算上三角矩阵主对角线元素的乘积，并判断result是否为零，若果为零，则说明行列式为零，则退出循环，若不为零，则继续循环

3）循环结束后，执行 result*=mat[m][n] ，乘上主对角线最后一个元素（这里 m = n），返回result

2.  判断矩阵是否可逆：

如果矩阵不是方阵，则不可逆，否则计算出行列式的值， 如果不为零，则矩阵可逆（非奇异），否则，矩阵不可逆（奇异）

三、代码实现：

类的定义：

class Mat
{
public:
	int m = 1, n = 1; //行数和列数
	double mat[N][N] = { 0 };  //矩阵开始的元素

	Mat() {}
	Mat(int mm, int nn)
	{
		m = mm; n = nn;
	}
	void create();//创建矩阵
	void copy(Mat& a);//复制

	double det();//计算行列式
	bool judgeinv();//判断矩阵是否可逆
};

 det()函数求解矩阵的行列式：

double Mat::det()
{
	if (m != n)
	{
		cout << "不是方阵，无行列式" << endl;
		exit(1);
	}
	Mat a; copy(a);
	double result = 1;
	for (int i = 1; i < m; i++)
	{
		//寻找第 i 列不为零的元素
		int k;
		for (k = i; k <= m; k++)
		{
			if (fabs(mat[k][i]) > 1e-10) //满足这个条件时，认为这个元素不为0
				break;
		}
		if (k <= m)//说明第 i 列有不为0的元素
		{
			if (k != i)//说明需要交换不同的两行
			{
				//交换第 i 行和第 k 行所有元素
				for (int j = i; j <= n; j++)//从第 i 个元素交换即可，因为前面的元素都为0
				{//使用mat[0][j]作为中间变量交换元素
					mat[0][j] = mat[i][j]; mat[i][j] = mat[k][j]; mat[k][j] = mat[0][j];
				}
				result = -result;
			}
			double a;//倍数
			for (int j = i + 1; j <= m; j++)
			{
				a = -mat[j][i] / mat[i][i];
				for (k = i; k <= n; k++)
				{
					mat[j][k] += a * mat[i][k];//第 i 行 a 倍加到第 j 行
				}
			}
		}
		result *= mat[i][i];
		if (fabs(result) < 1e-10) //如果为零，则已经可以说明行列式为零了，没必要继续算下去了
			break;
	}
	result *= mat[m][n];
	return result;
}

judgeinv()函数判断矩阵是否可逆：

bool Mat::judgeinv()
{
	if (m != n)//不是方阵，不可逆
		return false;
	if (fabs(det()) > 1e-10)//行列式不等于 0
		return true;
	else
		return false;
}

有兴趣的同学也可以自己利用定义做一做求解行列式的函数，主要难点在于如何知道全排列，有兴趣的同学可以想一想。计算行列式当然也有其他方法，这篇文章中介绍的方法算是比较好的方法，大家也可以研究其他方法，同样，判断矩阵是否可逆也有其他方法，大家也同样可以研究研究。包括线性代数的知识，大家都可以仔细思考，实际上线性代数的很多知识都有很好的几何意义，例如我们讲过的矩阵乘法，行列式计算等都是有十分好的几何意义，大家可以去理解理解。（悄悄告诉大家：n 阶矩阵的行列式的绝对值实际上就是 n 维空间中平行多面体的体积）这里附上完整代码：

#include<iostream>
#include <cmath>
#define N 10
using namespace std;
class Mat
{
public:
	int m = 1, n = 1; //行数和列数
	double mat[N][N] = { 0 };  //矩阵开始的元素

	Mat() {}
	Mat(int mm, int nn)
	{
		m = mm; n = nn;
	}
	void create();//创建矩阵
	void copy(Mat& a);//复制

	double det();//计算行列式
	bool judgeinv();//判断矩阵是否可逆
};

void Mat::create()
{
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> mat[i][j];
		}
	}
}
void Mat::copy(Mat& a)//复制函数
{
	a.m = m; a.n = n;
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			a.mat[i][j] = mat[i][j];
		}
	}
}
double Mat::det()
{
	if (m != n)
	{
		cout << "不是方阵，无行列式" << endl;
		exit(1);
	}
	Mat a; copy(a);
	double result = 1;
	for (int i = 1; i < m; i++)
	{
		//寻找第 i 列不为零的元素
		int k;
		for (k = i; k <= m; k++)
		{
			if (fabs(mat[k][i]) > 1e-10) //满足这个条件时，认为这个元素不为0
				break;
		}
		if (k <= m)//说明第 i 列有不为0的元素
		{
			if (k != i)//说明需要交换不同的两行
			{
				//交换第 i 行和第 k 行所有元素
				for (int j = i; j <= n; j++)//从第 i 个元素交换即可，因为前面的元素都为0
				{//使用mat[0][j]作为中间变量交换元素
					mat[0][j] = mat[i][j]; mat[i][j] = mat[k][j]; mat[k][j] = mat[0][j];
				}
				result = -result;
			}
			double a;//倍数
			for (int j = i + 1; j <= m; j++)
			{
				a = -mat[j][i] / mat[i][i];
				for (k = i; k <= n; k++)
				{
					mat[j][k] += a * mat[i][k];//第 i 行 a 倍加到第 j 行
				}
			}
		}
		result *= mat[i][i];
		if (fabs(result) < 1e-10) //如果为零，则已经可以说明行列式为零了，没必要继续算下去了
			break;
	}
	result *= mat[m][n];
	return result;
}
bool Mat::judgeinv()
{
	if (m != n)//不是方阵，不可逆
		return false;
	if (fabs(det()) > 1e-10)//行列式不等于 0
		return true;
	else
		return false;
}

int main()
{
	Mat a(3, 3);
	cout << "请输入 " << a.m << "*" << a.n << " 的矩阵：" << endl;
	a.create();
	cout << "矩阵的行列式为：  " << a.det() << endl;
	if (a.judgeinv())
		cout << "可逆！" << endl;
	else
		cout << "不可逆！" << endl;
	return 0;
}

若有不足之处，欢迎大家指正！