HOWTO · C++

C++의 매직 스퀘어 문제

이 문서에서는 C++를 사용하여 마방진 문제를 구현하는 방법에 대해 설명합니다.

작성자 Adnan Ashraf게시일 2023-06-20업데이트 2023-10-12

이 기사에서는 마방진 문제, 속성 및 C++를 사용한 구현에 대해 설명합니다. 마방진을 구현하기 위해 마방진 문제를 배워봅시다.

매직 스퀘어 문제

마방진은 각 행, 열 및 대각선의 합이 동일한 양의 정수의 2D 배열입니다. 합은 흔히 매직 합(Magic Sum)이라고 부르는데 각 행, 열, 대각선의 일정한 합을 말합니다.

마방진의 각 위치에 있는 정수 값은 고유해야 합니다. N이 마방진의 크기인 경우 1에서 N2까지의 정수를 포함할 수 있습니다.

다음 공식은 매직섬을 계산합니다.

<사업부>
$$
Magic;Sum=N\left(N^{2}+1\right) / 2
$$

마방진의 크기는 행과 열의 수를 나타냅니다. N이 3이면 마방진에는 3개의 행과 3개의 열이 있습니다.

이제 매직섬을 예로 들어 설명하겠습니다. N의 값이 3이라고 가정하면 위 공식에 의해 다음과 같이 계산할 수 있습니다.

<사업부>
$$
Magic;Sum=3\left(3^{2}+1\right) / 2 = 15
$$

여기서 15는 매직섬입니다. 이는 각 열, 행 및 대각선 합계가 15와 같아야 함을 의미합니다.

크기가 3인 마방진이 아래 그림에 나와 있습니다.

매직합 3

각 행, 열 및 대각선 합계가 매직 합계와 같고 모든 항목이 고유하다는 것을 알 수 있습니다.

마방진 문제를 이해했다면 이제 구현해 봅시다.

우리가 구현할 마방진의 크기를 n이라고 하자. 그런 다음 첫 번째 값(즉, 1)은 마방진의 위치 (n/2,n-1)에 저장됩니다.

이 위치가 (i,j)라고 가정하면 다음 값은 위치 (i-1,j+1)에 있습니다. 여기서 우리는 모든 행과 열에 랩어라운드(즉, 원형 패션이라고도 함)가 있다고 가정합니다.

매직 스퀘어 문제의 조건

  1. 다음 값의 위치는 현재 열 번호에 1을 더하고 현재 행 번호에서 1을 빼서 결정됩니다.
    • 열의 새로운 위치가 n이 되면 열과 행이 순환 방식이므로 0으로 래핑됩니다.
    • 마찬가지로 까마귀의 새 위치가 -1이 되면 n-1로 래핑됩니다.
  2. 새로 계산된 위치에 이미 값이 포함되어 있다고 가정합니다. 이 경우 1을 추가하여 현재 행 번호가 업데이트되고 2를 빼서 현재 열 번호가 업데이트됩니다.
  3. 새로 계산된 열 번호가 n이고 행 번호가 -1인 경우 업데이트된 위치는 (0,n-2)입니다.

C++에서 매직 스퀘어 구현

세부 사항으로 이동하기 전에 아래 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
// This function will generate an old-size magic square only.
void magicSquareGenerator(int s) {
  int magic_Square[s][s];
  // This will initialize all locations of the magic square to 0
  memset(magic_Square, 0, sizeof(magic_Square));
  // here, r is the row index, and c is the column index for the first number
  int r = s / 2;
  int c = s - 1;
  //  generating magic square
  for (int num = 1; num <= s * s;) {
    if (r == -1 && c == s)  // Third condition
    {
      c = s - 2;
      r = 0;
    } else {
      if (c == s) c = 0;
      if (r < 0) r = s - 1;
    }
    if (magic_Square[r][c])  // second condition
    {
      c -= 2;
      r++;
      continue;
    } else
      magic_Square[r][c] = num++;
    c++;
    r--;  // 1st condition
  }

  // Print magic square
  cout << "The Magic Square has:" << s << " rows and " << s << " columns.";
  cout << "\nThe Magic Sum is: " << s * (s * s + 1) / 2 << ":\n";
  for (r = 0; r < s; r++) {
    for (c = 0; c < s; c++)
      // displaying the magic square.
      cout << setw(4) << magic_Square[r][c] << " ";
    cout << endl;
  }
}

int main() {  // Code expects only odd sizes
  int s;
  cout << "Enter the size of the Magic Square: ";
  cin >> s;
  while (s % 2 == 0) {
    cout << "Plz Enter an odd number :" << endl;
    cout << "Enter the size of the Magic Square: ";
    cin >> s;
  }
  magicSquareGenerator(s);
  return 0;
}

다음은 위의 매직 스퀘어 프로그램에 대한 단계별 설명입니다.

  1. 값 1의 위치는 = (3/2,3-1) = (1,2) = [1][2]입니다.
  2. 값 2의 위치는 = (1-1,2+1) = (1,2) = [1][2]입니다.
  3. 값 3의 위치는 = (0-1,0+1) = (3-1,1+1) = [2][1]입니다.
  4. 값 4의 위치는 = (2-1,1+1) = (1,2) = [1][2]입니다.
    • [1][2]에는 이미 1의 값이 있으므로 조건 2에 의해 새 위치는 (1+1,2-2) = [2][0]이 됩니다.
  5. 값 5의 위치는 = (2-1,0+1) = (1,1) = [1][1]입니다.
  6. 값 6의 위치는 = (1-1,1+1) = (1,2) = [0][2]입니다.
  7. 값 7의 위치는 = (0-1,2+1) = (-1,3)입니다.
    • 조건 3이 성립하므로 새 위치는 (0,3-2)=[0][1]이 됩니다.
  8. 값 8의 위치는 = (0-1,1+1) = (-1,2) = [2][2] 조건에 따라 1 행이 래핑됩니다.
  9. 값 9의 위치는 = (2-1,2+1) = (1,3) = [1][0] 조건에 따라 1 열이 래핑됩니다.

다음은 마방진 3의 크기를 입력했을 때의 출력입니다.

Enter the size of the Magic Square: 3
The Magic Square has:3 rows and 3 columns.
The Magic Sum is: 15:
   2    7    6
   9    5    1
   4    3    8

다음은 마방진 7의 크기를 입력했을 때의 출력입니다.

Enter the size of the Magic Square: 7
The Magic Square has:7 rows and 7 columns.
The Magic Sum is: 175:
  20   12    4   45   37   29   28
  11    3   44   36   35   27   19
   2   43   42   34   26   18   10
  49   41   33   25   17    9    1
  40   32   24   16    8    7   48
  31   23   15   14    6   47   39
  22   21   13    5   46   38   30

참고: 위의 프로그램은 마방진의 홀수 크기를 입력했을 때만 작동합니다.

제안 알고리즘의 시간 및 공간 복잡도는 $O(n^2)$이다.

작성자 소개

Adnan Ashraf

작성자 프로필 보기