Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Eficienta - Matrice patrat magic.  (Citit de 5842 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Insomniacc
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« : Octombrie 31, 2015, 18:17:11 »

Salut ! Asta este primul meu post pe forum si as vrea sa va cer ajutorul la o problema care imi cere sa verific daca o matrice formeaza un patrat magic.

! Un patrat magic este o matrice care are suma fiecarei linii egala cu suma fiecarei coloane egala cu suma diagonalei principale si secundare.

Ex: 1 1 1
      1 1 1
      1 1 1

Am realizat un program care aparent functioneaza dar nu e foarte eficient si as vrea sa stiu ce ar trebui sa fac pentru a fi mai cat mai eficient posibil.
Codul este urmatorul :

Cod:
//Determinam daca o matrice este patrat magic.

#include <iostream>
using namespace std;
int main(){
    int a[30][30],sumaLD[30],sumaCol[30],n;
    int x=2; //Initializam cu 2 indicele vectorului ce retine suma liniilor si a diagonalelor
            //pentru ca indicii 0 si 1 vor memora suma de pe diagonala principala si cea de pe diagonala secundara.

    int y=0; //Indicele vectorului ce retine suma coloanelor.
    bool ok = true;

    cout << "Dati numarul de linii si coloane "; cin >> n;

    for(int i=0;i<=n+2;++i) //Initializam toate elementele vectorului sumei de linii si diagonale cu 0.
        sumaLD[i]=0;

    for(int i=0;i<=n;++i) //Initializam toate elementele vectorului sumei de coloane cu 0.
        sumaCol[i]=0;

    for(int i=1;i<=n;++i){ //Citim elementele matricei si in acelasi timp calculam suma de pe linii si diagonale.
        for(int j=1;j<=n;++j){
            cin >> a[i][j];
            sumaLD[x] += a[i][j];
            if(i == j)
                sumaLD[0] += a[i][j]; //Suma de pe diagonala principala.
            if(i+j == n+1)
                sumaLD[1] += a[i][j]; //Suma de pe diagonala secundara.
        }

        ++x; //Incrementam cu o unitate indicele sumei liniilor pentru ca se va trece la o noua linie.
    }

    for(int j=1;j<=n;++j){ //Calculam suma de pe coloane.
        for(int i=1;i<=n;++i)
            sumaCol[y] += a[i][j];

        ++y; //Incremetnam indicele sumei coloanelor pentru ca se va trece la o noua coloana.
    }

    /*

    In continuare verificam daca vectorii creeati sumaLD(suma liniilor si a diagonalelor) si sumaCol sunt egali.
    In caz afirmativ este necesar sa verificam daca primul element din sumaLD este egal cu primul element din sumaCol
    In caz afirmativ rezulta ca toate sumele sunt egale,iar matricea formeaza un patrat magic.

    */

    for (int i=0;i<x-1;++i)
        if(sumaLD[i] != sumaLD[i+1])
            ok = false;



    for (int i=0;i<y-1;++i)
        if(sumaCol[i] != sumaCol[i+1])
            ok = false;


    if(ok){
        if(sumaLD[0] == sumaCol[0])
            cout << "Este patrat magic.";
        else
            cout << "Nu este patrat magic.;";
    } else
        cout << "Nu este patrat magic.";

    return 0;
}

Ideea este urmatoarea : creez un vector care retine sumele de pe linii si diagonale, apoi alt vector care va retine sumele de pe coloane.Verific daca toate elementele vectorilor sunt egale intre ele.
Daca sunt egale, e necesar sa verific daca un element din primul vector este egal cu alt element din al doilea vector, in caz afirmativ , este un patrat magic.
Memorat
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 341
Deconectat Deconectat

Mesaje: 804



Vezi Profilul
« Răspunde #1 : Noiembrie 02, 2015, 04:48:57 »

Mai intai iti spun ca ai o greseala in cod. Folosesti SumaLD[1] si pentru linia 1 si pentru diagonala secundara.

Apoi, din punct de vedere al complexitatii timpului ai deja cea mai eficienta solutie: O(N^2), si constanta este relativ mica. La memorie poti sa optimizezi de la O(N^2) la O(N) observand ca nu trebuie sa mentii matricea a. Fiecare element din matrice il folosesti imediat si dupa nu te mai uiti la el.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines