Verwenden Sie ein C-Programm, um eine n x n-Spiralmatrix zu drucken und dabei O(1) zusätzlichen Platz zu verwenden

Gegeben sei eine positive ganze Zahl n und konstruiere eine n x n-Spiralmatrix unter Verwendung von nur O(1) zusätzlichem Platz im Uhrzeigersinn.

Eine Spiralmatrix ist eine Matrix, die wie eine Spirale funktioniert. Sie beginnt am Ursprung des Kreises , im Uhrzeigersinn drehen. Die Aufgabe besteht also darin, die Matrix in Spiralform unter Verwendung des O(1)-Raums zu drucken, beginnend mit 2 → 4 → 6 → 8 → 10 → 12 → 14 → 1 6→ 18.

Unten ist die Beispiel-Spiralmatrix -

Beispiel

Input: 3
Output:
   9 8 7
   2 1 6
   3 4 1

Es wird einfach, den Code mit unendlich viel Platz zu lösen, aber er ist nicht so effizient wie das optimale Programm, oder der Code ist sowohl im Speicher als auch in der Zeit effizient . Um die Spiralreihenfolge aufrechtzuerhalten, werden also vier Schleifen verwendet, jeweils eine für die obere, rechte, untere und linke Ecke der Matrix. Wenn wir die Matrix jedoch in zwei Teile teilen, die obere rechte und die untere linke Ecke, können wir This direkt verwenden Konzept

< p>Für die obere rechte Hälfte,

mat[i][j] = (n-2*x)*(n-2*x)-(i-x)-(j-x)

Für die untere linke Hälfte,

mat[i][j] = (n-2*x-2)*(n-2*x-2) + (i-x) + (j-x)

Hinweis-Wir schreiben ein Programm zum Drucken von Matrix-Vielfachen von. 2

Algorithmus

int spiralmatrix(int n)
START
STEP 1: DECLARE i, j, a, b, x
STEP 2: LOOP FOR i = 0 AND i < n AND i++
   LOOP FOR j = 0 AND j < n AND j++
      FIND THE MINIMUM IN (i<j ) AND ASSIGN IT TO a
      FIND THE MINIMUM (n-1-i) < (n-1-j) AND ASSIGN IT TO b
      THEN ASSIGN THE LEAST VALUE FROM a AND b TO x
      IF i <= j THEN,
         PRINT THE VALUE OF 2* ((n-2*x)*(n-2*x) - (i-x) - (j-x))
      ELSE
         PRINT THE VALUE OF 2*((n-2*x-2)*(n-2*x2) + (i-x) + (j-x))
   END LOOP
   PRINT NEWLINE
END LOOP
STOP

Beispiel

#include <stdio.h>
//For n x n spiral matrix
int spiralmatrix(int n){
   int i, j, a, b, x; // x stores the layer in which (i, j)th element exist
   for ( i = 0; i < n; i++){
      for ( j = 0; j < n; j++){
         // Finds minimum of four inputs
         a = ((i<j ? i : j));
         b = ((n-1-i) < (n-1-j) ? (n-1-i) : (n-1-j));
         x = a < b ? a : b;
         // For upper right half
         if (i <= j)
            printf("%d\t ", 2 * ((n-2*x)*(n-2*x) - (i-x) - (j-x)));
            // for lower left half
         else
            printf("%d\t ", 2*((n-2*x-2)*(n-2*x-2) + (i-x) + (j-x)));
      }
      printf("</p><p>");
   }
}
int main(int argc, char const *argv[]){
   int n = 3;
   spiralmatrix(n);
   return 0;
}

Ausgabe

Wenn wir das obige Programm ausführen, wird die folgende Ausgabe generiert:

18 16 14
4 2 12
6 8 10

Das obige ist der detaillierte Inhalt vonVerwenden Sie ein C-Programm, um eine n x n-Spiralmatrix zu drucken und dabei O(1) zusätzlichen Platz zu verwenden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!