[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 ;
 }