[Swust OJ 643]--行列式的计算

[Swust OJ 643]--行列式的计算(上三角行列式变换)

题目链接：http://acm.swust.edu.cn/problem/643/

Time limit(ms): 1000　　　　　　　　Memory limit(kb): 65535   Description 一个n阶方阵A行列式记作detA,或者|A|.detA是一个数字，它的值按照下面的方式递归定义： 
如果n=1，detA=a11; 
如果n>1,detA= s1 *a11*detA1+s2 * a12 *detA2 +......+sn * a1n *det An 
一个上三角矩阵的行列式等于主对角线上元素的乘积。

 
行列式具有如下的性质： 
　性质1 　行列式的行与列互换，其值不变； 
性质2 用数k乘行列式的某一行（列），等于以数乘此行列式

  Input 第一行输入矩阵的阶n    Output
第二行输入矩阵本身。

n阶矩阵A的行列式detA.

  Sample Input   2 1 2 3 4 Sample Output -2 hint 用高斯消去法得上三角矩阵     解题思路：并不相信hint了(开个n次方就是x^(1/n),非要说牛顿切线方程，笑哭~~~),利用线性代数中行列式的性质化为上三角(下三角)行列式 　　　　　我这里化为上三角,然后行列式的值就是对角线乘积~~~~代码有详细注释，实在不会的看现代书吧~~~~ 代码如下：

 #include <stdio.h>

 double mpt[][];

 void init(int n)

 {

     int row, col;

     for (row = ; row < n; row++)

     for (col = ; col < n; col++)

         scanf("%lf", &mpt[row][col]);

 }

 void solve(int n){

     double temp, ans = 1.0;

     int cnt = , flag = ;

     //cnt统计行变换 次数，每交换一次行，行列式符号变化1次，统计变化次数(详见线性代数课本)

     int row, nextrow, col;

     double tmp;

     for (row = ; row < n - ; row++){

         nextrow = row + ;

         //开始处理第一列，如果行列式第一行第一个数为零，要交换行

         if (mpt[row][row] == ){

             while (mpt[nextrow][row] == ){

                 nextrow++; //如果行列式第二行第一个数为零，行增加继续寻找非零数值的行

                 //如果遍历完行列式行列式第一列元素都为零，退出while循环

                 if (nextrow == n){

                     flag = ;

                     break;

                 }

             }

             if (flag)continue;

             //退出while循环后回到for(row=0;row<n-1;row++)行加1从mpt[row][row]==0知列也相应加1，开始处理第二列

             cnt++;

             for (col = ; col < n; col++){

                 //交换非零行到行列式顶部

                 tmp = mpt[row][col];

                 mpt[row][col] = mpt[nextrow][col];

                 mpt[nextrow][col] = tmp;

             }

         }

         for (nextrow = row + ; nextrow < n; nextrow++){

             temp = mpt[nextrow][row] / mpt[row][row];

             for (col = ; col < n; col++)

                 mpt[nextrow][col] += -temp*mpt[row][col];//化行列式为上三角行列式形式

         }

     }

     for (row = ; row < n; row++)ans *= mpt[row][row];

     printf("%.f\n", cnt &  ? -ans : ans);

 }

 int main(){

     int n;

     scanf("%d", &n);

     init(n);

     solve(n);

     return ;

 }