Kuidas lahendada 3×3 maagilise ruudu mõistatust C- ja C-tähes Python

Mis on maagiline ruut?

Maagiline ruut on ruutmaatriks, millel on eriline numbrite paigutus. Väärtused on paigutatud nii, et summa igas reas, igas veerus ja mõlemas peadiagonaalis jääb samaks. Maagilised ruudud on lihtsad loogikamõistatused, mida kasutatakse meelelahutusmatemaatikas.

Maagiliste ruutude näide:

Ülaltoodud diagramm näitab kolmanda järgu maagilist ruutu. Iga diagonaali, rea ja veeru summa on võrdne 15-ga. Järgmises osas selgitatakse, kuidas see konstantne summa saadakse.

Kuidas maagilised ruudud töötavad

Maagiline ruut järguga n on n korda n maatriks, mis sisaldab n² positiivset täisarvu. Ridade või veergude arvu nimetatakse maatriksi järguks.

Tüüpilised maagilised ruudumõistatused on paaritu järguga ja kasutavad täisarve 1-st n²-ni. Kuna iga rea, veeru ja diagonaali summa peab olema sama, nimetatakse seda väärtust maagiliseks summaks või maagiliseks konstandiks. Konstant sõltub ainult n-st. Maagilise summa valem n-järgulises järjekorras on:

Vaatleme kolmanda järgu maagilist ruutu. Maagiline summa on siis:

See valem selgitab aritmeetikat, kuid pusle pika kultuurilise ajaloo tõttu on see ka meeldejääv.

Miks neid maagiaks nimetatakse?

Muistsed matemaatikud olid lummatud huvitavatest numbrikombinatsioonidest ja maagiline ruut oli üks neist. Varaseimad tõendid pärinevad Hiinast umbes aastast 190 eKr.

Uuringud näitavad tõendeid võluruutude mõistatuste kohta iidses Jaapanis, Indias ja Araabias. Legendid seostasid neid paigutusi võlumaailmaga ja see nimi jäigi püsima. Lisaks folkloorile on matemaatikud määratlenud ka formaalseid kategooriaid, mis eristavad ühte ruutu teisest.

Maagilise ruudu tüübid

Matemaatikas on mitu maagiliste ruutude varianti:

• Tavaline maagiline ruut: Sisaldab esimesi n² naturaalarvu.
• Poolmaagiline ruut: Maagilise konstandi summeerimiseks kuluvad ainult read ja veerud.
• Lihtne maagiline ruut: Read, veerud ja mõlemad peamised diagonaalid moodustavad maagilise konstandi.
• Kõige täiuslikum maagiline ruut: Tavaline maagiline ruut kahe lisaomadusega. Iga 2 x 2 maatriksi osaruut annab kokku 2(n²+1) ja iga arvupaar, mis asub üksteisest n/2 lahtri kaugusel, annab kokku n²+1.

Lisakategooriaid on rohkem, mis põhinevad täiendavatel omadustel. Kui selles õpetuses kasutatakse terminit „maagiline ruut” ilma tingimusteta, viitab see paaritu järgu, normaalsele, lihtsale maagilisele ruudule.

Maagilise ruudu genereerimise algoritm

Klassikaline algoritm paaritu järgu maagilise ruudu genereerimiseks, mida nimetatakse Siiami meetodiks, on järgmine:

• Esimene arv (1) salvestatakse positsioonile (n/2, n-1), kus esimene koordinaat on reaindeks ja teine ​​on veeruindeks. Hilisemate sammude jaoks nimetage seda positsiooni (x, y).
• Järgmine arv asetatakse punkti (x-1, y+1). Kui see positsioon on vale, rakendage järgmisi reegleid:
  1. Kui reaindeks on -1, murra see väärtuseks n-1. Kui veeruindeks on n, murra see väärtuseks 0.
  2. Kui arvutatud positsioonis on juba number, suurendage rea arvu 1 võrra ja vähendage veeru arvu 2 võrra.
  3. Kui rida on -1 ja veerg on n samal ajal, on uus positsioon (0, n-2).

