AcWing 883. 高斯消元解线性方程组python3
原题链接
简单
作者:
xanxus1111
,
2020-06-17 12:01:59
,
所有人可见
,
阅读 677
# 初等行列变化
# 完美阶梯型 ---- 唯一解
# 0 = 非零 ---- 无解
# 0 = 0 ---- 无穷解
# 也可以根据矩阵的质来判断
# 高斯消元
# 枚举每一列c
# 1. 找到绝对值最大的一行
# 2. 将这行换到最上面去
# 3. 将该行第一个数变成1
# 4. 将下面所有第c列消成0
def gauss(n):
eps = 1e-6
r = 0 #初始化行数
for c in range(n): #从0开始遍历每一列
t = r
i = r
while i < n:
if abs(a[i][c]) > abs(a[t][c]): #找到第c列中绝对值最大的那一行
t = i #让 t 等于那一行
i += 1
# if abs(a[t][c]) == 0: continue # 被数据卡住了,不能直接判断是否大于0 要判断是否小于1e-6
if abs(a[t][c]) < eps: continue
for i in range(c,n+1): a[t][i], a[r][i] = a[r][i], a[t][i] #从当前列到等号右边列开始交换 绝对值最大行与当前行
for i in range(n,c,-1): a[r][i] /= a[r][c] # 把绝对值最大行每个数都除最大值,让第一个数系数变成 1
for i in range(r+1,n): #遍历当前行后面的行
# if abs(a[i][c]): # 被数据卡住了,不能直接判断是否大于0 要判断是否大于1e-6
if abs(a[i][c]) > eps: #如果当前行的当前列不为0
for j in range(n,c,-1): #那么从等号右边开始遍历
a[i][j] -= a[r][j] * a[i][c] #a[r][j]*a[i][c] 将r行第j个数扩大 后面行的c列的倍数
r += 1
if r < n:
for i in range(r,n):
if abs(a[i][n]) > eps: #如果 0 == 非零
# if abs(a[i][n]): # 被数据卡住了,不能直接判断是否大于0 要判断是否大于1e-6
return 2 #无解
return 1 #无穷解
for i in range(n-1,-1,-1): #从后面行开始往上遍历 i 是行
for j in range(i+1,n): #
a[i][n] -= a[i][j] * a[j][n] #a[i][n]是等号右边的数,也就是每一个xi的解。 a[j][n]是xj 的值
return 0
if __name__ == "__main__":
n = int(input())
a = [0]*n
for i in range(n):
a[i] = list(map(float, (input().split())))
t = gauss(n)
if t == 0:
# for i in range(n):print(round(a[i][n],2)) #这种写法,小数点第二位的0会不显示,会被答案卡
for i in range(n):print('%.2f' % a[i][n])
elif t == 1:
print('Infinite group solutions')
else:
print('No solution')