C++ の魔方陣問題
この記事では、魔方陣問題とその性質、および C++ を使用したその実装について説明します。 魔方陣を実装するために魔方陣問題を学びましょう。
魔方陣問題
魔方陣は、正の整数の 2D 配列で、各行、列、および対角線の合計が同じです。 合計は、Magic Sum と呼ばれることが多く、行、列、および対角の各定数の合計を指します。
魔方陣の各位置の整数値は一意でなければなりません。 N が魔方陣のサイズである場合、1 から N2 までの整数を含めることができます。
次の式は、魔法の合計を計算します。
魔方陣のサイズは、行と列の数を示します。 N が 3 の場合、魔方陣は 3 行 3 列になります。
では、例を挙げて魔力和について説明しましょう。 N の値を 3 とすると、上記の式から次のように計算できます。
ここで、15 は魔法の合計です。 これは、各列、行、対角線の合計が 15 になることを意味します。
サイズが 3 の魔方陣を下の図に示します。
各行、列、および対角線の合計が魔法の合計に等しく、すべてのエントリが一意であることがわかります。
魔方陣問題を理解したら、実装してみましょう。
実装する魔方陣のサイズを n とします。 次に、最初の値 (つまり 1) が魔方陣の (n/2,n-1) の位置に格納されます。
この位置を (i,j) とすると、次の値は位置 (i-1,j+1) になります。 ここでは、すべての行と列にラップアラウンドがあると仮定します (つまり、循環型としても知られています)。
魔方陣問題の条件
- 次の値の位置は、現在の列番号に
1を加算し、現在の行番号から1を引いて決定されます。- 列の新しい位置が
nになると、列と行が循環するため0にラップされます。 - 同様に、カラスの新しい位置が
-1になる場合、n-1にラップされます。
- 列の新しい位置が
- 新しく計算された場所にすでに値が含まれているとします。 その場合、現在の行番号は
1を追加することで更新され、現在の列番号はそこから2を減算することで更新されます。 - 新しく計算された列番号が
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 の位置は = (3/2,3-1) = (1,2) =
[1][2]です。 - 値 2 の位置は = (1-1,2+1) = (1,2) =
[1][2]です。 - 値 3 の位置は = (0-1,0+1) = (3-1,1+1) =
[2][1]です。 - 値 4 の位置は = (2-1,1+1) = (1,2) =
[1][2]です。[1][2]はすでに値 1 を持っているため、条件 2 により、新しい場所は (1+1,2-2) =[2][0]になります。
- 値 5 の位置は = (2-1,0+1) = (1,1) =
[1][1]です。 - 値 6 の位置は = (1-1,1+1) = (1,2) =
[0][2]です。 - 値 7 の位置 = (0-1,2+1) = (-1,3)
- 条件 3 が成立するため、新しい位置は (0,3-2)=
[0][1]になります。
- 条件 3 が成立するため、新しい位置は (0,3-2)=
- 値 8 の位置は = (0-1,1+1) = (-1,2) =
[2][2]で、条件 1 行がラップされます。 - 値 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)$ です。