Märge: See algoritm genereerib ainult paaritu järgu kehtivaid maagilisi ruute. Tulemuseks on tavaline maagiline ruut, mis sisaldab esimesi n² naturaalarvu. Sama n jaoks võib olla rohkem kui üks kehtiv lahend.

Reeglid saavad selgemaks väikese näite abil, kus on 3. järk, kus kasutatakse numbreid 1 kuni 9.

Kuidas see 3x3 ruudul töötab

Rakenduse algoritm ülaltoodud sammud on järgmised:

Step 1) Esimene arv (1) asetatakse kohale (3/2, 3-1) või (1, 2). Hilisemate sammude jaoks määrake x = 1 ja y = 2.

Step 2) Ülejäänud numbrite positsioonid arvutatakse järgmiselt.

Numbri 2 asukoht:

Järgmine arv peaks minema (x-1, y+1) või (0, 3) juurde, mis ei ole kehtiv positsioon. Reegli (a) kohaselt murdub veerg nullini, saades (0, 0). Määrake x = 0, y = 0.

Numbri 3 asukoht:

Arv 3 peaks asuma punktis (x-1, y+1) või (-1, 1), mis pole kehtiv positsioon. Reegli (a) kohaselt murdub rida punktini n-1 (mis on 2). Seega läheb number 3 punkti (2, 1). Määrake x = 2, y = 1.

Numbri 4 asukoht:

Arv 4 peaks asuma punktis (x-1, y+1) või (1, 2), mis on kehtiv, aga sisaldab juba arvu 1. Reegli (b) kohaselt on uus positsioon (1+1, 2-2) või (2, 0). Määrake x = 2, y = 0.

Numbri 5 asukoht:

Arv 5 peaks asuma punktis (x-1, y+1) või (1, 1), mis on kehtiv tühi positsioon. Määrake x = 1, y = 1.

Numbri 6 asukoht:

Arv 6 peaks asuma punktis (x-1, y+1) või (0, 2), mis on kehtiv tühi positsioon. Määrake x = 0, y = 2.

Numbri 7 asukoht:

Number 7 peaks asuma punktis (x-1, y+1) või (-1, 3), mis on vale. Reegli (c) kohaselt on uus positsioon (0, n-2) või (0, 1). Määrake x = 0, y = 1.

Numbri 8 asukoht:

Arv 8 peaks asuma punktis (x-1, y+1) või (-1, 2), mis on vale. Reegli (a) kohaselt murdub rida punktini 2, saades tulemuseks (2, 2). Määrake x = 2, y = 2.

Numbri 9 asukoht:

Number 9 peaks asuma punktis (x-1, y+1) või (1, 3), mis on vale. Reegli (a) kohaselt murdub veerg nullini, saades tulemuseks (1, 0).

Iga täidetud lahtriga tõlgitakse sama loogika otse pseudokoodiks.

Maagilise ruudu pseudokood

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

Pseudokood seostub otse kompileeritud ja interpreteeritud keeltega, nagu on näidatud järgmises pildis. C++ ja Python.

C++ Code Maagilise ruudu jaoks

sisend:

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

Näite väljund:

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 Allolev versioon kasutab identseid rea- ja veerureegleid.

Python Code Maagilise ruudu jaoks

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)

Näite väljund:

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

Mõlemad rakendused toimivad identselt, mistõttu on nende maksumust lihtne võrrelda.

Keerukuse analüüs

• Ruumi keerukus: Maagiline ruut on salvestatud n x n massiivis, seega on ruumi keerukus O(n²).
• Aja keerukus: Generaator kasutab kahte pesastatud tsüklit. Välimine tsükkel töötab n korda ja sisemine tsükkel töötab samuti n korda, seega on üldine ajaline keerukus O(n²).

KKK