Magisch Vierkant – Los een 3×3-puzzel op met behulp van C- en Python-voorbeelden

Wat is Magisch Vierkant?

Een magisch vierkant is een vierkante matrix met een speciale nummering. Deze getallen zijn zo gerangschikt dat de som van de getallen op elke diagonaal, rij en kolom hetzelfde blijft. Magische sqares spellen zijn eenvoudige logische puzzels die worden gebruikt in de recreatieve wiskunde.

Magische sqares voorbeeld:

Magic Square

Bovenstaand diagram is een voorbeeld van een magisch vierkant van orde 3. De som van elke diagonaal, rij en kolom is 15.

Hoe Magisch Vierkant werkt

Magische sqares zijn n*n matrices bestaande uit n^2 positieve gehele getallen. Het aantal rijen of kolommen van een vierkante matrix wordt de volgorde van de matrix genoemd.

Typisch, magische squares puzzels hebben een oneven volgorde en dragen de gehele getallen van 1 tot n^2. De som van elke diagonaal, rij en kolom is hetzelfde. Dit getal wordt magische som of magische constante genoemd. Over het algemeen hangt deze magische som af van de volgorde van de matrix. De magische squares formule voor de magische som van orde n is-

Magisch Vierkant werkt

Laten we een voorbeeld nemen van een magisch vierkant met gehele getallen 3. De magische som zou dus zijn:

Magisch Vierkant werkt

Magisch Vierkant werkt

Waarom worden ze Magie genoemd?

Wiskundigen uit de oudheid waren gefascineerd door de aard van verschillende interessante combinaties van getallen. Het magische vierkant was er één van. Het vroegste bewijs van magische squares dateert uit China in 190 BCE.

Sommige onderzoeken tonen bewijs van de Magic squares puzzel in het oude Japan, India en Arabië. Op basis van enkele legendes werd aangenomen dat deze speciale getallenformaties verband hielden met de magische wereld. Daarom zijn die squares werden magische squ genoemdares.

Soorten magisch vierkant

Er zijn verschillende varianten van magische squares wiskunde -

  • Normaal magisch vierkant: Dit type magisch vierkant bevat de eerste n^2 getallen.
  • Semi-magisch vierkant: Bij dit type vormen alleen de rijen en de kolom de magische constante.
  • Eenvoudig magisch vierkant: In tegenstelling tot het vorige type vormen de rijen, kolommen en beide diagonalen samen de magische constante.
  • Meest perfecte magische vierkant: Dit is een normaal magisch vierkant met twee bijzondere eigenschappen. Hier komt elk subvierkant van 2 bij 2 van de matrix neer op een totaal van 2(n^2+1). En elk paar getallen dat n/2 squ isares afgezien van de rastersom tot n^2+1.

Op basis van eigenschappen zijn er nog veel meer soorten magische squares. Maar telkens wanneer we alleen maar het magische vierkant noemen, gaan we ervan uit dat het een normaal en eenvoudig magisch vierkant van oneven orde is.

Algoritme om magisch vierkant te genereren

Het algoritme voor het genereren van magische squares is:

  • Het eerste getal of 1 wordt opgeslagen op (n/2, n-1), waarbij de eerste coördinaat de rijpositie is en de tweede coördinaat de kolompositie. Voor later Laten we deze positie aangeven als (x, y).
  • De volgende nummers worden opgeslagen op (x-1, y+1). Als de positie niet geldig is, zullen we het volgende overwegenwing voorwaarden.
    1. Als de rijpositie -1 is, zal deze kromtrekken naar n-1. Op dezelfde manier, als de berekende kolompositie n is, zal deze naar 0 vervormen.
    2. De rijpositie wordt met 1 verhoogd en de kolompositie met 2 verlaagd als de berekende positie al een getal bevat.
    3. Als de rijpositie -1 is en de corresponderende kolompositie n is, is de nieuwe positie (0, n-2.

Opmerking: Dit algoritme genereert alleen geldige magische squares van vreemde orde. We beschouwen dit magische vierkant ook als een normaal magisch vierkant met de eerste n^2 getallen. Bovendien kunnen er meerdere oplossingen zijn voor dezelfde waarde van n.

Laten we een voorbeeld nemen en kijken hoe het werkt. Laten we zeggen dat we het magische vierkant van orde 3 willen vinden. Omdat het een eenvoudig en normaal magisch vierkant van oneven orde zal zijn, zal het alle getallen van 1 tot 3^2 of 9 bevatten.

Hoe het werkt?

Volgens onze algoritme, de stappen zijn de volgendewing:

Stap 1) Het eerste nummer of 1 staat op de (3/2, 3-1) of (1, 2) positie. Beschouw volgens afspraak x= 1 en y= 2 voor later stappen.

