求行列式
作者:
实干者
,
2024-08-06 17:07:58
,
所有人可见
,
阅读 9
递归地按行列展开即可
算法:递归,状态压缩
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 64;
int g[N][N];
int n;
//dfs参数:行展开所在行的编号,行列子式阶数,子行列式所在列用二进制表示(防止先前已经展开的列再次被使用)
int dfs(int row,int grade,ll col_path) {
if (grade == 0) return 1;
int sum = 0,cnt = 0;
for (int j = 0; j < n;j ++ ) {
if ((col_path >> j & 1) == 0) {
sum += pow(-1,cnt) * g[row + 1][j] * dfs(row + 1,grade - 1,col_path + (1 << j));
cnt ++;
}
}
return sum;
}
int main()
{
//输入行列式的行列数和行列式本身
cin >> n;
for (int i = 0;i < n;i ++ )
for (int j = 0;j < n;j ++ )
cin >> g[i][j];
//计算并输出行列式的值
int res = 0;
for (int i = 0;i < n;i ++ ) {
int val = pow(-1,i) * g[0][i] * dfs(0,n - 1,1 << i);
res += val;
}
cout << "=> value of determinant equal :" << res << '\n';
return 0;
}