Rozwiąż układ równań liniowych

12

Napisz program, który rozwiąże szereg równań liniowych tak krótko, jak to możliwe. Musi rozwiązać dowolną liczbę problemów równań. Można je wprowadzać w dowolny sposób, współczynniki rozszerzonej macierzy są prawdopodobnie najłatwiejsze. Program nie musi obsługiwać współczynników ani rozwiązań niecałkowitych. Żadne zdegenerowane lub nieprawidłowe przypadki nie będą testowane. Program musi wypisać wartość każdej zmiennej lub formularza zredukowanego wiersza.

Żadne biblioteki rozwiązywania równań, funkcje macierzy ani żaden sposób automatycznego rozwiązywania równań nie jest dozwolony. Możesz symulować macierze za pomocą tablic lub list.

Przykładowe dane wejściowe (lub równoważne):

m={{2,1,-1,8},{-3,-1,2,-11},{-2,1,2,-3}}

To reprezentuje 2x+y-z=8, -3x-y+2z=-11, -2x+y+2z=-3

Przykładowe dane wyjściowe (lub równoważne):

{2,3,-1}

To reprezentuje x=2, y=3, z=-1

qwr
źródło
2
Czy współczynniki zmiennych i wyrażenia stałe można podzielić na dwie tablice na wejściu?
user12205
@ace tak, w porządku
qwr
1
Co dokładnie mówisz o zdegenerowanych przypadkach? Myślę, że odnosisz się do wszystkich tych przypadków: 1) Źle sformułowane dane wejściowe; 2) Rzeczy takie jak 0x=0lub 0x=5; 4) Przypadki, w których liczba równań jest inna niż liczba zmiennych; 5) Sprzeczne przypadki, takie jak x+5y=7, x+5y=8; 6) Obudowy bez liniowej niezależności, jak x+3y=6, 2x+6y=12. Czy mam rację?
Victor Stafusa
@Victor Tak, wszelkie dane wejściowe, które są w ogóle niejasne lub których nie można rozwiązać.
qwr
Co z przypadkami, które nie są zdegenerowane, ale źle uwarunkowane? (Lub innymi słowy, jaki rodzaj obrotu jest wymagany?)
Peter Taylor

Odpowiedzi:

3

Python 169 166

Realizacja

def s(a):
 if a:b=a[0];r=s([[x-1.*y*b[0]/r[0]for x,y in zip(b[1:],r[1:])]for r in a[1:]]);return[round((b[-1]-sum(x*y for x,y in zip(b[1:-1],r)))/b[0])]+r
 return[]

Próbny

>>> arr=[[2, 1, -1, 8], [-3, -1, 2, -11], [-2, 1, 2, -3]]
>>> s(arr)
[2.0, 3.0, -1.0]

Uwaga

Jeśli zgadzasz się na przybliżenie liczby zmiennoprzecinkowej, możesz usunąć wywołanie funkcji rundy i dalej grać w golfa do 159 znaków

Abhijit
źródło
9

APL, 1 znak

Wiem, że nie spełnia (poprawionych) wymagań, ale zbyt dobrze jest nie publikować:

Symbol „domino” (podział ÷w prostokącie) wykonuje podział macierzy, dlatego może rozwiązać dowolny układ równań liniowych. Musisz po prostu umieścić go między wektorem stałego terminu a macierzą z innymi terminami:

      8 ¯11 ¯3 ⌹ ⊃(2 1 ¯1)(¯3 ¯1 2)(¯2 1 2)
2 3 ¯1

(jeśli chcesz spróbować na TryApl, jest )

Tobia
źródło
4

JavaScript ( 284 181) - Metoda eliminacji Gaussa

function f(A){l=A.length;d=1;for(i=0;i+1;i+=d){v=A[i][i];for(k=0;k<l+1;k++)A[i][k]/=v;for(j=i+d;A[j];j+=d)for(k=0,w=A[j][i];k<l+1;k++)A[j][k]-=w*A[i][k];if(i==l-d)d=-1,i=l}return A}

Test

f([[2,1,-1,8],[-3,-1,2,-11],[-2,1,2,-3]]);

=> [[1,0,0,2],[0,1,0,3],[-0,-0,1,-1]]

Zwrócona tablica łączy macierz tożsamości i rozwiązanie.

Michael M.
źródło
Możesz zapisać jeszcze kilka postaci.
MarcinJuraszek
Zamiast l=A.length;for(i=0;i<l;i++)używać for(i=0;i<l=A.length;i++).
Victor Stafusa
Zamiast for(i=l-1;i>=0;i--)używać for(i=l;--i;).
Victor Stafusa,
Można także przenieść w=A[j][i]się for()i przejść {}wokół.
MarcinJuraszek
Dzięki wszystkim, udało mi się połączyć kroki do przodu i do tyłu w jednym kroku, oszczędzając sto znaków, a niektóre z twoich wskazówek nie są już ważne. (z wyjątkiem @MarcinJuraszek wskazówka)
Michael M.
3

Ta odpowiedź nie pasuje już do pytania po zmianie reguły, ponieważ korzysta z funkcji macierzowej. *

Sage , 32 lata

~matrix(input())*vector(input())

