posts - 16,comments - 0,trackbacks - 0
/*
    求行列式 O(n^3)
*/
# include 
< string .h >

int  v[N][N], t[N];

int  gcd( int  a,  int  b) { return  b  ?  gcd(b, a % b):a;}

int  det( int  n)
{
    
int  c, r, i;
    
int  cof  =   1 , ret  =   1 ;
    
int  mc, mh;
    
    
for  (c  =   1 ; c  <=  n;  ++ c)
    {
            
for  (r  =  c; r  <=  n;  ++ r)
            {
                    
if  (v[r][c]  <   0 for  (i  =  c; i  <=  n;  ++ i) v[r][i]  =   - v[r][i];
                        
for  (tt  =   0 , i  =  c; i  <=  n;  ++ i)  if  (v[r][i]  !=   0 )
                                    
if  (tt  ==   0 ) tt  =  v[r][i];
                                    
else  tt   =  gcd(v[r][i], tt);
                        
if  (tt  <   0 ) tt  =   - tt;
                        
if  (tt  >   1 for  (i  =  c; i  <=  n;  ++ i) v[r][i]  /=  tt;
                }
        
for  (mv  =  v[ 1 ][c], mr =  c, r  =  c + 1 ; r  <=  n;  ++ r)
        {
            
if  (v[r][c]  <   0 for  (ret  =   - ret, i  =  c; i  <=  n;  ++ i) v[r][i]  *=   - 1 ;
            
if  (v[r][c]  >  mv) mv  =  m[r][c], mr  =  r;
        }
        
        
/*  行列式整列都为 0  */
        
if  (mv  ==   0 return   0 ;
        
        
/*  交换行使 v[c][c] 是 v[cn][c] 中最大的  */
        memcpy(t
+ 1 , v[ 1 ] + 1 sizeof (v[ 0 ][ 0 ]) * n);
        memcpy(v[
1 ] + 1 , v[mr] + 1 sizeof (v[ 0 ][ 0 ]) * n);
        memcpy(v[mr]
+ 1 , t + 1 sizeof (v[ 0 ][ 0 ]) * n);
        
        
/*  消去 c+1..n 行行首非零元素  */
        
for  (r  =  c + 1 ; r  <=  n;  ++ r)  if  (v[r][c])
        {
            mh 
=  v[r][c] / gcd(mv, v[r][c]));
            mc 
=  mv * mh / v[r][c];
            
for  (t  =  c; t  <=  n;  ++ c)     v[r][t]  =  mc * v[r][t] - mh * v[c][t];
            cof 
*=  mc;
        }
        ret 
*=  v[c][c];
    }
    
    
return  ret * mc;
}
 
posted on 2012-08-30 17:20 yajunw 阅读(347) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理