Durchqueren Sie die Matrix in Diagonalstreifen

Question 1

Ich dachte, dieses Problem hätte eine triviale Lösung, ein paar for-Schleifen und einige ausgefallene Zähler, aber anscheinend ist es etwas komplizierter.

Meine Frage ist also, wie würden Sie (in C) eine Funktionsdurchquerung einer quadratischen Matrix in diagonalen Streifen schreiben.

Beispiel:

1  2  3
4  5  6
7  8  9

Müsste in folgender Reihenfolge durchlaufen werden:

[1],[2,4],[3,5,7],[6,8],[9]

Jeder obige Streifen wird von eckigen Klammern eingeschlossen. Eine der Anforderungen besteht darin, Streifen unterscheiden zu können. Das bedeutet, dass Sie wissen, wann Sie einen neuen Streifen beginnen. Dies liegt daran, dass es eine andere Funktion gibt, die ich für jedes Element in einem Streifen und dann vor dem Beginn eines neuen Streifens aufrufen muss. Daher ist eine Lösung ohne Codeduplizierung ideal.

Question 2

Hier ist etwas, das Sie verwenden können. Ersetzen Sie einfach die printfs durch das, was Sie tatsächlich tun möchten.

#include <stdio.h>

int main()
{
    int x[3][3] = {1, 2, 3,
                   4, 5, 6,
                   7, 8, 9};
    int n = 3;
    for (int slice = 0; slice < 2 * n - 1; ++slice) {
        printf("Slice %d: ", slice);
        int z = (slice < n) ? 0 : slice - n + 1;
        for (int j = z; j <= slice - z; ++j) {
            printf("%d ", x[j][slice - j]);
        }
        printf("\n");
    }
    return 0;
}

Ausgabe:

Slice 0: 1
Slice 1: 2 4
Slice 2: 3 5 7
Slice 3: 6 8
Slice 4: 9

Question 3

Ich würde die Zeilen so verschieben:

1  2  3  x  x
x  4  5  6  x
x  x  7  8  9

Und iterieren Sie einfach die Spalten. Dies kann tatsächlich ohne physisches Verschieben erfolgen.

Question 4

Schauen wir uns an, wie Matrixelemente indiziert werden.

(0,0)   (0,1)   (0,2)   (0,3)   (0,4)  
(1,0)   (1,1)   (1,2)   (1,3)   (1,4)  
(2,0)   (2,1)   (2,2)   (2,3)   (2,4)

Schauen wir uns nun die Streifen an:

Stripe 1: (0,0)
Stripe 2: (0,1)    (1,0)  
Stripe 3: (0,2)    (1,1)    (2,0)
Stripe 4: (0,3)    (1,2)    (2,1)
Stripe 5: (0,4)    (1,3)    (2,2)
Stripe 6: (1,4)    (2,3)
Stripe 7: (2,4)

Wenn Sie genauer hinsehen, werden Sie eines bemerken. Die Summe der Indizes jedes Matrixelements in jedem Streifen ist konstant. Also, hier ist der Code, der dies tut.

public static void printSecondaryDiagonalOrder(int[][] matrix) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int maxSum = rows + cols - 2;

    for (int sum = 0; sum <= maxSum; sum++) {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i + j - sum == 0) {
                    System.out.print(matrix[i][j] + "\t");
                }
            }
        }
        System.out.println();
    }
}

Es ist nicht der schnellste Algorithmus da draußen (macht (rows * cols * (rows+cols-2)) Operationen), aber die Logik dahinter ist ziemlich einfach.

Question 5

Ich habe das hier gefunden: Traverse Rectangular Matrix in Diagonal Strips

#include <stdio.h>