Algoritme om magisch vierkant te genereren

Stap 2) De positie voor de rest van de getallen wordt hieronder berekendwing manier-

Positie van nummer 2:

Het volgende getal bevindt zich op (x-1, y+1) of (0, 3), wat geen geldige positie is. Door voorwaarde (a) te gebruiken, zou de overeenkomstige geldige positie (0,0) zijn. Dus x= 0, y= 0.

Algoritme om magisch vierkant te genereren

Positie van nummer 3:

Nummer 3 bevindt zich op (x-1, y+1) of (-1, 1), wat geen geldige positie is. Door voorwaarde (a) te gebruiken, zou de geldige rijpositie n-1 of 2 zijn. Nummer 3 zal dus op (2, 1) staan. Voor het volgende getal, x= 2, y= 1.

Algoritme om magisch vierkant te genereren

Positie van nummer 4:

Nummer 4 moet op (x-1, y+1) of (1, 2) staan, wat een geldige positie is. Maar die positie bevat al een nummer. Volgens voorwaarde (b) zou de geldige positie (1+1, 2-2) of (2,0) zijn. Voor het volgende getal x= 2, y= 0.

Algoritme om magisch vierkant te genereren

Positie van nummer 5:

Nummer 5 moet op (x-1, y+1) of (1, 1) staan, wat een geldige positie is. Voor het volgende getal x= 1, y= 1.

Algoritme om magisch vierkant te genereren

Positie van nummer 6:

Nummer 6 moet op (x-1, y+1) of (0, 2) staan, wat een geldige positie is. Voor het volgende getal x= 0, y= 2.

Algoritme om magisch vierkant te genereren

Positie van nummer 7:

Nummer 7 moet op (x-1, y+1) of (-1, 3) staan, wat geen geldige positie is. Volgens voorwaarde (c) zou de geldige positie (0, n-2) of (0, 1) zijn. Voor het volgende getal x= 0, y= 1.

Algoritme om magisch vierkant te genereren

Positie van nummer 8:

Nummer 8 moet op (x-1, y+1) of (-1, 2) staan, wat geen geldige positie is. Door voorwaarde (a) te gebruiken, zou de geldige positie (2, 2) zijn. Voor het volgende getal x= 2, y= 2.

Algoritme om magisch vierkant te genereren

Positie van nummer 9:

Nummer 9 moet op (x-1, y+1) of (1, 3) staan, wat geen geldige positie is. Door voorwaarde (a) te gebruiken, zou de geldige positie (1, 0) zijn.

Algoritme om magisch vierkant te genereren

Pseudo-code

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++ Code Magisch Vierkant

Input:

/*
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;
}

Uitvoer van voorbeeld:

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 Code Magisch Vierkant

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)

Uitvoer van voorbeeld:

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

complexiteitsanalyse

  • Ruimte Complexiteit: Om de magische vierkante matrix te behouden, hebben we een*n array nodig. Dus de ruimte complexDe eenheid zou O(n^2) zijn.
  • Tijd Complexiteit: De code die we gebruikten om magische squares wiskunde bestaat uit twee lussen. De buitenste lus loopt n keer en de binnenste lus loopt ook n keer. Uiteindelijk is de tijd complexiteit is O(n^2).