vineri, 20 ianuarie 2017

Construcţia unui pătrat magic impar

Tags

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
3
8
9
5
1
2
7
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
10
4
23
17
18
12
6
5
24
25
19
13
7
1
2
21
20
14
8
9
3
22
16
15

Despre program:

            Programul permite 2 tipuri de afişare a pătratului magic:

1.       Direct
-         programul afişează pătratul chiar dacă nu o să încapă pe ecran
2.       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 <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');
}


loading...