c++算法：计算行列式的值（详细讲解）

参考了：

需要的基础：学过《线性代数》，知道⾏列式值的求法基本公式：对于如下的⾏列式：

其值为：

相信⼤家都懂这个公式的具体含义，我就不解释了，不懂的同学百度⼀下⾏列式分析⼀个这个公式该如何实现：

假定现有有⼀个3*3的⾏列式，则其计算公式为：

观察这个式⼦，可以发现其有⼀个核⼼，那就是⽣成⼀个全排列。本例中是⼀个3*3矩阵，因此需要⽣成123的全排列，共有六个：123、132、213、231、321、312。然后就是要计算，⽣成的排列的逆序数，即

总结起来可分为如下⼏步：

1、求出给定n阶矩阵的全排列，我⽤vector存储⼀个全排列（即上例中6个全排列中的某⼀个），⽤vector >存储所有的全排列（即上例中的六个全排列）。2、计算排列的逆序数。

3、分别以1，2...n为row值，从vector中依次提取的值为col值，组成⾏列式中元素的下标，然后相乘4、求和。

算法实现：

1、求全排的算法如下，不懂该算法的可以移步：

//交换元素

void swap(vector& vec, int i, int j){

int temp = vec[i]; vec[i] = vec[j]; vec[j] = temp;}

//第⼀个参数表⽰初始的数列，在上例中，该vec中的元素为1，2，3//第⼆个参数表⽰最终得到的全排列集合

void Perm(vector& vec, vector >& vec_seq, int current_index = 0){

if (current_index == ((int)vec.size() - 1)) {

vec_seq.push_back(vec); } else {

for (int i = current_index; i < (int)vec.size(); i++) {

swap(vec, i, current_index);

Perm(vec, vec_seq, current_index + 1); swap(vec, i, current_index); } }}

　当然，还得有⼀个⽣成初始数列的函数

//根据n⽣成⼀个初始vectorvector inivec(int n){

vector vec;

for (int i = 0; i < n; i++) vec.push_back(i); return vec;}

　第⼆步：求出全排列的逆序数，判断逆序数的奇偶

//得出排列的逆排序数，并根据奇偶判读正负

bool Iseven(int num){

//⽤位与运算来判断奇偶（最快的判断奇偶的⽅法） return ((num & 1) == 0);}

//是否幂为正

bool PowerIsPosition(vector& vec){

//count即为逆序数，初始化为0 int count = 0;

for (int i = 0; i < (int)vec.size(); i++) {

for (int j = i + 1; j < (int)vec.size(); j++) {

if (vec[i] > vec[j]) {

count += 1; } } }

return (Iseven(count));}

　　第三步和第四步：

//计算结果

//第⼀个参数表⽰输⼊的⾏列式

//第⼆个参数表⽰该⾏列式的阶数，在本例中n = 3，即⼀个3*3的⾏列式int calculate(int** array, int n){

vector > vec_que; vector vec = inivec(n); vector vec_elem; Perm(vec, vec_que); //最终结果，初始化为0 int result = 0;

//依次为vec_que中取出⾏列式

for (int i = 0; i < (int)vec_que.size();i++) {

vec_elem = vec_que[i];

//mi即为前⾯(-1)的n次幂，最后结果为-1或者1 int mi = PowerIsPosition(vec_elem) ? 1 : (-1); int temp = mi;

//row号初始化为0之后依次加1 int row = 0;

//col号依次从vec_elem中取出

for (int j = 0; j < (int)vec_elem.size();j++) {

int col = vec_elem[j];

temp *= array[row++][col]; }

result += temp; }

return result; }

　　检验⼀下：

int main(){

int** array = new int*[3]; for (int i = 0; i < 3; i++) {

array[i] = new int[3]; }

array[0][0] = 2; array[0][1] = -4; array[0][2] = 1; array[1][0] = 1; array[1][1] = -5; array[1][2] = 3; array[2][0] = 1; array[2][1] = -1; array[2][2] = 1;

int result = calculate(array, 3); return 0;}

　　计算的result = -8，结果正确