Sume pe linii și coloane la BAC: matrice în C++

Sumele pe linii și pe coloane se calculează adunând fiecare element în grupul potrivit. La BAC, diferența dintre cele două parcurgeri apare în indicele care rămâne fix și în momentul în care resetezi acumulatorul. O resetare pusă în bucla greșită poate transforma suma unei linii în suma unui singur element sau în suma întregii matrice.

Lecția despre tablouri bidimensionale se adresează profilului matematică-informatică; verifică programa specializării tale înainte să alegi exercițiile.

Vom găsi prima linie cu sumă maximă și prima coloană cu sumă maximă într-o matrice dreptunghiulară. Numărul liniilor poate fi diferit de numărul coloanelor. Exemplele sunt construite pentru a clarifica o schemă reutilizabilă în problemele de BAC la informatică.

Linia și coloana au limite diferite

Dacă matricea are două linii și trei coloane, indicele liniei ia două valori, iar indicele coloanei ia trei. În convenția de la zero, liniile sunt zero și unu, iar coloanele sunt zero, unu și doi.

Pentru o sumă pe linie, fixezi linia și parcurgi toate coloanele. Pentru o sumă pe coloană, fixezi coloana și parcurgi toate liniile. Inversarea celor două limite poate rămâne ascunsă când testezi numai matrice pătratice.

De aceea, un test dreptunghiular este esențial. El verifică faptul că ai folosit corect fiecare dimensiune, nu doar că buclele au o formă familiară.

Exemplu cu sume negative și pozitive

Considerăm matricea cu prima linie doi, minus unu, patru și a doua linie trei, cinci, minus doi. Suma primei linii este cinci, iar suma celei de-a doua este șase. Linia cu sumă maximă este a doua.

Coloană, de la unu	Element din prima linie	Element din a doua linie	Sumă
1	2	3	5
2	-1	5	4
3	4	-2	2

Coloana cu sumă maximă este prima, cu suma cinci. Linia și coloana câștigătoare nu trebuie să se întâlnească în elementul maxim al matricei. Criteriul privește suma grupului, nu un singur element.

Suma tuturor sumelor pe linii este unsprezece. Suma tuturor sumelor pe coloane este tot unsprezece. Egalitatea oferă o verificare independentă, fiindcă fiecare element trebuie adunat o dată în ambele moduri de grupare.

Unde resetezi suma unei linii

Când citești matricea linie cu linie, pornești suma curentă de la zero înainte de citirea elementelor unei linii. Aduni toate elementele acelei linii, apoi compari suma cu cel mai bun rezultat.

Dacă resetezi suma înaintea fiecărui element, vei păstra doar ultima valoare. Dacă o resetezi o singură dată, înaintea tuturor liniilor, vei calcula sume cumulative ale mai multor linii, nu sume separate.

Locul inițializării exprimă durata de viață a informației. Acumulatorul unei linii trebuie păstrat pe durata parcurgerii coloanelor acelei linii și reînceput când treci la următoarea.

Sumele coloanelor pot fi păstrate simultan

În citirea pe linii, valorile aceleiași coloane sosesc la distanță unele de altele. Pentru a nu memora întreaga matrice, putem păstra câte un acumulator pentru fiecare coloană.

Când citim un element de pe coloana curentă, îl adăugăm în suma acelei coloane. După toate liniile, fiecare acumulator conține suma completă a unei coloane. Numărul acestor acumulatori depinde de numărul coloanelor, nu de numărul total al celulelor.

Această alegere folosește ordinea în care sosesc datele. O linie se încheie complet înainte de următoarea, dar o coloană se completează treptat de-a lungul întregii citiri.

Program C++ complet

Dimensiunile sunt între unu și o sută, iar valorile întregi au cel mult un miliard în valoare absolută. Programul afișează pozițiile numerotate de la unu și sumele maxime corespunzătoare.

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    long long sumeColoane[100] = {};
    long long maximLinie = 0;
    int linie = 0;
    for (int i = 0; i < n; ++i) {
        long long suma = 0;
        for (int j = 0; j < m; ++j) {
            long long x;
            cin >> x;
            suma += x;
            sumeColoane[j] += x;
        }
        if (i == 0 || suma > maximLinie) {
            maximLinie = suma;
            linie = i;
        }
    }
    long long maximColoana = sumeColoane[0];
    int coloana = 0;
    for (int j = 1; j < m; ++j) {
        if (sumeColoane[j] > maximColoana) {
            maximColoana = sumeColoane[j];
            coloana = j;
        }
    }
    cout << linie + 1 << ' ' << maximLinie << '\n';
    cout << coloana + 1 << ' ' << maximColoana;
    return 0;
}