Przykładowe dane wejściowe:

[[2, 1, -1], [-3, -1, 2], [-2, 1, 2]]
[8, -11, -3]

Przykładowe dane wyjściowe:

(2, 3, -1)

* Prawdopodobnie matrix()jest to rzut typu, a nie funkcja (uruchamianie import types; isinstance(matrix, types.FunctionType)daje False). Ponadto operatory~ i *operatorami , a nie funkcjami.

użytkownik12205
źródło
Zaktualizowałem zasady. Kod musi obsługiwać różną liczbę równań i nie można teraz używać funkcji macierzowych.
qwr
3

Java - 522 434 228 213 znaków

Rozwiązuje się przez systematyczne sprawdzanie wszystkich możliwych n-krotek całkowitych przez bezpośrednie mnożenie, aż do znalezienia jednego, który działa.

Funkcja przyjmuje rozszerzoną macierz, A, wektor rozwiązania próbnego, x i wymiar, n, jako wektor rozwiązania wejścia-wyjścia, x. Zauważ, że wektor x jest w rzeczywistości o jeden większy niż wymiar, aby pomóc przejść przez możliwe rozwiązania. (Gdybym zadeklarował zmienne A, x, n, j, k, s jako zmienne instancji, funkcja byłaby o 31 znaków krótsza - w sumie 182, ale wydaje się, że wyginanie reguł jest zbyt duże).

int[]Z(int[][]A,int[]x,int n){int j,k,s;for(;;){for(j=0;j<n;j++){for(k=s=0;k<n;s+=A[j][k]*x[k++]);if(s!=A[j][n])j+=n;}if(j==n)return x;for(j=0;j<=n;j++)if(x[j]!=x[n]||j==n){x[j]++;for(k=0;k<j;x[k++]=-x[n]);j=n;}}}

Program do testowania (nieco nie golfowy):

import java.util.*;
class MatrixSolver{
    public MatrixSolver() {
        Scanner p=new Scanner(System.in); //initialize everything from stdin
        int j,k,n=p.nextInt(),A[][]=new int[n][n+1],x[]=new int[n+1];
        for(j=0;j<n;j++)for(k=0;k<=n;A[j][k++]=p.nextInt());
        x=Z(A,x,n); //call the magic function
        for(j=0;j<n;j++) System.out.print(x[j]+" "); //print the output
    }
    public static void main(String[]args){
        new MatrixSolver();
    } 

    int[]Z(int[][]A,int[]x,int n){
        int j,k,s;
        for(;;){
            for(j=0;j<n;j++){ //multiply each row of matrix by trial solution and check to see if it is correct
                for(k=s=0;k<n;s+=A[j][k]*x[k++]);
                if(s!=A[j][n])j+=n;
            }
            if(j==n)return x; //if it is correct return the trial solution
            for(j=0;j<=n;j++)if(x[j]!=x[n]||j==n){//calculate the next trial solution
                x[j]++;
                for(k=0;k<j;x[k++]=-x[n]);
                j=n;
            }
        }
    }
}

Program pobiera dane wejściowe ze stdin jako liczby całkowite oddzielone spacją w następujący sposób: po pierwsze, wymiar problemu, po drugie, wpisy rozszerzonej macierzy po rzędzie.

Przykładowy przebieg:

$java -jar MatrixSolver.jar
3 2 1 -1 8 -3 -1 2 -11 -2 1 2 -3
2 3 -1 

Ogoliłem kilka postaci, postępując zgodnie z radami Victora dotyczącymi pętli i „publicznych”, przechowując RHS w rozszerzonej matrycy zamiast osobno i dodając dodatkowy wpis do mojego rozwiązania próbnego, aby uprościć generowanie każdego nowego rozwiązania próbnego. OP stwierdził również, że wystarczy funkcja - nie trzeba liczyć całego programu.

Wally
źródło
while(true){f=0;for(j=0;j<n;j++)można zastąpić while(true){for(f=j=0;j<n;j++). Co więcej, twoja klasa nie musi być publiczna. Pętle For z jedną instrukcją w ciele nie potrzebują nawiasów klamrowych.
Victor Stafusa,
Myślę, że for(j=0;j<n;j++){for(k=0;k<n;k++){A[j][k]=p.nextInt();}b[j]=p.nextInt();}można to zastąpićfor(j=0;j<n;b[j++]=p.nextInt())for(k=0;k<n;)A[j][k++]=p.nextInt();
Victor Stafusa
@Victor Dzięki, wprowadziłem te i inne zmiany.
Wally,
while(true)można zmienić nafor(;;)
użytkownik12205
@ace dzięki - zmieniłem to i kilka innych rzeczy i ogoliłem 15 znaków.
Wally
1

JavaScript (ES6),  152  151 bajtów

Wdrożenie zasady Cramera .

(m)(v)mv

m=>v=>m.map((_,i)=>(D=m=>m+m?m.reduce((s,[v],i)=>s+(i&1?-v:v)*D(m.map(([,...r])=>r).filter(_=>i--)),0):1)(m.map((r,y)=>r.map((k,x)=>x-i?k:v[y])))/D(m))

Wypróbuj online!

Arnauld
źródło