Teilmatrizen aus Matrix ziehen und auswerten

Fips1907

Hallo,

ich habe folgendes Problem:
Es ist ein Algorithmus zu erstellen der für eine Matrix mit x Zeilen und y Spalten nur Werte von 0 und 1 ablegt.
Soweit kein Problem denke ich.. Hier habe ich einfach ne Prozedur gemacht, der man die Matrix, x, y und den Wert (0 oder 1) übergibt und dann wird der Wert in der Matrix in der ensprechenden Stelle gesetzt..

Jetzt das was ich noch nicht verstehe:
Es soll noch ermittelt werden wieviele quadratische Teilmatrizen enthalten sind und wieviele dieser Teilmatrizen in der Hauptdiagonalen nur den Wert 1 besitzen..

Irgendwie fehlt mir bei dem Teil komplett der Ansatz..
Ein paar denkanstösse wären nicht schlecht :o

gruß,
fips

Fips1907

so.. habs fast.. mir fehlt nur noch die ausgabe der teilmatrizen

die anzahl der teilmatrizen ermittle ich nun mit dieser methode:

Code

private static void getTeilmatrizen(int [][] matrix) {
        int countTeilmatrizen = 0;
        int maxQuadrat = matrix.length;
        if (matrix[0].length < maxQuadrat) maxQuadrat = matrix[0].length;

        for (int k = 2; k<=maxQuadrat; k++) {
            int teilmatrizen = (matrix.length - k + 1) * (matrix[0].length - k + 1);
            countTeilmatrizen += teilmatrizen;
        }
        System.out.println("Anzahl Teilmatrizen: " + countTeilmatrizen);
    }

Alles anzeigen

und prüfen ob eine matrix (oder teilmatrix, das ist ja in dem moment egal) in der hauptdiagonalen nur 1er hat mach ich so:

Code

private static boolean checkHautpdiagonale(int[][] matrix) {
        int spalte = 0;
        for (int i=0; i<matrix.length; i++) {
            if (matrix[i][spalte] != 1) return false;
            spalte++;
        }

        System.out.println("Matrix hat in Hauptdiagonale nur den Wert 1");
        return true;
    }

mir fehlt jetzt nur noch ne möglichkeit wie ich nicht nur die anzahl der teilmatrizen ausgeben kann, sondern die teilmatrizen selbst..

Ringding

Nachdem hier nichts von asymptotischer Laufzeitbeschränkung steht, würde ich eine rekursive Funktion machen, die ein Quadrat als Input nimmt (Seitenlänge a) und zuerst mal dessen Hauptdiagonale checkt. Danach ruft sie sich rekursiv für alle 4 Teilquadrate mit Seitenlänge a-1 auf und addiert dann alles zusammen. Ganz außen muss man das Ding halt in einer Schleife aufrufen, wenn man ein Rechteck hat.

Fips1907

irgendwie raff ichs nicht..
das problem was ich noch habe ist, wenn ich z.b. eine matrix 4*4 habe, dann sind da 9 teilmatrizen mit 2*2 drin und 4 teilmatrizen mit 3*3 drin..
ich weiß nicht wie ich das alles in dem algo unterbringen kann..

Ringding

Ich komm grad drauf, dass meine Methode falsch ist...

viper

Du machst einfach drei verschachtelte Schleifen. Die erste geht über alle möglichen Größen einer Matrix, die zweite z.B. über den Index der ersten Spalte der Teilmatrix (z.B. wenn du eine 4x4-Matrix hast und alle 2x2-Matrizen suchst, wird es Teilmatrizen geben, die in den Spalten 1,2 und 3 anfangen, also von 1 bis "Breite der Matrix - Teilmatrixgröße + 1") und die dritte über den Index der ersten Zeile der Teilmatrix (analog, nur für Zeilen und nicht für Spalten).
Benennst du die Zählvariablen z.B. n, i und j (in der angegebenen Reihenfolge), kannst du die durch (i,j) und (i+n-1, j+n-1) begrenzte Matrix dem Hauptdiagonalentest unterziehen (du überprüfst also ob (i, j), (i+1, j+1), (i+2, j+2) ... (i+n-1, j+n-1) gleich eins sind in einer Schleife); falls das passt kannst du so die Matrix ausgeben:

Code

for (int a = i; a < i + n; a++) {
  for (int b = j; b < j + n; b++) {
    System.out.print(matrix[a][b]+" ");
  }
  System.out.println();
}

Ist es das was du brauchst?

Du kannst diese Schleifen natürlich auch als rekursive Funktionen formulieren, falls dir das eher liegt.

Erklärbär

überlegs dir mal mathematisch. wieviele matrizen erhältst du aus ner 2x2, 3x3, 4x4 usw. vielleicht erkennst du ein system dahinter und kannst das ergebnis berechnen und brauchst keinen komplizierten algorithmus entwerfen.

Fips1907

danke viper.. ich glaube das hat mich auf die richtige spur gebracht..
werd mich nachher gleich nochmal dran machen..

Erklärbär:
mathematisch hab ichs ja schon..
mit (n - k + 1) * (m - k + 1) kann ich die anzahl errechnen.. k ist dabei die größe der quadratischen teilmatrix
mein problem ist (war) das ich die teilmatrizen auch ausgeben will.. aber ich denke ich werds nun hinbekommen..
werde heute abend nochmal posten obs geklappt hat..

Fips1907

so.. habs nun so gemacht:

Code

private static void checkTeilmatrizen(int[][] matrix) {
        System.out.println("Teilmatrizen: ");

        int countTeilmatrizen = 0;
        int maxQuadrat = matrix.length;
        if (matrix[0].length < maxQuadrat) maxQuadrat = matrix[0].length;


        for (int n=2; n<=maxQuadrat+1; n++) {
            for (int i=0; i<matrix[0].length-n+1; i++) {
                for (int j=0; j<matrix.length-n+1; j++) {

                    for (int a=j; a<j+n; a++) {
                        for (int b=i; b<i+n; b++) {
                            System.out.print(matrix[a][b]+" ");
                        }
                        System.out.println();
                    }

                    if (checkHautpdiagonale(matrix, j, i, n)) { // Hauptdiagonale pruefen
                        System.out.println("Matrix hat in Hauptdiagonale nur den Wert 1");
                    }
                    countTeilmatrizen++;


                    System.out.println();
                }
            }
        }

        System.out.println("Anzahl Teilmatrizen: " + countTeilmatrizen);
    }

    private static boolean checkHautpdiagonale(int[][] matrix, int j, int i, int n) {
        for (int a=j; a<j+n; a++) {
            if (matrix[a][i] != 1) return false;
            i++;
        }
        return true;
    }

Alles anzeigen

funktioniert auch ganz gut..
kann man evtl. noch was optimieren, aber das mach ich dann am wochenende..

danke euch!

Jetzt mitmachen!