行列式計算（編程實現） - acm1314－IT工程師數位筆記本

文章出處

Write programs that do one thing and do it well

----- Doug McIlroy (UNIX哲學）

如果你學過線代，又恰巧你是個coder，那么你應該寫個計算行列式的program。

計算行列式（數學知識）：

每行都按行坐標排序，求出列坐標排列的逆序數

根據逆序數的奇偶行判斷該項的正負（奇負，偶正）

逐項求和。

說明：輸入行列式的行（列）數 N

并依次輸入n*n個數。程序將輸出

行列式的計算算式，并得出結果！

代碼實現分析：調用頭文件<algorithm>里的庫函數 next_permutation() 具體實現細節詳見代碼。

用線段樹求逆序數時間復雜度為N*logN。當然以這種時間復雜度的算法還有樹狀數組求逆序數，歸并排序求逆序數。

當然你也可以用直接暴力的方法求出逆序數，代碼是十分簡單的。時間復雜度和插入排序相同n*n。

然后就是具體的一些實現細節啦

線段樹求逆序數，代碼有點長。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

void PushUp(int cur, int *sum)
{
    sum[cur] = sum[cur<<1]+sum[cur<<1|1];
}

void Build(int l, int r, int cur, int *sum)
{
    sum[cur] = 0;
    if(l==r) return ;
    int m = (l+r)>>1;
    Build(l, m, cur<<1, sum);
    Build(m+1, r, cur<<1|1, sum);
}

void Update(int p, int l, int r, int cur, int *sum)
{
    if(l==r)
    {
        sum[cur]++;
        return;
    }
    int m = (l+r)>>1;
    if(p<=m) Update(p, l, m, cur<<1, sum);
    else Update(p, m+1, r, cur<<1|1, sum);
    PushUp(cur, sum);
}
int Query(int L, int R, int l, int r, int cur, int *sum)
{
    if(L<=l&&r<=R)
    {
        return sum[cur];
    }
    int m = (l+r)>>1;
    int ret = 0;
    if(L<=m) ret+=Query(L, R, l, m, cur<<1, sum);
    if(R>m) ret+=Query(L, R, m+1, r, cur<<1|1, sum);
    return ret;
}

int Reverse(int n, int *p)
{
    int sum[n<<2];
    Build(0, n-1, 1, sum);
    int tot = 0;
    for(int i=0; i<n; i++)
    {
        tot+=Query(p[i], n-1, 0, n-1, 1, sum);
        Update(p[i], 0, n-1, 1, sum);
    }
    return tot;
}

void solve(int n, int a[15][15])
{
    int flag = 0; 
    long long ans=0;
    int p[15];
    for(int i=0; i<n; i++) 
    p[i] = i+1;
    do
    {
        int ok = Reverse(n, p);
        if(ok&1) 
        {
            flag++;
           printf(" - ");
            long long temp=1;
            for(int j=1, i=0; i<n; j++, i++)
            {
                temp*=(long long)a[j][p[i]];
                if(j!=1)printf(" * ");
                printf("%d", a[j][p[i]]);
                
            }
            ans-=temp;
        }
        else 
        {
           if(flag)printf(" + ");
           flag++;
             long long temp=1;
            for(int j=1, i=0; i<n; j++, i++)
            {
                temp*=(long long)a[j][p[i]];
                if(j!=1)printf(" * ");
                printf("%d", a[j][p[i]]);
            }
            ans+=temp;
        }
    }while(next_permutation(p, p+n));
    printf("\n%d\n\n", ans);
}

int main() {
  int n;
  int a[15][15];
  while(scanf("%d", &n)!=EOF)
  {
      for(int i=1; i<=n; i++)
      for(int j=1; j<=n; j++)
      scanf("%d", &a[i][j]);
    solve(n, a);
  }
  return 0;
}

View Code

歸并排序求逆序數：

歸并排序

void Merge_Sort(int * A, int x, int y, int *T)
{
    if(y-x > 1) 
    {
        int m = x + (y-x)/2;
        int p = x, q = m, i = x;
        Merge_Sort(A, x, m, T);
        Merge_Sort(A, m, y, T);
        while(p < m || q < y)
        {
            if(q >= y ||(p<m && A[p] <= A[q])) T[i++] = A[p++];
            else    T[i++] = A[q++];
        } 
        for( i = x; i < y; i++) A[i] = T[i]; 
    }
}

稍加改動，即可求逆序數。把 “else T[i++] = A[q++]； ” 改成 “else { T[i++] = A[q++]; cnt += m-p; }”

即：

void Merge_Sort(int * A, int x, int y, int *T)
{
    if(y-x > 1) 
    {
        int m = x + (y-x)/2;
        int p = x, q = m, i = x;
        Merge_Sort(A, x, m, T);
        Merge_Sort(A, m, y, T);
        while(p < m || q < y)
        {
            if(q >= y ||(p<m && A[p] <= A[q])) T[i++] = A[p++];
            else  {    T[i++] = A[q++]; cnt += m-p;}
        } 
        for( i = x; i < y; i++) A[i] = T[i]; 
    }
}

如果想求順序數的個數，直接用總情況數（n-1+1）*（n-1）/2 - 逆序數即可！

用歸并排序法----計算行列式

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;


int Merge_Sort(int * A, int x, int y)
{
    int T[1000];
    int cnt = 0;
    if(y-x > 1) 
    {
        int m = x + (y-x)/2;
        int p = x, q = m, i = x;
        Merge_Sort(A, x, m);
        Merge_Sort(A, m, y);
        while(p < m || q < y)
        {
            if(q >= y ||(p<m && A[p] <= A[q])) T[i++] = A[p++];
            else  {    T[i++] = A[q++]; cnt += m-p;}
        } 
        
    }
    return cnt;
}            

void solve(int n, int a[15][15])
{
    int flag = 0; 
    long long ans=0;
    int p[15];
    for(int i=0; i<n; i++) 
    p[i] = i+1;
    do
    {
        int ok = Merge_Sort(p, 0,  n); 
        if(ok&1) 
        {
            flag++;
           printf(" - ");
            long long temp=1;
            for(int j=1, i=0; i<n; j++, i++)
            {
                temp*=(long long)a[j][p[i]];
                if(j!=1)printf(" * ");
                printf("%d", a[j][p[i]]);
                
            }
            ans-=temp;
        }
        else 
        {
           if(flag)printf(" + ");
           flag++;
             long long temp=1;
            for(int j=1, i=0; i<n; j++, i++)
            {
                temp*=(long long)a[j][p[i]];
                if(j!=1)printf(" * ");
                printf("%d", a[j][p[i]]);
            }
            ans+=temp;
        }
    }while(next_permutation(p, p+n));
    printf("\n%d\n\n", ans);
}

int main() 
{
  int n;
  int a[15][15];
  while(scanf("%d", &n)!=EOF)
  {
      for(int i=1; i<=n; i++)
      for(int j=1; j<=n; j++)
      scanf("%d", &a[i][j]);
      solve(n, a);
  }
  return 0;
}

View Code

稍加完善 ~ ~ ~

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

//template <typename Type> 
int Merge_Sort(int * A, int x, int y)
{
     int T[1000];
    int cnt = 0;
    if(y-x > 1) 
    {
        int m = x + (y-x)/2;
        int p = x, q = m, i = x;
        Merge_Sort(A, x, m);
        Merge_Sort(A, m, y);
        while(p < m || q < y)
        {
            if(q >= y ||(p<m && A[p] <= A[q])) T[i++] = A[p++];
            else  {    T[i++] = A[q++]; cnt += m-p;}
        }     
    }
    return cnt;
}            

template <typename TT>
void solve(int n,  TT a[15][15])
{
    int flag = 0; 
    TT ans=0;
    int p[15];
    for(int i=0; i<n; i++) 
    p[i] = i+1;
    cout << "\n    計算算式為:\t"; 
    do
    {
        int ok = Merge_Sort(p, 0, n); 
        if(ok&1) 
        {
            flag++;
           printf(" - ");
            TT temp=1;
            for(int j=1, i=0; i<n; j++, i++)
            {
                temp*= a[j][p[i]];
                if(j!=1)printf(" * ");
                cout << a[j][p[i]];
                
            }
            ans-=temp;
        }
        else 
        {
           if(flag)printf(" + ");
           flag++;
             TT temp=1;
            for(int j=1, i=0; i<n; j++, i++)
            {
                temp*=a[j][p[i]];
                if(j!=1)printf(" * ");
                cout<< a[j][p[i]]; 
            }
            ans+=temp;
        }
    }while(next_permutation(p, p+n));
    cout<<endl;
    cout <<"\n\n行列式的結果為: " <<ans << endl << endl; 
}

int main() 
{
  int n;
  double a[15][15];                    // whatever types you want 
  cout<<"請輸入所求行列式的階數: ";
  while(scanf("%d", &n)!=EOF)
  {    
         cout << "\n請輸入 "<<n<< " * " <<n<< " 的行列式！\n\n"; 
      for(int i=1; i<=n; i++)
      for(int j=1; j<=n; j++)
      cin >> a[i][j]; 
      solve(n, a);
      cout<<"請輸入所求行列式的階數: ";
  }
  return 0;
}