Constructia unui patrat magic impar

Problema:

59614tiz99lit5k Sa se construiasca un patrat magic de dimensiune n ( cu n impar), adica o matrice cu n linii si n coloane avand ca elemente numerele naturale 1, 2, ..., n^2 astfel incat sumele elementelor pe linii, pe coloane si pe cele doua diagonale sa fie identice.

Introducere:

59614tiz99lit5k Un patrat magic consta dintr-un tablou de numere aranjate in forma unui patrat, astfel incat sumele elementelor din fiecare linie, coloana si din cele doua diagonale sa fie identice; valoarea sumei se numeste numar magic. Un patrat magic este de ordin n daca pe o latura a sa sunt asezate n numere, iar in componenta sa intra numerele 1, 2, 3…, n2; atunci numarul magic poate fi calculat cu formula: numar magic = n(n2+1)/2.

59614tiz99lit5k

59614tiz99lit5k Exista un singur patrat magic de ordinul 3 (cu toate ca prin rotatii si simetrii pot fi obtinute 8 astfel de patrate):

4 59614tiz99lit5k 3 59614tiz99lit5k 8 59614tiz99lit5k

9 59614tiz99lit5k 5 59614tiz99lit5k 1 59614tiz99lit5k

2 59614tiz99lit5k 7 59614tiz99lit5k 6 59614tiz99lit5k

59614tiz99lit5k Patratele magice de ordin 4 sunt in numar de 880 (7040 daca sunt considerate si rotatiile si simetriile), iar numarul patratelor magice de ordin 5 este de circa 13.000.000.

59614tiz99lit5k Sunt cunoscute mai multe metode de obtinere a patratelor magice, ele diferind pentru patratele de ordin par, respectiv impar.

Metoda:

59614tiz99lit5k O metoda foarte simpla consta in urmatoarele actiuni:

• Se plaseaza 1 in centrul ultimei coloane;

• Se merge in linie oblica, dreapta-jos, cu numarul urmator; daca se iese din patrat prin partea dreapta, se merge in partea opusa, in stanga liniei unde trebuia depus numarul, iar daca se iese prin partea de jos a patratului, se merge in partea de sus a coloanei unde trebuia depus numarul;

• Dupa ce se completeaza un grup de n numere, se merge cu o casuta spre stanga, pe aceeasi linie, pentru a se repeta apoi pasul 2 si a genera urmatorul grup de n numere.

Se obtine in final urmatorul patrat magic:

11 59614tiz99lit5k 10 59614tiz99lit5k 4 59614tiz99lit5k 23 59614tiz99lit5k 17 59614tiz99lit5k

18 59614tiz99lit5k 12 59614tiz99lit5k 6 59614tiz99lit5k 5 59614tiz99lit5k 24 59614tiz99lit5k

25 59614tiz99lit5k 19 59614tiz99lit5k 13 59614tiz99lit5k 7 59614tiz99lit5k 1 59614tiz99lit5k

2 59614tiz99lit5k 21 59614tiz99lit5k 20 59614tiz99lit5k 14 59614tiz99lit5k 8 59614tiz99lit5k

9 59614tiz99lit5k 3 59614tiz99lit5k 22 59614tiz99lit5k 16 59614tiz99lit5k 15 59614tiz99lit5k

Despre program:

59614tiz99lit5k Programul permite 2 tipuri de afisare a patratului magic:

1. 59614tiz99lit5k Direct

• programul afiseaza patratul chiar daca nu o sa incapa pe ecran

2. 59614tiz99lit5k Pas cu pas

• dupa fiecare numar afisat trebuie apasata o tasta

• se vor afisa numai patratele cu n<15. Pentru n>15 afisarea se va face numai in mod 'Direct'

Sursa programului:

#include <stdio.h>#include <conio.h>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');

}