Магически квадрат – Решете пъзел 3×3 с помощта на C & Python Примери
Сара Чен
Какво е Magic Square?
Магическият квадрат е квадратна матрица със специално подреждане на числата. Тези числа са подредени така, че сумата от числата на всеки диагонал, ред и колона остава същата. Игрите с магически квадрати са прости логически пъзели, използвани в развлекателната математика.
Пример за магически квадрати:
Посочената по-горе диаграма е пример за магически квадрат от порядък 3. Сборът на всеки диагонал, ред и колона е 15.
Как работи Magic Square
Магическите квадрати са n*n матрици, състоящи се от n^2 положителни цели числа. Броят на редовете или колоните на квадратна матрица се нарича ред на матрицата.
Обикновено пъзелите с магически квадрати имат нечетен ред и носят цели числа от 1 до n^2. Сумата на всеки диагонал, ред и колона е една и съща. Това число се нарича магическа сума или магическа константа. Като цяло тази магическа сума зависи от реда на матрицата. Формулата на магическите квадрати за магическата сума от ред n е-
Нека вземем пример за магически квадрат с цели числа 3. И така, магическата сума ще бъде-
Защо се наричат Магия?
Древните математици са били очаровани от природата на няколко интересни комбинации от числа. Магическият квадрат беше един от тях. Най-ранните доказателства за магически квадрати датират от Китай през 190 г. пр.н.е.
Някои проучвания показват доказателства за пъзел с магически квадрати в древна Япония, Индия и Арабия. Въз основа на някои легенди се предполагаше, че тези специални образувания от числа са свързани с магическия свят. Следователно тези квадрати бяха наречени магически квадрати.
Видове магически квадрат
Има различни варианти на математиката с магически квадрати –
- Нормален магически квадрат: Този тип магически квадрат съдържа първите n^2 числа.
- Полумагически квадрат: В този тип само редовете и колоната сумират до магическата константа.
- Прост магически квадрат: За разлика от предишния тип, редовете, колоните и двата диагонала сумират до магическата константа.
- Най-съвършеният магически квадрат: Това е нормален магически квадрат с две специални свойства. Тук всеки подквадрат 2 на 2 на матрицата дава общо 2(n^2+1). И всяка двойка числа, които са n/2 квадрата извън решетката, се събират до n^2+1.
Въз основа на свойствата има много повече видове магически квадрати. Но когато просто споменем магическия квадрат, приемаме, че това е нормален и прост магически квадрат от нечетен ред.
Алгоритъм за генериране на магически квадрат
Алгоритъмът за генериране на магически квадрати от нечетен ред е:
- Първото число или 1 ще бъде съхранено в (n/2, n-1), където първата координата е позицията на реда, а втората координата е позицията на колоната. За по-късни стъпки нека обозначим тази позиция като (x, y).
- Следващите числа ще бъдат съхранени в (x-1, y+1). Ако позицията не е валидна, тогава ще разгледаме следните условия.
- Ако позицията на реда е -1, тя ще се изкриви до n-1. По същия начин, ако изчислената позиция на колоната е n, тя ще се изкриви до 0.
- Позицията на реда ще бъде увеличена с 1, а позицията на колоната ще бъде намалена с 2, ако изчислената позиция вече съдържа число.
- Ако позицията на реда е -1 и позицията на съответната колона е n, новата позиция ще бъде (0, n-2.
Забележка: Този алгоритъм генерира само валидни магически квадрати от нечетен ред. Също така считаме този магически квадрат за нормален магически квадрат с първите n^2 числа. Освен това може да има множество решения за една и съща стойност на n.
Нека вземем пример и да видим как работи. Да кажем, че искаме да намерим магическия квадрат от порядък 3. Тъй като това ще бъде прост и нормален магически квадрат от нечетен ред, той ще съдържа всички числа от 1 до 3^2 или 9.
Как работи?
Според нашия алгоритъм, стъпките ще бъдат следните:
Стъпка 1) Първото число или 1 ще бъде на позиция (3/2, 3-1) или (1, 2). По конвенция вземете x= 1 и y= 2 за по-късни стъпки.
Стъпка 2) Позицията за останалите числа ще бъде изчислена по следния начин-
Позиция на номер 2:
Следващото число ще бъде на (x-1, y+1) или (0, 3), което не е валидна позиция. Чрез използване на условие (a), съответната валидна позиция ще бъде (0,0). И така, x= 0, y= 0.
Позиция на номер 3:
Номер 3 ще бъде на (x-1, y+1) или (-1, 1), което не е валидна позиция. Чрез използване на условие (a), валидната позиция на ред ще бъде n-1 или 2. Така че номер 3 ще бъде на (2, 1). За следващото число x= 2, y= 1.
Позиция на номер 4:
Число 4 трябва да е на (x-1, y+1) или (1, 2), което е валидна позиция. Но тази позиция вече съдържа число. Съгласно условие (b), валидната позиция би била (1+1, 2-2) или (2,0). За следващото число x= 2, y= 0.
Позиция на номер 5:
Число 5 трябва да е на (x-1, y+1) или (1, 1), което е валидна позиция. За следващото число x= 1, y= 1.
Позиция на номер 6:
Число 6 трябва да е на (x-1, y+1) или (0, 2), което е валидна позиция. За следващото число x= 0, y= 2.
Позиция на номер 7:
Число 7 трябва да бъде на (x-1, y+1) или (-1, 3), което не е валидна позиция. Съгласно условие (c), валидната позиция би била (0, n-2) или (0, 1). За следващото число x= 0, y= 1.
Позиция на номер 8:
Число 8 трябва да е на (x-1, y+1) или (-1, 2), което не е валидна позиция. Чрез използване на условие (a), валидната позиция ще бъде (2, 2). За следващото число x= 2, y= 2.
Позиция на номер 9:
Число 9 трябва да е на (x-1, y+1) или (1, 3), което не е валидна позиция. Чрез използване на условие (a), валидната позиция ще бъде (1, 0).
Псевдо код
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++ Код магически квадрат
Вход:
/*
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;
}
Резултат от пример:
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 Код магически квадрат
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)
Резултат от пример:
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
Анализ на сложността
- Космическа сложност: За да поддържаме матрицата на магическия квадрат, ни е необходим *n масив. Така че пространствената сложност ще бъде O(n^2).
- Времева сложност: Кодът, който използвахме за генериране на математика с магически квадрати, се състои от два цикъла. Външният цикъл се изпълнява n пъти, а вътрешният цикъл също се изпълнява n пъти. В крайна сметка времевата сложност е O(n^2).
