Constructia Unui Patrat Magic Impar

Construcţia unui pătrat magic impar Problema: Să se construiască un pătrat magic de dimensiune n ( cu n impar), adică o matrice cu n linii si n coloane având ca elemente numerele naturale 1, 2, ..., n^2 astfel încât sumele elementelor pe linii, pe coloane si pe cele doua diagonale sa fie identice.

Introducere: Un pătrat magic constă dintr-un tablou de numere aranjate în forma unui pătrat, astfel încât sumele elementelor din fiecare linie, coloană şi din cele două diagonale să fie identice; valoarea sumei se numeşte număr magic. Un pătrat magic este de ordin n dacă pe o latură a sa sunt aşezate n numere, iar în componenţa sa intră numerele 1, 2, 3…, n2; atunci numărul magic poate fi calculat cu formula: număr magic = n(n2+1)/2. Există un singur pătrat magic de ordinul 3 (cu toate că prin rotaţii şi simetrii pot fi obţinute 8 astfel de pătrate): 4 9 2

3 5 7

8 1 6

Pătratele magice de ordin 4 sunt în număr de 880 (7040 dacă sunt considerate şi rotaţiile şi simetriile), iar numărul pătratelor magice de ordin 5 este de circa 13.000.000. Sunt cunoscute mai multe metode de obţinere a pătratelor magice, ele diferind pentru pătratele de ordin par, respectiv impar.

Metoda:  



O metodă foarte simplă constă în următoarele acţiuni: Se plasează 1 în centrul ultimei coloane; Se merge în linie oblică, dreapta-jos, cu numărul următor; dacă se iese din pătrat prin partea dreaptă, se merge în partea opusă, în stânga liniei unde trebuia depus numărul, iar dacă se iese prin partea de jos a pătratului, se merge în partea de sus a coloanei unde trebuia depus numărul; După ce se completează un grup de n numere, se merge cu o căsuţă spre stânga, pe aceeaşi linie, pentru a se repeta apoi pasul 2 şi a genera următorul grup de n numere. Se obţine în final următorul pătrat magic: 11 18 25 2 9

10 12 19 21 3

4 6 13 20 22

23 5 7 14 16

17 24 1 8 15

Despre program:

1. 2.

Programul permite 2 tipuri de afişare a pătratului magic: Direct − programul afişează pătratul chiar dacă nu o să încapă pe ecran Pas cu pas

− −

după fiecare număr afişat trebuie apăsată o tastă se vor afişa numai pătratele cu n<15. Pentru n>15 afişarea se va face numai în mod ‘Direct’

Sursa programului: #include <stdio.h>#include unsigned char m[200][200];int n; void af(){ for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) printf("%3d%c",m[i][j],j==n?'\n':' ');}void mod_1(){ int i=n/2+1,j=1; for (int nr=1;nr<=n*n;nr++) { if (nr%n==1) {if (!(--j)) j=n;} else {if (++i==n+1) i=1; if (++j==n+1) j=1; } m[i][j]=(unsigned char)nr; } af(); } void mod_2() { if (n>17) { printf("Nu pot afisa pas cu pas patrate cu n>17.Il afisez normal...\n"); mod_1(); return; } int poz=wherey()-1; int i=n/2+1,j=1; for (int nr=1;nr<=n*n;nr++) { if (nr%n==1) {if (!(--j)) j=n;} else {if (++i==n+1) i=1; if (++j==n+1) j=1; } gotoxy(j*4,poz+i); printf("%3d ",nr); getch(); } gotoxy(1,poz+n); } void main(void) { char c; do{ clrscr(); printf("N=");scanf("%d",&n);fflush(stdin); if (n%2) { puts("1. Direct 2. Pas cu pas"); printf("Alegeti modul de afisare al patratului (1/2):"); unsigned char k; scanf("%u",&k); if (k==1) mod_1(); else mod_2(); printf("\nAcesta este patratul magic de ordin %d.",n); printf("\nNumarul magic este %d.",n*(n*n+1)/2); } else printf("Ati introdus un numar par..."); printf("\nContinuati? (d/n) ");c=getch();

}while (c!='n'); }