Condiția pentru prima linie asigură inițializarea maximului cu o sumă reală, chiar dacă este negativă. Valoarea zero din declarație nu rămâne un candidat artificial. Pentru coloane, inițializarea se face direct cu prima sumă calculată.

Comparațiile stricte păstrează prima linie și prima coloană în caz de egalitate. Dacă se cere ultima, regula trebuie adaptată. Nu modifica și convenția de numerotare atunci când schimbi regula de departajare.

De ce maximul elementelor nu rezolvă problema

O linie care conține un element foarte mare poate conține și valori negative care îi reduc suma. De exemplu, linia o sută, minus nouăzeci și nouă are suma unu. Linia doi, doi are suma patru și este mai bună după criteriul sumei.

Un algoritm care reține linia elementului maxim ar alege greșit prima linie. Trebuie să finalizezi suma întregii linii înainte să o compari cu celelalte. Criteriul global nu se reduce automat la cel mai mare element local.

Aceeași observație se aplică mediilor, produselor sau numărului elementelor care respectă o proprietate. Numește exact criteriul și construiește acumulatorul potrivit, conform principiului de învățare prin înțelegere.

Sume, medii și numărări

Pentru linii cu același număr pozitiv de coloane, ordinea sumelor este aceeași cu ordinea mediilor aritmetice. Împărțirea fiecărei sume la același număr nu schimbă comparația. Dacă problema cere doar linia cu media maximă, poți compara sumele.

Totuși, afișarea mediei cere o împărțire potrivită și respectarea preciziei cerute. O împărțire întreagă poate pierde partea fracționară. Nu folosi un rezultat trunchiat pentru o comparație care ar trebui să distingă valori apropiate.

Pentru numărul valorilor pare de pe fiecare linie, acumulatorul crește cu unu la fiecare element par. Pentru suma valorilor pare, adaugi elementul însuși. Condiția de selecție poate fi aceeași, dar sensul rezultatului este diferit.

Eficiența soluției

Fiecare celulă este citită și adunată în două sume, deci timpul este proporțional cu produsul dintre numărul liniilor și numărul coloanelor. Parcurgerea finală a coloanelor adaugă un termen mai mic, fără să schimbe ordinul dominant pentru matrice nevide.

Memoria auxiliară este proporțională cu numărul coloanelor, deoarece păstrăm doar sumele lor. Nu este necesar un tablou cu toate elementele matricei pentru aceste cerințe.

Dacă enunțul cere ulterior afișarea liniei câștigătoare, simpla reținere a sumei și a poziției nu păstrează și elementele ei. Trebuie adaptată strategia: memorare, păstrarea unui candidat complet sau o a doua citire, dacă este permisă. Analizează toate cerințele înainte să alegi memoria.

Exerciții cu răspunsuri

Două linii au sumele minus cinci și minus doi. Linia a doua are suma maximă. Zero nu este un răspuns valid dacă nicio linie nu are acea sumă.

Trei coloane au sumele șapte, șapte și trei. Programul prezentat alege prima coloană. Pentru ultima coloană cu sumă maximă, ar trebui aleasă a doua.

Matricea are o singură linie cu valorile patru, minus unu, doi. Suma liniei este cinci. Coloana cu sumă maximă este prima, deoarece fiecare coloană conține un singur element.

Matricea are o singură coloană cu valorile trei și opt. Linia cu sumă maximă este a doua, iar unica sumă pe coloană este unsprezece.

Întrebări frecvente

De ce testez o matrice dreptunghiulară?

Ea descoperă inversarea limitelor liniilor și coloanelor, o eroare care poate rămâne invizibilă pentru matrice pătratice. Alege dimensiuni diferite și valori ușor de adunat.

Trebuie să resetez și sumele coloanelor la fiecare linie?

Nu. Ele acumulează contribuții din toate liniile. Resetarea lor în interiorul parcurgerii ar păstra doar ultima linie și ar pierde informația anterioară.

Cum pot verifica organizarea buclelor?

Scrie lângă fiecare acumulator ce grup descrie și când acel grup este complet. Pentru corectarea unui program propriu, poți discuta această schemă cu un profesor de informatică.