int main()
{
    int x[3][4] = { 1,  2,  3,  4,
                    5,  6,  7,  8,
                    9, 10, 11, 12};
    int m = 3;
    int n = 4;
    for (int slice = 0; slice < m + n - 1; ++slice) {
        printf("Slice %d: ", slice);
        int z1 = slice < n ? 0 : slice - n + 1;
        int z2 = slice < m ? 0 : slice - m + 1;
        for (int j = slice - z2; j >= z1; --j) {
                printf("%d ", x[j][slice - j]);
        }
        printf("\n");
    }
    return 0;
}

Ausgang:

Slice 0: 1
Slice 1: 5 2
Slice 2: 9 6 3
Slice 3: 10 7 4
Slice 4: 11 8
Slice 5: 12

Ich fand das eine ziemlich elegante Methode, da es nur Speicher für 2 zusätzliche Variablen (z1 und z2) benötigt, die im Grunde die Informationen über die Länge jedes Slice enthalten. Die äußere Schleife bewegt sich durch die Slice-Nummern (slice) und die innere Schleife bewegt sich dann durch jedes Slice mit Index: slice - z1 - z2. Alle anderen Informationen, die Sie dann benötigen, wo der Algorithmus beginnt und wie er sich durch die Matrix bewegt. Im vorherigen Beispiel bewegt es sich zuerst in der Matrix nach unten und nachdem es das untere Ende erreicht hat, bewegt es sich nach rechts: (0,0) -> (1,0) -> (2,0) -> (2,1) – > (2,2) -> (2,3). Auch dieses Muster wird von den Variablen z1 und z2 erfasst. Die Zeile wird zusammen mit der inkrementiert slice Nummer, bis es den Boden erreicht, dann z2 beginnt zu inkrementieren, was verwendet werden kann, um den Zeilenindex an seiner Position konstant zu halten: slice - z2. Die Länge jeder Scheibe ist bekannt durch: slice - z1 - z2indem Sie Folgendes ausführen: (slice - z2) - (slice - z1 -z2) (minus, da sich der Algorithmus in aufsteigender Reihenfolge m–, n++ bewegt) ergibt z1 das ist das Abbruchkriterium für die innere Schleife. Es bleibt nur der Spaltenindex übrig, der bequem von der Tatsache geerbt wird, dass j konstant ist, nachdem es den Boden erreicht hat, wonach der Spaltenindex zu inkrementieren beginnt.

Vorangehender Algorithmus bewegt sich nur in aufsteigender Reihenfolge von links nach rechts beginnend oben links (0,0). Als ich diesen Algorithmus brauchte, musste ich auch eine Matrix in absteigender Reihenfolge durchsuchen, beginnend unten links (m,n). Da ich von dem Algorithmus ziemlich begeistert war, beschloss ich, auf den Grund zu gehen und ihn anzupassen:

Die Scheibenlänge ist wieder bekannt durch: slice -z1 - z2
Die Startpositionen der Slices sind: (2,0) -> (1,0) -> (0,0) -> (0,1) -> (0,2) -> (0,3)
Die Bewegung jeder Scheibe ist m++ und n++

Ich fand es sehr nützlich, es wie folgt darzustellen:

Slice=0 z1=0 z2=0 (2,0) (Spaltenindex= Zeilenindex – 2)
Slice=1 z1=0 z2=0 (1,0) (2,1) (Spaltenindex= Zeilenindex – 1)

Slice=2 z1=0 z2=0 (0,0) (1,1) (2,2) (Spaltenindex= Zeilenindex + 0)
Slice=3 z1=0 z2=1 (0,1) (1,2) (2,3) (Spaltenindex= Zeilenindex + 1)
Slice=4 z1=1 z2=2 (0,2) (1,3) (Spaltenindex= Zeilenindex + 2)

Slice=5 z1=2 z2=3 (0,3) (Spaltenindex= Zeilenindex + 3)

Folgendes ableiten: j = (m-1) - slice + z2 (mit j++) unter Verwendung des Ausdrucks der Slice-Länge, um das Stoppkriterium zu erstellen:((m-1) - slice + z2)+(slice -z2 - z1) ergibt sich zu: (m-1) - z1
Wir haben jetzt die Argumente für die innere Schleife: for (int j = (m-1) - slice + z2; j < (m-1) - z1; j++)

