Matematické Fórum

!/usr/bin/env python
# -*- coding: utf-8 -*-

# uloha - reseni linearnich soustav v Z3 pomoci Gauss-Jordanovy metody v jazyce Python

import sys

# pro kontrolni vypis matice
def pprint(A):
    n = len(A)
    for i in range(0, n):
        line = ""
        for j in range(0, n+1):
            line += str(A[i][j]) + "\t"
            if j == n-1:
                line += "| "
        print(line)
    print("")

# funkce pro vypocitani vhodneho nasobku pro eliminaci prvku ve sloupci s pivottem
def elimnumber(x, y):
    if y == 0:
        return 0
    if x == 1:
        return -y
    if x == 2:
        return -(3-y)

# hlavin funkce, vrati LZ nebo LN podle toho, ci jsou radky soustavy LZ nebo ne,
# dale pokud existuje reseni, vypise ho, pokud ne, vypise NE
def gauss(A):
    dependent = False # na zacatku predpokladame, ze matice ma vsechny radky nezavisle
    n = len(A)
    x = [0 for i in range(n)] # inicializace vektoru reseni

    # prochazime jeden sloupec za druhym
    for i in range(0, n):
        # hledame yvota, tedy nejvyssi hodnotu ve sloupci
        maxEl = abs(A[i][i])
        maxRow = i #v maxRow udrzujeme kandidata na pivota
        for k in range(i+1, n):
            if abs(A[k][i]) > maxEl:
                maxEl = abs(A[k][i])
                maxRow = k

        # vybublame pivot na i-ty radek
        for k in range(i, n+1):
            tmp = A[maxRow][k]
            A[maxRow][k] = A[i][k]
            A[i][k] = tmp

        # pokud jediny pivot, ktereho jsme nasli, je 0, jsou zbyle radky LZ, tedy i cela matice
        if A[i][i] == 0:
            dependent = True
            for z in range(i,n):
                x[z] = 1
            break

        # vynulujeme cely sloupec nad i pod pivocem
        for k in range(0, n):
            if k != i: # pro vsechny radky, kde neni pivot
                c = elimnumber(A[i][i],A[k][i]) # pomoci pomocne funkce ziskame vhodny nasobek, abycho nulovali
                for j in range(i, n+1):
                    if i == j:
                        A[k][j] = 0
                    else:
                        A[k][j] += c * A[i][j]
                        A[k][j] = A[k][j] % 3 # pracujeme v aritmetice modulo 3
    
    # nyni uz vime, ci jsou radky LZ nebo LN
    if dependent:
        print ("LZ")
    else:
        print ("LN")

    # najdeme reseni

    # pokud mame v A nenulovy radek a v b nenulovou slozku v prislusnem radku, reseni neexistuje
    for i in range(n):
        nenulove = True
        for j in range(n):
            if A[i][j] != 0:
                nenulove = False
        if (A[i][n] != 0 and nenulove == False):
            print ("NE")

    # metodou zpetneho dosazeni najdeme reseni rovnice
    for i in range(n-1, -1, -1):
        if A[i][i] == 0:
            x[i] = 0 # pokud je slozka volnym parametrem, volime 0
        else:
            x[i] = (A[i][n] * A[i][i]) % 3
        for k in range(i-1, -1, -1):
            A[k][n] -= A[k][i] * x[i]
            A[k][n] = A[k][n] % 3

    # vypiseme reseni, vektor x, v pozadovanem tvaru
    line = ""
    for i in range(0, n):
        line += str(x[i]) + " "
    print (line)

# hlavni program
n = input() # pocet radku
m = input() # pocet sloupcu
ishomegonous = input() 

matrix = [[0 for j in (range((n+1)))] for i in (range((n)))] # inicializace matice

# pokud je homogeni, tak v soustave Ax=b je b nulovy vektor
if ishomegonous == 'H':
    for i in range(n):
        matrix[i][m-1] = 0
    for i in range(n):
        for j in range(n):
            matrix[i][j] = input()
# jinak nacitame i vektor b jako posledni sloupec
else:
    for i in range(n):
        for j in range(n+1):
            matrix[i][j] = input()

gauss(matrix) # spusteni reseni programu