Magic Square – Λύστε παζλ 3×3 χρησιμοποιώντας C & Python Παραδείγματα
Σάρα Τσεν
Τι είναι το Magic Square;
Ένα μαγικό τετράγωνο είναι ένας τετράγωνος πίνακας με ειδική διάταξη αριθμών. Αυτοί οι αριθμοί είναι διατεταγμένοι έτσι ώστε το άθροισμα των αριθμών σε κάθε διαγώνιο, γραμμή και στήλη να παραμένει το ίδιο. Τα παιχνίδια μαγικών τετραγώνων είναι απλά λογικά παζλ που χρησιμοποιούνται στα ψυχαγωγικά μαθηματικά.
Παράδειγμα μαγικών τετραγώνων:
Το παραπάνω διάγραμμα είναι ένα παράδειγμα μαγικού τετραγώνου τάξης 3. Το άθροισμα κάθε διαγωνίου, γραμμής και στήλης είναι 15.
Πώς λειτουργεί το Magic Square
Τα μαγικά τετράγωνα είναι n*n πίνακες που αποτελούνται από n^2 θετικούς ακέραιους αριθμούς. Ο αριθμός των γραμμών ή στηλών ενός τετραγωνικού πίνακα ονομάζεται σειρά του πίνακα.
Συνήθως, τα παζλ μαγικών τετραγώνων έχουν περιττές παραγγελίες και φέρουν τους ακέραιους αριθμούς από το 1 έως το n^2. Το άθροισμα κάθε διαγωνίου, γραμμής και στήλης είναι το ίδιο. Αυτός ο αριθμός ονομάζεται μαγικό άθροισμα ή μαγική σταθερά. Γενικά, αυτό το μαγικό άθροισμα εξαρτάται από τη σειρά του πίνακα. Ο τύπος των μαγικών τετραγώνων για το μαγικό άθροισμα της τάξης n είναι-
Ας πάρουμε ένα παράδειγμα μαγικού τετραγώνου με ακέραιους αριθμούς 3. Έτσι, το μαγικό άθροισμα θα ήταν-
Γιατί ονομάζονται Magic;
Οι αρχαίοι μαθηματικοί γοητεύτηκαν από τη φύση αρκετών ενδιαφέροντων συνδυασμών αριθμών. Το μαγικό τετράγωνο ήταν ένα από αυτά. Τα πρώτα στοιχεία για μαγικά τετράγωνα χρονολογούνται από την Κίνα το 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), το οποίο δεν είναι έγκυρη θέση. Χρησιμοποιώντας τη συνθήκη (α), η αντίστοιχη έγκυρη θέση θα ήταν (0,0). Άρα, x= 0, y= 0.
Θέση αριθμού 3:
Ο αριθμός 3 θα είναι στο (x-1, y+1) ή στο (-1, 1), το οποίο δεν είναι έγκυρη θέση. Χρησιμοποιώντας τη συνθήκη (α), η έγκυρη θέση της γραμμής θα ήταν n-1 ή 2. Άρα, ο αριθμός 3 θα είναι στο (2, 1). Για τον επόμενο αριθμό, x= 2, y= 1.
Θέση αριθμού 4:
Ο αριθμός 4 πρέπει να βρίσκεται στο (x-1, y+1) ή στο (1, 2) που είναι έγκυρη θέση. Αλλά αυτή η θέση περιέχει ήδη έναν αριθμό. Σύμφωνα με την προϋπόθεση (β), η έγκυρη θέση θα ήταν (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) που δεν είναι έγκυρη θέση. Σύμφωνα με την συνθήκη (γ), η έγκυρη θέση θα ήταν (0, n-2) ή (0, 1). Για τον επόμενο αριθμό x= 0, y= 1.
Θέση αριθμού 8:
Ο αριθμός 8 πρέπει να είναι στο (x-1, y+1) ή στο (-1, 2) που δεν είναι έγκυρη θέση. Χρησιμοποιώντας την συνθήκη (α), η έγκυρη θέση θα ήταν (2, 2). Για τον επόμενο αριθμό x= 2, y= 2.
Θέση αριθμού 9:
Ο αριθμός 9 πρέπει να είναι στο (x-1, y+1) ή στο (1, 3) που δεν είναι έγκυρη θέση. Χρησιμοποιώντας την συνθήκη (α), η έγκυρη θέση θα ήταν (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++ Κωδικός Magic Square
εισόδου:
/*
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 Κωδικός Magic Square
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).
