Constructia unui patrat magic impar

Problema:

55472vyo72vtj4t 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:

55472vyo72vtj4t 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.

55472vyo72vtj4t

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

4 55472vyo72vtj4t 3 55472vyo72vtj4t 8 55472vyo72vtj4t

9 55472vyo72vtj4t 5 55472vyo72vtj4t 1 55472vyo72vtj4t

2 55472vyo72vtj4t 7 55472vyo72vtj4t 6 55472vyo72vtj4t

55472vyo72vtj4t 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.

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

Metoda:

55472vyo72vtj4t 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 55472vyo72vtj4t 10 55472vyo72vtj4t 4 55472vyo72vtj4t 23 55472vyo72vtj4t 17 55472vyo72vtj4t

18 55472vyo72vtj4t 12 55472vyo72vtj4t 6 55472vyo72vtj4t 5 55472vyo72vtj4t 24 55472vyo72vtj4t

25 55472vyo72vtj4t 19 55472vyo72vtj4t 13 55472vyo72vtj4t 7 55472vyo72vtj4t 1 55472vyo72vtj4t

2 55472vyo72vtj4t 21 55472vyo72vtj4t 20 55472vyo72vtj4t 14 55472vyo72vtj4t 8 55472vyo72vtj4t

9 55472vyo72vtj4t 3 55472vyo72vtj4t 22 55472vyo72vtj4t 16 55472vyo72vtj4t 15 55472vyo72vtj4t

Despre program:

55472vyo72vtj4t Programul permite 2 tipuri de afisare a patratului magic:

1. 55472vyo72vtj4t Direct

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

2. 55472vyo72vtj4t 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');

}