Magický čtverec – Vyřešte hádanku 3×3 pomocí C & Python Příklady
Sarah Chen
Co je Magic Square?
Magický čtverec je čtvercová matice se speciálním uspořádáním čísel. Tato čísla jsou uspořádána tak, aby součet čísel na každé diagonále, řádku a sloupci zůstal stejný. Hry s magickými čtverci jsou jednoduché logické hádanky používané v rekreační matematice.
Příklad magických čtverců:
Výše uvedený diagram je příklad magického čtverce řádu 3. Součet každé úhlopříčky, řádku a sloupce je 15.
Jak Magic Square funguje
Magické čtverce jsou n*n matic sestávajících z n^2 kladných celých čísel. Počet řádků nebo sloupců čtvercové matice se nazývá řád matice.
Hádanky magických čtverců mají obvykle liché pořadí a nesou celá čísla od 1 do n^2. Součet každé úhlopříčky, řádku a sloupce je stejný. Toto číslo se nazývá magický součet nebo magická konstanta. Obecně platí, že tato magická suma závisí na pořadí matice. Vzorec magických čtverců pro magický součet řádu n je-
Vezměme si příklad magického čtverce s celými čísly 3. Magický součet by tedy byl-
Proč se jim říká magie?
Starověcí matematici byli fascinováni povahou několika zajímavých kombinací čísel. Magický čtverec byl jedním z nich. Nejstarší důkazy o magických čtvercích pocházejí z Číny v roce 190 před naším letopočtem.
Některé studie ukazují důkazy o magických čtvercích ve starověkém Japonsku, Indii a Arábii. Na základě některých legend se předpokládalo, že tyto zvláštní útvary čísel byly spojeny s magickým světem. Proto byly tyto čtverce pojmenovány magické čtverce.
Typy magického čtverce
Existují různé varianty matematiky magických čtverců –
- Normální magický čtverec: Tento typ magického čtverce obsahuje prvních n^2 čísel.
- Semi-Magic Square: V tomto typu se do magické konstanty sčítají pouze řádky a sloupec.
- Jednoduchý kouzelný čtverec: Na rozdíl od předchozího typu se řádky, sloupce a obě úhlopříčky sčítají do magické konstanty.
- Nejdokonalejší magický čtverec: Toto je normální magický čtverec se dvěma speciálními vlastnostmi. Zde každý 2 x 2 dílčí čtverec matice dává dohromady 2 (n^2+1). A libovolná dvojice čísel, která jsou n/2 čtverců od součtu mřížky na n^2+1.
Na základě vlastností existuje mnohem více druhů magických čtverců. Ale kdykoli se zmíníme o magickém čtverci, předpokládáme, že jde o normální a jednoduchý magický čtverec lichého řádu.
Algoritmus pro generování magického čtverce
Algoritmus pro generování magických čtverců lichého řádu je:
- První číslo nebo 1 bude uloženo jako (n/2, n-1), kde první souřadnice je pozice řádku a druhá souřadnice je pozice sloupce. Pro pozdější kroky označme tuto pozici jako (x, y).
- Další čísla budou uložena jako (x-1, y+1). Pokud pozice není platná, zvážíme následující podmínky.
- Pokud je pozice řádku -1, bude se deformovat na n-1. Podobně, pokud je vypočítaná pozice sloupce n, bude se deformovat na 0.
- Pozice řádku se zvýší o 1 a pozice sloupce se sníží o 2, pokud vypočtená pozice již obsahuje číslo.
- Pokud je pozice řádku -1 a odpovídající pozice sloupce je n, bude nová pozice (0, n-2.
Poznámka: Tento algoritmus generuje pouze platné magické čtverce lichého řádu. Tento magický čtverec také považujeme za normální magický čtverec s prvními n^2 čísly. Navíc pro stejnou hodnotu n může být více řešení.
Vezměme si příklad a uvidíme, jak to funguje. Řekněme, že chceme najít magický čtverec řádu 3. Protože to bude jednoduchý a normální magický čtverec lichého řádu, bude obsahovat všechna čísla od 1 do 3^2 nebo 9.
Jak to funguje?
Podle našich algoritmus, kroky budou následující:
Krok 1) První číslo nebo 1 bude na pozici (3/2, 3-1) nebo (1, 2). Podle konvence zvažte x= 1 a y= 2 pro pozdější kroky.
Krok 2) Pozice pro zbytek čísel bude vypočítána následujícím způsobem-
Pozice čísla 2:
Další číslo bude na (x-1, y+1) nebo (0, 3), což není platná pozice. Při použití podmínky (a) by odpovídající platná pozice byla (0,0). Takže x = 0, y = 0.
Pozice čísla 3:
Číslo 3 bude na (x-1, y+1) nebo (-1, 1), což není platná pozice. Při použití podmínky (a) by platná pozice řádku byla n-1 nebo 2. Takže číslo 3 bude na (2, 1). Pro další číslo, x= 2, y= 1.
Pozice čísla 4:
Číslo 4 by mělo být na (x-1, y+1) nebo (1, 2), což je platná pozice. Ale tato pozice již obsahuje číslo. Podle podmínky (b) by platná pozice byla (1+1, 2-2) nebo (2,0). Pro další číslo x= 2 je y= 0.
Pozice čísla 5:
Číslo 5 by mělo být na (x-1, y+1) nebo (1, 1), což je platná pozice. Pro další číslo x= 1 je y= 1.
Pozice čísla 6:
Číslo 6 by mělo být na (x-1, y+1) nebo (0, 2), což je platná pozice. Pro další číslo x= 0 je y= 2.
Pozice čísla 7:
Číslo 7 by mělo být na (x-1, y+1) nebo (-1, 3), což není platná pozice. Podle podmínky (c) by platná pozice byla (0, n-2) nebo (0, 1). Pro další číslo x= 0, y= 1.
Pozice čísla 8:
Číslo 8 by mělo být na (x-1, y+1) nebo (-1, 2), což není platná pozice. Při použití podmínky (a) by platná pozice byla (2, 2). Pro další číslo x= 2 je y= 2.
Pozice čísla 9:
Číslo 9 by mělo být na (x-1, y+1) nebo (1, 3), což není platná pozice. Při použití podmínky (a) by platná pozice byla (1, 0).
Pseudo kód
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++ Kouzelný čtverec kódu
Vstup:
/*
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;
}
Výstup příkladu:
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 Kouzelný čtverec kódu
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)
Výstup příkladu:
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
Analýza složitosti
- Prostorová složitost: Abychom zachovali magickou čtvercovou matici, potřebujeme pole *n. Prostorová složitost by tedy byla O(n^2).
- Časová složitost: Kód, který jsme použili ke generování magických čtverců, se skládá ze dvou smyček. Vnější smyčka běží nkrát a vnitřní smyčka také běží nkrát. Časová složitost je nakonec O(n^2).
