Salut! Imi poate scrie cineva un cod cum as putea afla submatricea de suma maxima dintr-o matrice în C++? Am nevoie de rezolvarea cu sume parțiale. Dacă puteți să oferiți și câteva explicații, nu înțeleg deloc cum să fac problema asta. Mersi!
Răspunsuri la întrebare
Răspuns:
#include <iostream>
using namespace std;
int main()
{
int matrice[6][6] = {
{1, 2, 54, 9, 0, 23},
{85, 3, 2, 19, 19, 4},
{12, 13, 14, 15, 16, 17},
{9, 8, 1, 2, 7, 7},
{1, 2, 3, 4, 5, 6},
{8, 8, 4, 3, 2, 2}
};
int rezultat = 0, suma = 0, n = 2;
for(int a=0; a<6; a++)
{
for(int b=0; b<6; b++)
{
if((a + n < 6) && (b + n < 6))
{
for(int c=a; c<a+n; c++)
{
for(int d=b; d<b+n; d++)
{
suma += matrice[c][d];
}
}
if(rezultat < suma)
{
rezultat = suma;
}
}
suma = 0;
}
}
cout << "Rezultat: " << rezultat << endl;
return(0);
}
Explicație:
Salut. Asta ar fi o metoda nu e cea mai eficienta pentru ca folosesc 4 bucle for. Dar am ales-o pe asta pentru ca e usor de explicat.
'matrice[6][6]' = matricea principala.
'rezultat' = variabila asta pastreaza cea mai mare suma gasita in submatrice
'suma' = aduna valorile din fiecare submatrice (la finalul buclei cu var 'c' se reseteaza)
'n' = dimensiunea submatricei
primele 2 bucle for care folosesc variabila 'a' si 'b' le folosesc ca sa iterez toate valorile din matricea principala.
ultimele 2 bucle for care folosesc variabila 'c' si 'd' sunt o 'matrita' a submatricei. In ultimele bucle adun valorile din submatricea respecita si verific daca sunt mai mari decat cea mai mare suma pe care am gasit-o pana in momentul acela.
Poti incerca sa gasesti o rezolvare mai eficienta :).
Bafta!