O(1) 추가 공간을 사용하여 C 프로그램을 사용하여 n x n 나선형 행렬을 인쇄합니다.-C++-php.cn

O(1) 추가 공간을 사용하여 C 프로그램을 사용하여 n x n 나선형 행렬을 인쇄합니다.

WBOY

풀어 주다： 2023-09-06 11:53:08

앞으로

791명이 탐색했습니다.

양의 정수 n이 주어지고 시계 방향으로 O(1) 추가 공간만 사용하여 n x n 나선 행렬을 구성합니다.

나선 행렬은 나선처럼 작동하는 행렬로, 원의 원점에서 시작합니다. 시계 방향으로 회전하세요. 따라서 작업은 2 → 4 → 6 → 8 → 10 → 12 → 14 → 1 6 → 18에서 시작하는 O(1) 공간을 사용하여 나선형 형태로 행렬을 인쇄하는 것입니다.

아래는 나선형 행렬의 예시입니다. -

使用C程序打印n x n的螺旋矩阵，使用O(1)额外空间

예제

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

로그인 후 복사

무한한 공간으로 코드를 풀기는 쉬워지지만, 최적의 프로그램만큼 효율적이지 않거나 메모리와 시간 모두 효율적인 코드입니다. . 따라서 나선형 순서를 유지하기 위해 행렬의 위쪽, 오른쪽, 아래쪽 및 왼쪽 모서리에 각각 하나씩 4개의 루프가 사용됩니다. 그러나 행렬을 오른쪽 위쪽과 왼쪽 아래쪽 모서리의 두 부분으로 나누면 다음을 직접 사용할 수 있습니다. 개념

< p>오른쪽 위 절반은

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

로그인 후 복사

왼쪽 아래 절반은

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

로그인 후 복사

Note-우리는 2

알고리즘

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

로그인 후 복사

Example

#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;
}

로그인 후 복사