高斯消元（浮点数主列法消元，有剪枝细节..-白红宇

高斯消元（浮点数主列法消元，有剪枝细节..

阅读量：5331 次

发布时间：2019-06-15

本文共 1242 字，大约阅读时间需要 4 分钟。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const double EPS=1e-8; 7  8 typedef  vector
         
           vec; 9 typedef vector
          
            mat;10 11 vec Gauss(const mat& A,const vec& b){12 int n=A.size();13 mat B(n,vec(n+1));14 for(int i=0;i
           
            abs(B[pivot][i]))) pivot=j;20 swap(B[i],B[pivot]);21 if(abs(B[i][i])
            
             =0;--i){29 ans=x[i];30 for(int j=i+1;j

可能有一个令你疑惑的地方是为什么22行，j从i+1开始除，30行，j从i+1开始除

因为这些地方其实是被搞成系数为1的，我们在计算的时候不会用到这些值，所以我们不用去管当前消去的这一变量

最后一个步骤容易忽略，那就是回带的步骤，因为这个方法算完得到的B矩阵(不含增广，是一个上三角行列式，所以我们不断迭代就好了

这个方法的复杂度是n^3的

对于1000规模的，我们就需要剪枝了....

下面附上剪枝后的模板...sdut2878这个题需要剪枝

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const double EPS=1e-8; 7  8 typedef  vector
         
           vec; 9 typedef vector
          
            mat;10 11 vec Gauss(const mat& A,const vec& b){12 int n=A.size();13 mat B(n,vec(n+1));14 for(int i=0;i
           
            abs(B[pivot][i]))) pivot=j;20 if(pivot!=i) swap(B[i],B[pivot]);21 if(abs(B[i][i])
            
             =0;--i){32 ans=x[i];33 for(int j=i+1;j

20,25行是剪枝的地方

转载于:https://www.cnblogs.com/linkzijun/p/6695089.html

你可能感兴趣的文章