高斯消元模版
這模版敲了我倆個(gè)小時(shí)+寫注釋，參考自kuangbin！
兩百行的大模擬，累死了QAQ
下面附上模版！
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn=50; 4 typedef long long ll; 5 int a[maxn][maxn];///增廣矩陣 6 int x[maxn];///解集 7 bool free_x[maxn];///標(biāo)記是否是不確定的變?cè)?/span> 8 /* 9 void debug(void) 10 { 11 int i,j; 12 for(i=0;i<equ;i++) 13 { 14 for(j=0;j<var+1;j++) 15 { 16 cout<<a[i][j]<<" "; 17 } 18 cout<<endl; 19 } 20 cout<<endl; 21 } 22 */ 23 inline int read() 24 { 25 int x=0,f=1; 26 char ch=getchar(); 27 while(ch<'0'||ch>'9') 28 { 29 if(ch=='-') 30 f=-1; 31 ch=getchar(); 32 } 33 while(ch>='0'&&ch<='9') 34 { 35 x=x*10+ch-'0'; 36 ch=getchar(); 37 } 38 return x*f; 39 } 40 inline void write(int x) 41 { 42 if(x<0) 43 { 44 putchar('-'); 45 x=-x; 46 } 47 if(x>9) 48 write(x/10); 49 putchar(x%10+'0'); 50 } 51 inline int gcd(int a,int b)///最大公約數(shù) 52 { 53 return b==0?a:gcd(b,a%b); 54 } 55 inline int lcm(int a,int b)///最小公倍數(shù) 56 { 57 return a/gcd(a,b)*b;///先除后乘防溢出 58 } 59 ///高斯消元法解方程組【-2表示有浮點(diǎn)型解，無整數(shù)解】 60 ///【-1表示無解，0表示唯一解，大于0表示無窮解，并返回自由元的個(gè)數(shù)】 61 ///【有equ方程，var個(gè)變?cè)?#xff0c;增廣矩陣行數(shù)為equ，分別為0->equ-1，列數(shù)為var+1，分別為0->var】 62 int Gauss(int equ,int var) 63 { 64 int i,j,k; 65 int max_r;///當(dāng)前這列絕對(duì)值最大的行 66 int col;///當(dāng)前處理的列 67 int ta,tb; 68 int LCM; 69 int temp; 70 int free_x_num; 71 int free_index; 72 for(i=0;i<=var;i++) 73 { 74 x[i]=0; 75 free_x[i]=true; 76 } 77 ///轉(zhuǎn)化為階梯型矩陣 78 col=0;///處理當(dāng)前列 79 for(k=0;k<equ&&col<var;k++,col++)///枚舉當(dāng)前處理的行 80 { 81 ///找到該col列元素絕對(duì)值最大的那一行與第k行交換(為了在除法時(shí)減小誤差) 82 max_r=k; 83 for(i=k+1;i<equ;i++) 84 { 85 if(abs(a[i][col])>abs(a[max_r][col])) 86 max_r=i; 87 } 88 if(max_r!=k) 89 { 90 ///與第k行交換 91 for(j=k;j<var+1;j++) 92 { 93 swap(a[k][j],a[max_r][j]); 94 } 95 } 96 if(a[k][col]==0) 97 { 98 ///說明該col列第k行以下全是0了，則處理當(dāng)前行的下一列 99 k--; 100 continue; 101 } 102 for(i=k+1;i<equ;i++) 103 { 104 ///枚舉要?jiǎng)h除的行 105 if(a[i][col]!=0) 106 { 107 LCM=lcm(abs(a[i][col]),abs(a[k][col])); 108 ta=LCM/abs(a[i][col]); 109 tb=LCM/abs(a[k][col]); 110 if(a[i][col]*a[k][col]<0) 111 tb=-tb;///異號(hào)情況是相加 112 for(j=col;j<var+1;j++) 113 { 114 a[i][j]=a[i][j]*ta-a[k][j]*tb; 115 } 116 } 117 } 118 } 119 ///debug(); 120 ///無解的情況：化簡(jiǎn)的增廣矩陣中存在(0,0,......a)這樣的行(a!=0) 121 for(i=k;i<equ;i++) 122 { 123 if(a[i][col]!=0) 124 return -1; 125 } 126 ///對(duì)于無窮解來說，如果要判斷哪些是自由元，那么初等變換中的交換就會(huì)影響，則要記錄交換 127 ///無窮解的情況：在var*(var+1)的增廣矩陣中，出現(xiàn)(0,0,......0)這樣的行，即說明沒有形成嚴(yán)格的上三角陣 128 ///且目前出現(xiàn)的行數(shù)即為自由元的個(gè)數(shù) 129 if(k<var) 130 { 131 ///首先，自由元有var-k個(gè)，即不確定的變?cè)辽儆衯ar-k個(gè) 132 for(i=k-1;i>=0;i--) 133 { 134 ///第i行一定不會(huì)是(0,0,......0)的情況，因?yàn)檫@樣的行是在第k行到第equ行 135 ///同樣，第i行一定不會(huì)是(0,0,......a),(a!=0)這樣的情況無解 136 free_x_num=0;///用于判斷該行中的不確定的變?cè)膫€(gè)數(shù)，如果超過1就無法求解它們?nèi)詾椴淮_定的變?cè)?/span> 137 for(j=0;j<var;j++) 138 { 139 if(a[i][j]!=0&&free_x[j]!=0) 140 { 141 free_x_num++; 142 free_index=j; 143 } 144 } 145 if(free_x_num>1) 146 continue;///無法求出確定的變?cè)?147 ///說明只有一個(gè)不確定的變?cè)猣ree_index，那么可以求解出該變?cè)?#xff0c;且該變?cè)谴_定的， 148 temp=a[i][var]; 149 for(j=0;j<var;j++) 150 { 151 if(a[i][j]!=0&&j!=free_index) 152 temp-=a[i][j]*x[j]; 153 } 154 x[free_index]=temp/a[i][free_index];///求出該變?cè)?/span> 155 free_x[free_index]=0;///該變?cè)谴_定的 156 } 157 return var-k; 158 } 159 ///唯一解的情況：在var*(var+1)的增廣矩陣中形成嚴(yán)格的上三角形 160 ///求出Xn-1,Xn-2,......X0 161 for(i=var-1;i>=0;i--) 162 { 163 temp=a[i][var]; 164 for(j=i+1;j<var;j++) 165 { 166 if(a[i][j]!=0) 167 temp-=a[i][j]*x[j]; 168 } 169 if(temp%a[i][i]!=0) 170 return -2;///說明有浮點(diǎn)數(shù)解，但無整數(shù)解 171 x[i]=temp/a[i][i]; 172 } 173 return 0; 174 } 175 int main(void) 176 { 177 ///freopen("in.txt","r",stdin); 178 ///freopen("out.txt","w",stdout); 179 int i,j; 180 int equ,var; 181 while(equ=read(),var=read()) 182 { 183 memset(a,0,sizeof(a)); 184 for(i=0;i<equ;i++) 185 { 186 for(j=0;j<var+1;j++) 187 { 188 a[i][j]=read(); 189 } 190 } 191 ///debug(); 192 int free_num=Gauss(equ,var); 193 if(free_num==-1) 194 printf("No solution\n");///無解 195 else if(free_num==-2) 196 printf("There are floating point numbers, no integer solutions\n");///有浮點(diǎn)數(shù)解，無整數(shù)解 197 else if(free_num>0) 198 { 199 printf("The number of variables of infinite solution is:%d\n",free_num);///無窮多解,自由變?cè)獋€(gè)數(shù)為 200 for(i=0;i<var;i++) 201 { 202 if(free_x[i]!=0) 203 printf("x%d is not sure\n",i+1); 204 else 205 printf("x%d:%d\n",i+1,x[i]); 206 } 207 } 208 else 209 { 210 for(i=0;i<var;i++) 211 printf("x%d:%d\n",i+1,x[i]); 212 } 213 printf("\n"); 214 } 215 return 0; 216 }?
轉(zhuǎn)載于:https://www.cnblogs.com/ECJTUACM-873284962/p/7119751.html
總結(jié)
- 上一篇： Lintcode---统计比给定整数小的
- 下一篇： 关于Ueditor存储在mysqlUTF