Der Zeilenindex ist durch j bekannt, und wiederum wissen wir, dass der Spaltenindex nur zu inkrementieren beginnt, wenn j beginnt, konstant zu sein, und daher ist es keine schlechte Idee, j wieder im Ausdruck zu haben. Aus den Differenzen zwischen obiger Summation ist mir aufgefallen, dass die Differenz immer gleich ist j - (slice - m +1)als ich dies für einige andere Fälle testete, war ich zuversichtlich, dass dies für alle Fälle gelten würde (ich bin kein Mathematiker; P), und daher sieht der Algorithmus für die absteigende Bewegung, beginnend von unten links, wie folgt aus:

#include <stdio.h>

int main()
{
    int x[3][4] = { 1,  2,  3,  4,
                    5,  6,  7,  8,
                    9, 10, 11, 12};
    int m = 3;
    int n = 4;
    for (int slice = 0; slice < m + n - 1; ++slice) {
        printf("Slice %d: ", slice);
        int z1 = slice < n ? 0 : slice - n + 1;
        int z2 = slice < m ? 0 : slice - m + 1;
        for (int j = (m-1) - slice + z2; j <= (m-1) - z1; j++) {
                printf("%d ", x[j][j+(slice-m+1)]);
        }
        printf("\n");
    }
    return 0;
}

Die anderen beiden Richtungen überlasse ich jetzt euch ^^ (was nur wichtig ist, wenn die Reihenfolge wirklich wichtig ist).

Dieser Algorithmus ist ziemlich umwerfend, selbst wenn Sie denken, dass Sie wissen, wie er funktioniert, kann er Sie immer noch in den Arsch beißen. Ich finde es jedoch ziemlich schön, weil es sich buchstäblich durch die Matrix bewegt, wie Sie es erwarten würden. Ich bin interessiert, ob jemand mehr über den Algorithmus weiß, zum Beispiel einen Namen, damit ich schauen kann, ob das, was ich hier getan habe, tatsächlich Sinn macht und vielleicht gibt es bessere Lösungen.

Question 6

Ich denke, dies kann eine Lösung für jede Art von Matrix sein.

#include <stdio.h>

#define M 3
#define N 4

main(){
         int a[M][N] = {{1, 2, 3, 4}, 
                        {5, 6, 7, 8}, 
                        {9,10,11,12}};

         int i, j, t;
         for( t = 0; t<M+N; ++t)
              for( i=t, j=0; i>=0 ; --i, ++j)
                     if( (i<M) && (j<N) )
                             printf("%d ", a[i][j]);
         return 0;
}

Question 7

Ich dachte, dieses Problem hätte eine triviale Lösung, ein paar for-Schleifen und einige ausgefallene Zähler

Genau.

Es ist wichtig zu beachten, dass, wenn Sie jedem Element einen Index (ich, j) dann haben Gegenstände auf derselben Diagonale denselben Wert j+n–ichwo n ist die Breite Ihrer Matrix. Wenn Sie also auf die übliche Weise über die Matrix iterieren (dh verschachtelte Schleifen über ich und j) können Sie die Diagonalen in einem Array verfolgen, das auf die oben erwähnte Weise adressiert wird.

Question 8

// Dieser Algorithmus funktioniert für Matrizen aller Größen. 😉

    int x = 0;
    int y = 0;        
    int sub_x;
    int sub_y;

    while (true) {

        sub_x = x;
        sub_y = y;

        while (sub_x >= 0 && sub_y < y_axis.size()) {

            this.print(sub_x, sub_y);
            sub_x--;
            sub_y++;

        }

        if (x < x_axis.size() - 1) {

            x++;

        } else if (y < y_axis.size() - 1) {

            y++;

        } else {

            break;

        }

    }