Magiczny kwadrat – rozwiąż puzzle 3×3 za pomocą C i Python Przykłady
Sara Chen
Co to jest Magiczny Kwadrat?
Magiczny kwadrat to kwadratowa macierz ze specjalnym układem liczb. Liczby te są ułożone tak, że suma liczb na każdej przekątnej, w każdym rzędzie i każdej kolumnie pozostaje taka sama. Gry w magiczne kwadraty to proste łamigłówki logiczne stosowane w matematyce rekreacyjnej.
Przykład kwadratów magicznych:
Powyższy diagram jest przykładem magicznego kwadratu rzędu 3. Suma każdej przekątnej, wiersza i kolumny wynosi 15.
Jak działa Magiczny Kwadrat
Magiczne kwadraty to macierze n*n składające się z n^2 dodatnich liczb całkowitych. Liczba wierszy lub kolumn macierzy kwadratowej nazywana jest rzędem macierzy.
Zazwyczaj łamigłówki magicznych kwadratów mają nieparzyste rzędy i zawierają liczby całkowite od 1 do n^2. Suma każdej przekątnej, wiersza i kolumny jest taka sama. Liczba ta nazywana jest magiczną sumą lub magiczną stałą. Zazwyczaj ta magiczna suma zależy od rzędu macierzy. Wzór magicznych kwadratów na magiczną sumę rzędu n to-
Weźmy przykład magicznego kwadratu z liczbami całkowitymi 3. Zatem magiczna suma będzie wynosić:
Dlaczego nazywa się je Magią?
Starożytni matematycy byli zafascynowani naturą kilku interesujących kombinacji liczb. Jednym z nich był magiczny kwadrat. Najwcześniejsze dowody magicznych kwadratów pochodzą z Chin z 190 r. p.n.e.
Niektóre badania wskazują na istnienie zagadki magicznych kwadratów w starożytnej Japonii, Indiach i Arabii. Na podstawie niektórych legend przyjęto, że te specjalne formacje liczb były powiązane ze światem magicznym. Stąd też te kwadraty nazwano magicznymi kwadratami.
Rodzaje kwadratu magicznego
Istnieją różne odmiany matematyki kwadratów magicznych –
- Normalny magiczny kwadrat: Ten typ kwadratu magicznego zawiera pierwsze n^2 liczb.
- Kwadrat półmagiczny: W tym typie tylko wiersze i kolumny sumują się do magicznej stałej.
- Prosty magiczny kwadrat: W przeciwieństwie do poprzedniego typu, wiersze, kolumny i obie przekątne sumują się, tworząc magiczną stałą.
- Najdoskonalszy magiczny kwadrat: To jest normalny magiczny kwadrat z dwiema specjalnymi właściwościami. Tutaj każdy 2 na 2 podkwadrat macierzy sumuje się do 2(n^2+1). A każda para liczb, która jest n/2 kwadratów oddzielona od siatki, sumuje się do n^2+1.
Na podstawie właściwości istnieje wiele innych typów magicznych kwadratów. Ale kiedykolwiek wspominamy o magicznym kwadracie, zakładamy, że jest to nieparzysty, normalny i prosty magiczny kwadrat.
Algorytm generowania kwadratu magicznego
Algorytm generowania magicznych kwadratów nieparzystego rzędu jest następujący:
- Pierwsza liczba lub 1 zostanie zapisana w (n/2, n-1), gdzie pierwsza współrzędna jest pozycją wiersza, a druga współrzędna jest pozycją kolumny. W późniejszych krokach oznaczmy tę pozycję jako (x, y).
- Następne liczby zostaną zapisane w (x-1, y+1). Jeśli pozycja nie jest prawidłowa, rozważymy następujące warunki.
- Jeśli pozycja wiersza wynosi -1, zostanie ona przekształcona do n-1. Podobnie, jeśli obliczona pozycja kolumny wynosi n, zostanie ona zmieniona na 0.
- Pozycja w wierszu zostanie zwiększona o 1, a pozycja w kolumnie zostanie zmniejszona o 2, jeśli obliczona pozycja zawiera już liczbę.
- Jeśli pozycja w wierszu wynosi -1, a odpowiadająca pozycja w kolumnie to n, nową pozycją będzie (0, n-2.
Uwaga: Ten algorytm generuje tylko prawidłowe kwadraty magiczne nieparzystego rzędu. Uważamy również ten kwadrat magiczny za normalny kwadrat magiczny z pierwszymi n^2 liczbami. Co więcej, dla tej samej wartości n może być wiele rozwiązań.
Weźmy przykład i zobaczmy, jak to działa. Powiedzmy, że chcemy znaleźć magiczny kwadrat rzędu 3. Ponieważ będzie to prosty i normalny magiczny kwadrat rzędu nieparzystego, będzie zawierał wszystkie liczby od 1 do 3^2 lub 9.
Jak to działa?
Według naszych algorytm, kroki będą następujące:
Krok 1) Pierwsza liczba lub 1 będzie na pozycji (3/2, 3-1) lub (1, 2). Zgodnie z konwencją, rozważmy x= 1 i y= 2 w późniejszych krokach.
Krok 2) Pozycję pozostałych liczb oblicza się w następujący sposób:
Pozycja numeru 2:
Następna liczba będzie znajdować się w (x-1, y+1) lub (0, 3), co nie jest prawidłową pozycją. Stosując warunek (a), odpowiednią prawidłową pozycją będzie (0,0). Zatem x= 0, y= 0.
Pozycja numeru 3:
Numer 3 będzie w (x-1, y+1) lub (-1, 1), co nie jest prawidłową pozycją. Stosując warunek (a), prawidłową pozycją w wierszu będzie n-1 lub 2. Zatem liczba 3 będzie wynosić (2, 1). Dla następnej liczby x= 2, y= 1.
Pozycja numeru 4:
Liczba 4 powinna znajdować się w (x-1, y+1) lub (1, 2), co jest prawidłową pozycją. Ale ta pozycja zawiera już liczbę. Zgodnie z warunkiem (b) prawidłową pozycją byłoby (1+1, 2-2) lub (2,0). Dla następnej liczby x= 2, y= 0.
Pozycja numeru 5:
Liczba 5 powinna znajdować się w (x-1, y+1) lub (1, 1), co jest prawidłową pozycją. Dla następnej liczby x= 1, y= 1.
Pozycja numeru 6:
Liczba 6 powinna znajdować się w (x-1, y+1) lub (0, 2), co jest prawidłową pozycją. Dla następnej liczby x= 0, y= 2.
Pozycja numeru 7:
Liczba 7 powinna znajdować się w (x-1, y+1) lub (-1, 3), co nie jest prawidłową pozycją. Zgodnie z warunkiem (c) prawidłową pozycją będzie (0, n-2) lub (0, 1). Dla następnej liczby x= 0, y= 1.
Pozycja numeru 8:
Liczba 8 powinna znajdować się w (x-1, y+1) lub (-1, 2), co nie jest prawidłową pozycją. Stosując warunek (a), prawidłową pozycją będzie (2, 2). Dla następnej liczby x= 2, y= 2.
Pozycja numeru 9:
Liczba 9 powinna znajdować się w (x-1, y+1) lub (1, 3), co nie jest prawidłową pozycją. Stosując warunek (a), prawidłową pozycją będzie (1, 0).
Pseudo kod
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++ Kod Magiczny Kwadrat
Wejście:
/*
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;
}
Dane wyjściowe przykładu:
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 Kod Magiczny Kwadrat
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)
Dane wyjściowe przykładu:
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
Analiza złożoności
- Złożoność przestrzeni: Aby utrzymać macierz magicznych kwadratów, potrzebujemy tablicy *n. Zatem złożoność przestrzenna wyniesie O(n^2).
- Złożoność czasowa: Kod, którego użyliśmy do wygenerowania matematyki magicznych kwadratów, składa się z dwóch pętli. Zewnętrzna pętla działa n razy, a wewnętrzna pętla również działa n razy. Ostatecznie złożoność czasowa wynosi O(n^2).
