Magisches-Quadrat-Problem in C++

1. Problem des magischen Quadrats
2. Implementierung des Magic Square in C++

Dieser Artikel erklärt das Problem des magischen Quadrats, seine Eigenschaften und seine Implementierung in C++. Lassen Sie uns das Problem des magischen Quadrats lernen, um das magische Quadrat zu implementieren.

Problem des magischen Quadrats

Ein magisches Quadrat ist ein 2D-Array aus positiven ganzen Zahlen, bei dem die Summe jeder Zeile, Spalte und Diagonale gleich ist. Die Summe wird oft als magische Summe bezeichnet, was sich auf eine konstante Summe in jeder Zeile, Spalte und Diagonale bezieht.

Der ganzzahlige Wert an jeder Position des magischen Quadrats muss eindeutig sein. Wenn N die Grösse eines magischen Quadrats hat, kann es ganze Zahlen von 1 bis N² enthalten.

Die folgende Formel berechnet die magische Summe.

Die Größe des magischen Quadrats würde die Anzahl der Zeilen und Spalten anzeigen. Wenn N gleich 3 ist, hat das magische Quadrat drei Zeilen und drei Spalten.

Lassen Sie uns nun die magische Summe anhand eines Beispiels erklären. Angenommen, der Wert von N ist 3, dann kann er mit der obigen Formel wie folgt berechnet werden:

Hier ist 15 die magische Summe. Dies impliziert, dass jede Spalte, Zeile und Diagonalsumme gleich 15 sein sollte.

Das magische Quadrat mit einer Größe von 3 ist in der folgenden Abbildung dargestellt.

Wir können sehen, dass jede Zeile, Spalte und Diagonalsumme gleich der magischen Summe ist und jeder Eintrag einzigartig ist.

Nachdem wir das Problem des magischen Quadrats verstanden haben, wollen wir es jetzt implementieren.

Lassen Sie die Größe des magischen Quadrats, das wir implementieren werden, n sein. Dann wird der erste Wert (d. h. 1) an der Position (n/2,n-1) im magischen Quadrat gespeichert.

Angenommen, diese Position ist (i,j), dann befindet sich der nächste Wert an Position (i-1,j+1). Hier gehen wir davon aus, dass jede Zeile und Spalte einen Wrap-Around hat (d.h. auch bekannt als Circler-Mode).

Bedingungen für das Problem des magischen Quadrats

1. Die Position des nächsten Werts wird bestimmt, indem 1 zur aktuellen Spaltennummer addiert und 1 von der aktuellen Zeilennummer subtrahiert wird.
   • Wenn die neue Position der Spalte zu n wird, wird sie zu 0 umgebrochen, da Spalten und Zeilen kreisförmig sind.
   • Ähnlich, wenn die neue Position der Krähe zu -1 wird, wird sie zu n-1 gewickelt.
2. Angenommen, der neu berechnete Standort enthält bereits einen Wert. In diesem Fall wird die aktuelle Zeilennummer aktualisiert, indem 1 hinzugefügt wird, und die aktuelle Spaltennummer wird aktualisiert, indem 2 davon subtrahiert wird.
3. Wenn die neu berechnete Spaltennummer n und die Zeilennummer -1 ist, dann ist die aktualisierte Position (0,n-2).

Implementierung des Magic Square in C++

Schauen wir uns den folgenden Code an, bevor wir uns mit den Details befassen:

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

Hier ist eine Schritt-für-Schritt-Erklärung des obigen Programms für magische Quadrate.

1. Stelle des Wertes 1 ist = (3/2,3-1) = (1,2) = [1][2].
2. Ort des Wertes 2 ist = (1-1,2+1) = (1,2) = [1][2].
3. Ort des Wertes 3 ist = (0-1,0+1) = (3-1,1+1) = [2][1].
4. Ort des Wertes 4 ist = (2-1,1+1) = (1,2) = [1][2].
   • Da [1][2] bereits den Wert 1 hat, ist nach Bedingung 2 ein neuer Standort (1+1,2-2) = [2][0].
5. Ort des Wertes 5 ist = (2-1,0+1) = (1,1) = [1][1].
6. Ort des Wertes 6 ist = (1-1,1+1) = (1,2) = [0][2].
7. Ort des Wertes 7 ist = (0-1,2+1) = (-1,3)
   • Bedingung 3 gilt, also ist die neue Position (0,3-2)=[0][1].
8. Position von Wert 8 ist = (0-1,1+1) = (-1,2) = [2][2], da durch die Bedingung 1 Zeile umgebrochen wird.
9. Position von Wert 9 ist = (2-1,2+1) = (1,3) = [1][0], da durch Bedingung 1 Spalte umgebrochen wird.

Hier ist die Ausgabe, wenn wir die Größe des magischen Quadrats 3 eingeben.

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

Hier ist die Ausgabe, wenn wir die Größe des magischen Quadrats 7 eingeben.

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

Hinweis: Das obige Programm funktioniert nur, wenn wir die ungerade Größe des magischen Quadrats eingeben.

Die zeitliche und räumliche Komplexität des vorgeschlagenen Algorithmus beträgt $O(n^2)$.