线性代数行列式求值（史上最详细！）

介绍一下用行列式的定义求行列式值的程序，虽然时间复杂度是O(n!)，但是用于平时的学习的话是完全ok的。

另外就是，如果想在课上算答案，而又不能在课上玩电脑的话，可以下载手机编程软件计算，比如 C4droid ，具体安装方法自己去百度搜一下~

好了，废话不多说，开始讲解代码~~

首先来复习一下行列式求值的方法~
假定一个行列式为n阶的行列式，求这个行列式的值，行列式的每一项都有一个行坐标，一个列坐标，假定行坐标是从0~n-1排列的，然后枚举每种列坐标的排列情况，也就是生成一个列坐标为
0~n-1的全排列。然后判断每一个排列的逆序数，从而确定每一项的正负。

例如，当n=3时
a（0，0） 	a（0，1）	a（0，2）
a（1，0）	a（1，1）	a（1，2）
a（2，0）	a（2，1）	a（2，2）
首先按照行数选，先选第一行，比如选了坐标为（0，1）的元素，
然后选择第二行的元素，选第二行的时候第第2列的元素已经在第一行选过了，
所以只能选择a（1，0）或a（1，2），比如选了a（1，0）
最后选第三行的元素，这时第一列和第二列都已经选过了，所以只能选a（2，2）
这种情况下选出来的元素就是a（0，1）a（1，0）a（2，2）因为列数的排列是102，1前面没有比它大的数
0前面有1个，2前面也没有比它大的数，所以这个排列的逆序数就是1，1是奇数，所以这个排列的系数是-1
按照这种方法算出整个排列所有的项，结果为：
 a（0，0）*a（1，1）*a（2，2）-a（0，0）*a（1，2）*a（2，1）
-a（0，1）*a（1，0）*a（2，2）+a（0，1）*a（1，2）*a（2，0）
+a（0，2）*a（1，0）*a（2，1）-a（0，2）*a（1，1）*a（2，0）

终于复习完了~
开始写代码吧~
要想完成代码很简单，只需要三步，
第一步，把冰箱门打开，第二步，把大象塞进去，第三步，关上冰箱门。
第一步，求出0~n的全排列，求全排列可以用dfs，如果你不会dfs也不要紧，接下来我会教你怎么用（因为这里规定从行坐标是从0一直到n的顺序枚举，所以只需要生成列坐标的全排列）
第二步，求出每个全排列对应的元素的积
第三步，求出每个全排列的逆序数，判断每一项的正负，然后把所有的项加起来

（一）求n个数的全排列：
有0~n-1这n个元素，因为学习中计算的行列式阶数肯定不会很多，所以这里可以用一个pos变量的二进制形式做标记（英语贼菜，命名都是瞎命，见谅哈 ~），pos的二进制的形式中的每一位要么是0要么是1，0表示这个元素还没有取过，1表示这个元素已经取过了。

这里先介绍一下异或（^）运算符，异或的运算是这样的 0 ^ 0 =0 ，0 ^1 =1，1 ^0 =1 ，1 ^ 1=0，相同就是0，不同就是1，另外就是，异或也叫不进位加法，0+0=0，所以结果就是0，0+1=1，所以结果就是1，1+0=1，所以结果就是1，1+1=2(十进制)=10(二进制)，因为1+1需要进位，但是根据不进位加法的意思，这里就把进位后的那个1直接删掉了，所以结果就是0。

介绍完异或，下面就有介绍重点的操作了！！
如何把pos的第i位从0变成1或者从1变成0 ？

如果是只有一位 0 ^ 1=1 ，1 ^ 1=0 这样就可以实现0转化为1，1转化为0，但是如果pos有很多位就不能通过直接异或1了，
比如00010100 要想把这个1变成0改怎么办呢？
其实很简单，直接异或00010000就行了，来对应每一位看一下 ~ 异或结果应该是00000100
如果想把这个0再变回1呢？该怎么操作？讲到这里这个地方应该难不住你了吧 ~，请自己思考一下 ~

说好的介绍dfs。。光介绍怎么标记就说了这么多，好了，不说废话了 ~直接开始吧 ~

首先 dfs里面需要一个参数（sum），表示当前已经选了几个数，当选的数等于n个的时候就可以把这个排列对应的元素的积求出来加到用来存答案的变量里去了 ~
当sum小于n个的时候就需要选一个没有被选过的数字加到数组（book）中，这个数组用来存加入的每个元素的顺序。

void dfs(int sum)
{
    if(sum==n)//当选够n个数的时候计算结果然后return
    {
        int s=1;//用来存这种排列的每个元素的积
        //循环一次，求出对应元素的积，注意看a的两个下标！
        for(int i=0;i<n;i++) s*=a[i][book[i]];
        //nx()是需要自己实现的一个函数，当逆序数为奇数时返回-1，否则返回1，
        //把s加上正负号后在加到ans中去当所有的排列都加进去之后ans就是最终答案了
        ans+=nx()*s;
        return;
    }
    for(int i=0;i<n;i++)
    {
  		//pos>>i表示把pos的二进制码右移i位，所以pos>>i&1就可以判断pos的第i位是否是1了
  		//如果是1说明i这个数已经加入到排列中去了，所以就直接continue，否则的话，先把
  		//这位标记成1，然后把这个数加入到book中去，递归计算sum+1的结果
        if(pos>>i&1) continue;
        pos=pos|1<<i;
        book[sum]=i;
        dfs(sum+1);
        pos=pos^1<<i;//敲黑板！！！这里一定要好好理解一下！！！把第i为标记成1后还要再标记成0
                    //否则的话就不能继续往后枚举了！！
    }
}

终于讲完dfs了 ~

（二）逆序数的求法
这里介绍一种最暴力的求法，也是最简单的求法（求全排列的时间复杂度已经到O(n!)了，求逆序数的时间复杂度再高也对总体的时间基本没影响了~）

求逆序数的思路就是，枚举0~n-1的每一个元素，然后判断每个元素前面分别有几个比它大的元素，最后把这些数求和。

直接上代码~

int nx()
{
    int sum=0;//用来存放逆序数
    for(int i=0;i<n;i++)//枚举每一个元素
    {
        for(int j=0;j<i;j++)//找出第i个元素前面有几个比它大的元素
        {
            if(book[j]>book[i]) sum++;//没找到一个说明多了一个逆序数，所以sum+1
        }
    }
    if(sum&1) return -1;//如果是奇数就返回-1
    return 1;
}

上完整代码~

#include<cstdlib>
#include<iostream>
using namespace std;
int a[50][50];
int book[50];
int n,ans,pos;
int nx()
{
    int sum=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(book[j]>book[i]) sum++;
        }
    }
    if(sum&1) return -1;
    return 1;
}
void dfs(int sum)
{
    if(sum==n)
    {
        int s=1;
        for(int i=0;i<n;i++) s*=a[i][book[i]];
        ans+=nx()*s;
        return;
    }
    for(int i=0;i<n;i++)
    {
        if(pos>>i&1) continue;
        pos=pos|1<<i;
        book[sum]=i;
        dfs(sum+1);
        pos=pos^1<<i;
    }
}
int main()
{
    while(1)
    {
        pos=0;
        ans=0;
        printf("请输入行列式的阶数\n");
        cin>>n;
        printf("请输入行列式\n");
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>a[i][j];
            }
        }
        dfs(0);
        cout<<ans<<endl;
        getchar();
        getchar();
        system("CLS");
    }
    return 0;
}