Чарівний квадрат – розгадайте головоломку 3×3 за допомогою C & Python прикладів
Сара Чен
Що таке Магічний квадрат?
Магічний квадрат — це квадратна матриця зі спеціальним розташуванням чисел. Ці числа розташовані так, що сума чисел на кожній діагоналі, рядку та стовпці залишається незмінною. Ігри «Магічні квадрати» — це прості логічні головоломки, які використовуються в розважальній математиці.
Приклад магічних квадратів:
Наведена вище діаграма є прикладом магічного квадрата порядку 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).
