Problema Patrat Magic

[•miculprogramator]

Am urmatoarea cerinta: "Sa se scrie un prog. care verifica -printr-o singura parcurgere- daca o matrice cu n(n impar) linii si n coloane este patrat magic.

Am ajuns la urmatoarea concluzie:

-sa zicem ca n=5
np=n*n adica 25

if (n%2!=0) k=(int)np%2+1;
else k=(int)np%2;
si asa am aflat nr care trebuie pus in mijloc, in acest caz 13.
suma care trebuie sa fie in patrat o aflu cu 5*13=65 adica s=n*k.

Acum mai ramane problema cu parcurgerea...Am cautat si am gasit patratul:

11   24   7   20   3
4   12   25   8   16
17   5   13   21   9
10   18   1   14   22
23   6   19   2   15

Am observat ca elementele de pe diagonala principala sunt consecutive, iar cele de pe diagonala secunadra sunt +n.Adica:

3+5=8
8+5=13
13+5=18
18+5=23

Cum fac treaba cu o singura parcurgere?Mentionez ca nu am invatat inca functii...

[•alexandru92]

poate te ajuta urmatoarea chestie:

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(n^2+1)/2.

[•miculprogramator]

Exact acelasi lucru am facut si eu. Am probleme cu parcurgerea, nu cu aflarea nr magic (adica cel din centru).

[•gabor_oliviu1991]

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

[•miculprogramator]

Asta am gasit si eu pe net, pe mine ma interseaza cum verific, nu cum construiesc un patrat magic.

[•alexandru92]

Intr-un vector sumi -retii sumele de pe fiecare linie si de pe cele 2 diagonale, intr-un vector sumj retii sumele de toate coloanele , apoi verifici daca fiecare element din cei 2 vectori este egal  cu  n(n^2+1)/2 :d.
Vectorii ii  construiesti chiar de la citire => nu mai ai nevoie de matrice
daca te chinui putin poti sa scapi de vectorul sumi

[•miculprogramator]

Buna idee! O sa incerc si revin cu post.

[•miculprogramator]

Ce nu e bine?

Cod:

#include <iostream.h>
#include <conio.h>
main()
{
clrscr();
int a[5][5]={11,24,7,20,3,
			 4,12,25,8,16,
			 17,5,13,21,9,
			 10,18,1,14,22,
			 13,6,19,2,15};
int n=5,i,j,g=1,sumi[5],sumj[5],sp,ss;
for (i=0;i<n;i++)
	for (j=0;j<n;j++)
		{
		 sumi[i]+=a[i][j];
		 sumj[j]=a[i][j];
		 sp+=a[i][i];
		 ss=a[i][n-1-i];
		}
for (i=0;i<n;i++)
	for (j=0;j<n;j++)
		if ( (sumi[i]!=sumj[j]) && (sumj[j]!=ss) &&(ss!=sp) ) g=0;
if (g==1) cout<<"da!";
	else cout<<"nu!";
getch();
}

 

[•toni2007]

Pai, in primul rand tu adaugi la sp si ss de n ori aceeasi chestie. Tre sa mai compari ss cu sumi[1] si sumi[1] cu sumj[1]. De asemenea, la if-uri trebuie || in loc de &&.

Cod:

#include <iostream.h>
#include <conio.h>
main()
{
clrscr();
int a[5][5]={11,24,7,20,3,
			 4,12,25,8,16,
			 17,5,13,21,9,
			 10,18,1,14,22,
			 13,6,19,2,15};
int n=5,i,j,g=1,sumi[5],sumj[5],sp,ss;
for (i=0;i<n;i++)
	for (j=0;j<n;j++)
		{
		 sumi[i]+=a[i][j];
		 sumj[j]=a[i][j];
                 }
   for (i = 0; i < n; ++ i) {
		 sp+=a[i][i];
		 ss=a[i][n-1-i];
		}
for (i=0;i<n;i++)
	for (j=0;j<n;j++)
		if ( (sumi[i]!=sumj[j]) || (sumj[j]!=ss) || (ss!=sp) ) g=0;
if (sumi[1] != sumj[1] || sumi[1] != ss) g = 0;
if (g==1) cout<<"da!";
	else cout<<"nu!";
getch();
}

[•Florian]

Iar sumi[] nu e initializata [ faci direct "sumi[ i ] += a[ i ] [ j ]; " ]

[•miculprogramator]

Am modificat si asta si 13 acela din colt (care de fapt era 23) si afiseaza nu!

[•alexandru92]

Uite un cod care merge :d

Cod:

/*si ,si2 retin suma de pe linii
sumj[]-retin suma de pe coloane
diags,diagp-retin suma de pe diagonale*/
#include<stdio.h>
#define true 1
#define false 0
int n,i,j,x,si,si2,sumj[1000],diags,diagp;
int main()
  {short ok=true;
   freopen("patratmagic.in","rt",stdin);
   freopen("patratmagic.out","wt",stdout);
   scanf("%d",&n);
   for(i=1;i<=n;++i)
      {
       si=0;
       for(j=1;j<=n;++j)
	  {
	   scanf("%d",&x);
	   si+=x;
	   sumj[j]+=x;
	   if(i==j) diagp+=x;
	   if(i+j==n+1) diags+=x;
	  }
	if(i>1&&si!=si2) ok=false;
	si2=si;
       }
   if(!ok||diags!=diagp||diags!=si||diagp!=si) {printf("NU"); return 0;}
   for(i=1;i<=n&&ok;++i)
      if(sumj[i]!=si) ok=0;
   if(ok) printf("DA");
   else printf("NU");
   return 0;
  }

Daca nu-l intelegi pm :d
La tine din cate am vazut:

for (i = 1; i <= n; ++ i)

ar trebuii sa inceapa de la 0 ...n-1

ss=a[ i ][ n-1-i ];

ss+=a[ i ][ n-1-i ];

[•toni2007]

Mdea, asa e, greseala mea.

[•miculprogramator]

Salut! Am rezolvat problema altfel:

Cod:

clrscr();
int a[5][5]={11,24,7,20,3,
			 4,12,25,8,16,
			 17,5,13,21,9,
			 10,18,1,14,22,
			 23,6,19,2,15};
int n=5,i,j,gl=1,gc=1,x,sumi[]={0,0,0,0,0},sumj[]={0,0,0,0,0},sumt=0,k;
for (i=0;i<n;i++)
	for (k=0;k<n;k++)
		{
		 sumi[i]+=a[i][k];
		 sumj[i]+=a[k][i];
		}
for (i=0;i<n;i++)
sumt+=sumi[i];



x=int(n/2);
cout<<"x="<<x<<endl;
cout<<"mijlocul este:"<<a[x][x]<<endl;
cout<<"sumt="<<sumt<<endl ;
if (sumt==n*a[x][x]*n) cout<<"suma totala corecta"<<endl;
	else cout<<"suma totala gresita"<<endl;

if ( a[x][x]==(int)((n*n)/2)+1 )
								cout<<"mijlocul este corect"<<endl;
	else cout<<"mijlocul nu este corect"<<endl;


 for (i=0;i<n;i++)
	{
	cout<<sumi[i]<<" ";
	if (sumi[i]!=n*a[x][x]) gl=0;
	}
 if (gl)  cout<<"indeplineste a2a conditie";
	else cout<<"nu a2a conditie";
	cout<<endl;
 for (i=0;i<n;i++)
	{
	cout<<sumj[i]<<" ";
	if (sumj[i]!=n*a[x][x]) gc=0;
	}
 if (gc) cout<<"indeplineste a3a conditie";
		  else cout<<"nu a 3a conditie";
getch();
}