Hình vuông ma thuật – Giải câu đố 3×3 bằng C & Python Các ví dụ
Sarah Chen
Hình vuông ma thuật là gì?
Ma phương là một ma trận vuông có cách sắp xếp số đặc biệt. Các số này được sắp xếp sao cho tổng các số trên mỗi đường chéo, hàng và cột vẫn giữ nguyên. Trò chơi ma phương là những câu đố logic đơn giản được sử dụng trong toán học giải trí.
Ví dụ về hình vuông ma thuật:
Sơ đồ trên là một ví dụ về bình phương ma thuật bậc 3. Tổng của mỗi đường chéo, hàng và cột là 15.
Quảng trường ma thuật hoạt động như thế nào
Ma trận vuông là ma trận n*n gồm n^2 số nguyên dương. Số hàng hoặc cột của ma trận vuông được gọi là bậc của ma trận.
Thông thường, các câu đố ma phương có thứ tự lẻ và mang các số nguyên từ 1 đến n^2. Tổng của mỗi đường chéo, hàng và cột là như nhau. Con số này được gọi là tổng ma thuật hoặc hằng số ma thuật. Nhìn chung, tổng ma thuật này phụ thuộc vào thứ tự của ma trận. Công thức ma phương cho tổng ma thuật của thứ tự n là-
Hãy lấy một ví dụ về hình vuông kỳ diệu với số nguyên 3. Vì vậy, tổng kỳ diệu sẽ là-
Tại sao chúng được gọi là Phép thuật?
Các nhà toán học cổ đại bị cuốn hút bởi bản chất của một số tổ hợp số thú vị. Ma phương là một trong số đó. Bằng chứng sớm nhất về ma phương có từ Trung Quốc vào năm 190 TCN.
Một số nghiên cứu cho thấy bằng chứng về câu đố Magic squares ở Nhật Bản, Ấn Độ và Ả Rập cổ đại. Dựa trên một số truyền thuyết, người ta cho rằng những hình dạng số đặc biệt đó có liên quan đến thế giới phép thuật. Do đó, những hình vuông đó được gọi là magic squares.
Các loại hình vuông ma thuật
Có nhiều biến thể khác nhau của toán học ma phương –
- Hình vuông ma thuật thông thường: Loại hình vuông ma thuật này chứa n^2 số đầu tiên.
- Hình vuông bán ma thuật: Trong loại này, chỉ có các hàng và cột có tổng bằng hằng số ma thuật.
- Hình vuông ma thuật đơn giản: Ngược lại với loại trước, các hàng, cột và cả hai đường chéo cộng lại bằng hằng số ma thuật.
- Hình vuông ma thuật hoàn hảo nhất: Đây là một ma phương bình thường với hai tính chất đặc biệt. Ở đây, mỗi ô vuông con 2 x 2 của ma trận cộng lại bằng tổng là 2(n^2+1). Và bất kỳ cặp số nào cách lưới n/2 ô vuông thì tổng bằng n^2+1.
Dựa trên các thuộc tính, có nhiều loại ma phương hơn nữa. Nhưng bất cứ khi nào chúng ta chỉ đề cập đến ma phương, chúng ta cho rằng đó là ma phương chuẩn bậc lẻ và ma phương đơn giản.
Thuật toán tạo hình vuông ma thuật
Thuật toán để tạo ra các ma phương bậc lẻ là:
- Số đầu tiên hoặc 1 sẽ được lưu trữ tại (n/2, n-1), trong đó tọa độ đầu tiên là vị trí hàng và tọa độ thứ hai là vị trí cột. Đối với các bước sau, hãy biểu thị vị trí này là (x, y).
- Các số tiếp theo sẽ được lưu trữ tại (x-1, y+1). Nếu vị trí không hợp lệ, chúng ta sẽ xem xét các điều kiện sau.
- Nếu vị trí hàng là -1, nó sẽ chuyển sang n-1. Tương tự, nếu vị trí cột được tính là n thì nó sẽ cong về 0.
- Vị trí hàng sẽ tăng thêm 1 và vị trí cột sẽ giảm đi 2 nếu vị trí được tính đã chứa một số.
- Nếu vị trí hàng là -1 và vị trí cột tương ứng là n thì vị trí mới sẽ là (0, n-2.
Lưu ý: Thuật toán này chỉ tạo ra các ma phương hợp lệ có thứ tự lẻ. Chúng tôi cũng coi ma phương này là ma phương chuẩn với n^2 số đầu tiên. Hơn nữa, có thể có nhiều giải pháp cho cùng một giá trị n.
Hãy lấy một ví dụ và xem nó hoạt động như thế nào. Giả sử chúng ta muốn tìm ma phương bậc 3. Vì đây là một ma phương đơn giản và bình thường bậc lẻ nên nó sẽ chứa tất cả các số từ 1 đến 3^2 hoặc 9.
Cách thức học?
Theo chúng tôi thuật toán, các bước sẽ như sau:
Bước 1) Số đầu tiên hoặc 1 sẽ ở vị trí (3/2, 3-1) hoặc (1, 2). Theo quy ước, hãy xem xét x= 1 và y= 2 cho các bước sau.
Bước 2) Vị trí của các số còn lại sẽ được tính theo cách sau:
Vị trí của số 2:
Số tiếp theo sẽ ở (x-1, y+1) hoặc (0, 3), đây không phải là vị trí hợp lệ. Bằng cách sử dụng điều kiện (a), vị trí hợp lệ tương ứng sẽ là (0,0). Vì vậy, x= 0, y= 0.
Vị trí của số 3:
Số 3 sẽ ở (x-1, y+1) hoặc (-1, 1), đây không phải là vị trí hợp lệ. Bằng cách sử dụng điều kiện (a), vị trí hàng hợp lệ sẽ là n-1 hoặc 2. Vì vậy, số 3 sẽ ở (2, 1). Đối với số tiếp theo, x= 2, y= 1.
Vị trí của số 4:
Số 4 phải ở (x-1, y+1) hoặc (1, 2) là vị trí hợp lệ. Nhưng vị trí đó đã chứa một con số. Theo điều kiện (b), vị trí hợp lệ sẽ là (1+1, 2-2) hoặc (2,0). Đối với số tiếp theo x= 2, y= 0.
Vị trí của số 5:
Số 5 phải ở (x-1, y+1) hoặc (1, 1) là vị trí hợp lệ. Đối với số tiếp theo x= 1, y= 1.
Vị trí của số 6:
Số 6 phải ở (x-1, y+1) hoặc (0, 2) là vị trí hợp lệ. Đối với số tiếp theo x= 0, y= 2.
Vị trí của số 7:
Số 7 phải ở (x-1, y+1) hoặc (-1, 3) không phải là vị trí hợp lệ. Theo điều kiện (c), vị trí hợp lệ sẽ là (0, n-2) hoặc (0, 1). Với số tiếp theo x= 0, y= 1.
Vị trí của số 8:
Số 8 phải ở (x-1, y+1) hoặc (-1, 2) không phải là vị trí hợp lệ. Bằng cách sử dụng điều kiện (a), vị trí hợp lệ sẽ là (2, 2). Với số tiếp theo x= 2, y= 2.
Vị trí của số 9:
Số 9 phải ở (x-1, y+1) hoặc (1, 3) không phải là vị trí hợp lệ. Bằng cách sử dụng điều kiện (a), vị trí hợp lệ sẽ là (1, 0).
Mã giả
Begin Declare an array of size n*n Initialize the array to 0 Set row = n/2 Set column = n-1 For all number i: from 1 to n*n If the row = -1 and column = n row = 0 column = n-2 Else If row = -1 row = n-1 If column = n column = 0 If the position already contains a number decrement column by 2 increment row by 1 continue until the position is not 0 Else put the number i into the calculated position increment i Increment column value Decrement row value End
C++ Mã ma thuật vuông
Đầu vào:
/*
A C/C++ program for generating odd order magic squares
*/
#include <bits/stdc++.h>
using namespace std;
void GenerateMagicSquare(int n)
{
int magic[n][n];
//initializing the array
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
magic[i][j] = 0;
//setting row and column value
int i = n / 2;
int j = n - 1;
for (int k = 1; k <= n * n;)
{
//checking condition (c)
if (i == -1 && j == n)
{
j = n - 2;
i = 0;
}
else
{
//checking condition (a)
if (j == n)
j = 0;
if (i < 0)
i = n - 1;
}
//checking condition (b)
if (magic[i][j])
{
j -= 2;
i++;
continue;
}
else
{
//placing the number into the array
magic[i][j] = k;
k++;
}
//for the next number setting (i-1, j+1)
j++;
i--;
}
//printing the matrix
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cout << magic[i][j] << " ";
cout << endl;
}
}
int main()
{
//This code works for only odd numbers
int n = 7;
cout<<"The magic sum is " << n*(n*n+1)/2 <<endl;
GenerateMagicSquare(n);
return 0;
}
Đầu ra của ví dụ:
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
Python Mã ma thuật vuông
def GenerateMagicSquare(n):
#initializing the array
magic = [[0 for x in range(n)]
for y in range(n)]
#setting row and column value
i = n // 2
j = n - 1
k = 1
while k <= (n * n):
#checking condition (c)
if i == -1 and j == n:
j = n - 2
i = 0
else:
#checking condition (a)
if j == n:
j = 0
if i < 0:
i = n - 1
#checking conditon (b)
if magic[i][j]:
j = j - 2
i = i + 1
continue
else:
#placing the number into the array
magic[i][j] = k
k = k + 1
#for the next number setting (i-1, j+1)
j = j + 1
i = i - 1
#printing the matrix
for i in range(0, n):
for j in range(0, n):
print('%2d ' % (magic[i][j]),end='')
if j == n - 1:
print()
#This code works for only odd numbers
n = 7
print("The magic sum is ",n * (n * n + 1) // 2, "\n")
GenerateMagicSquare(n)
Đầu ra của ví dụ:
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
Phân tích độ phức tạp
- Không gian phức tạp: Để duy trì ma trận vuông ma thuật, chúng ta cần một mảng *n. Vì vậy, độ phức tạp không gian sẽ là O(n^2).
- Độ phức tạp về thời gian: Mã mà chúng tôi sử dụng để tạo ra các phép toán ma thuật hình vuông bao gồm hai vòng lặp. Vòng lặp bên ngoài chạy n lần và vòng lặp bên trong cũng chạy n lần. Cuối cùng, độ phức tạp thời gian là O(n^2).
