CMMDC pentru un șir de numere la BAC: algoritm C++

CMMDC-ul unui șir de numere se calculează prin acumulare: păstrezi rezultatul pentru valorile citite până atunci și îl combini cu următoarea valoare. Pentru fiecare combinație poți folosi algoritmul lui Euclid. Nu trebuie să memorezi întregul șir, iar inițializarea corectă face ca aceeași regulă să funcționeze încă de la primul element.

Lecția explică trecerea de la două numere la o secvență, justificarea rezultatului și diferența dintre numere prime între ele în ansamblu și numere prime între ele două câte două. Aceste idei te ajută la problemele cu prelucrarea datelor citite succesiv, din familia celor întâlnite în subiectele de BAC la informatică.

Ce înseamnă CMMDC pentru mai multe numere

Pentru numere naturale strict pozitive, cel mai mare divizor comun este cel mai mare număr natural care divide fiecare valoare din șir. La secvența formată din 18, 30 și 42, numărul șase divide toate valorile. Niciun număr mai mare decât șase nu le divide simultan, deci rezultatul este șase.

Cuvântul „fiecare” este esențial. Un divizor al primelor două numere poate să nu dividă al treilea. De exemplu, pentru 12 și 18 rezultatul provizoriu este șase; dacă următoarea valoare este 25, rezultatul pentru întreaga secvență devine unu. Acumulatorul se poate micșora pe parcurs.

Nu adunăm rezultatele pentru perechi și nu calculăm o medie. Păstrăm o singură valoare care rezumă exact proprietatea comună a prefixului deja citit. Un prefix este porțiunea inițială a șirului, până la o anumită poziție inclusiv.

Schema algoritmului cu un acumulator

Moment	Ce citești	Ce păstrezi
Înaintea parcurgerii	Numărul de elemente	Acumulatorul inițial
La fiecare pas	Următorul element	CMMDC dintre acumulator și element
După ultimul pas	Nimic suplimentar	CMMDC al întregii secvențe

Pentru un șir nevid de valori strict pozitive ai două inițializări corecte. Poți citi separat primul număr și îl poți pune în acumulator. Apoi prelucrezi elementele rămase. Sau poți porni acumulatorul de la zero și poți prelucra uniform toate elementele, deoarece CMMDC dintre zero și un număr pozitiv este chiar acel număr.

A doua variantă nu înseamnă că rezultatul căutat este zero. Zero este aici o valoare de pornire convenabilă. După citirea primului element pozitiv, acumulatorul devine pozitiv. Dacă enunțul permite un șir vid ori numai zerouri, trebuie stabilită separat convenția cerută; nu presupune că un asemenea caz există în orice problemă.

Exemplu rezolvat pas cu pas

Considerăm șirul 84, 126, 210, 315. Pornim cu acumulatorul zero.

Valoare nouă	Acumulator înainte	CMMDC calculat	Acumulator după
84	0	CMMDC dintre 0 și 84	84
126	84	CMMDC dintre 84 și 126	42
210	42	CMMDC dintre 42 și 210	42
315	42	CMMDC dintre 42 și 315	21

Rezultatul final este 21. Verificarea directă confirmă că fiecare valoare este multiplu al lui 21. Observă că acumulatorul poate rămâne neschimbat, cum se întâmplă după citirea lui 210. Nu este necesar ca fiecare pas să producă un rezultat diferit.

În ultima combinație, împărțirea lui 315 la 42 are restul 21, iar împărțirea lui 42 la 21 are restul zero. Acesta este pasul local al algoritmului lui Euclid. Bucla exterioară gestionează elementele șirului, iar bucla din funcție gestionează resturile unei singure combinații.

Program C++ complet

Programul următor presupune că numărul de elemente este între unu și un milion, iar fiecare element este un număr natural strict pozitiv de cel mult un miliard. Citește numărul de elemente, apoi exact atâtea valori.

#include <iostream>
using namespace std;

int cmmdc(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int n, x, g = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        g = cmmdc(g, x);
    }
    cout << g;
    return 0;
}

Variabilele funcției sunt copii ale argumentelor. Modificarea lor nu schimbă direct variabilele apelantului. Rezultatul este transmis prin instrucțiunea de revenire și apoi atribuit acumulatorului. Dacă ai scrie doar apelul funcției, fără atribuirea rezultatului, acumulatorul nu s-ar actualiza.

Programul nu are nevoie de un vector. Reține doar câteva variabile întregi, indiferent de numărul elementelor. Memoria suplimentară este constantă. Pentru valori limitate superior de o valoare maximă, timpul este proporțional cu numărul elementelor înmulțit cu un factor logaritmic provenit din algoritmul lui Euclid; nu descrie soluția ca fiind pătratică doar fiindcă vezi două bucle în funcții diferite.

De ce este corectă acumularea

După prelucrarea primului element, acumulatorul este acel element, deci reprezintă CMMDC-ul prefixului de lungime unu. Presupunem apoi că, înainte de un pas, el reprezintă corect CMMDC-ul tuturor valorilor deja citite.

Un număr divide toate valorile vechi și valoarea nouă exact atunci când divide atât CMMDC-ul valorilor vechi, cât și valoarea nouă. Prin urmare, actualizarea păstrează exact divizorii comuni relevanți, iar cel mai mare dintre ei devine noul acumulator. Repetând raționamentul, obții rezultatul întregii secvențe după ultimul element.

Aceasta este o justificare prin invariant: propoziția despre semnificația acumulatorului rămâne adevărată după fiecare pas. Nu trebuie să memorezi formularea mecanic. Leag-o de tabelul exemplului, așa cum recomandă și explicația despre diferența dintre memorare și înțelegere.

Când rezultatul devine unu

Dacă acumulatorul a ajuns la unu, nicio valoare pozitivă citită ulterior nu îl mai poate micșora. CMMDC dintre unu și orice număr pozitiv este unu. Din perspectiva calculului, răspunsul final este deja cunoscut.

Totuși, oprirea citirii nu este întotdeauna potrivită. Dacă programul trebuie să prelucreze ulterior alte date din același flux, elementele rămase ale șirului trebuie consumate, altfel următoarea citire va interpreta o valoare greșită. Poți continua citirea fără să mai apelezi funcția, dar păstrarea variantei simple este adesea suficientă pentru cerințele date.

Prime între ele nu înseamnă mereu două câte două

Secvența 6, 10, 15 are CMMDC unu. Totuși, fiecare pereche are un divizor comun mai mare decât unu: prima pereche are doi, a doua pereche relevantă are trei, iar perechea 10 și 15 are cinci. Așadar, rezultatul global unu nu dovedește că numerele sunt prime între ele două câte două.

Dacă enunțul cere această proprietate pentru fiecare pereche, acumularea unui singur CMMDC nu rezolvă cerința. Trebuie analizate perechile sau utilizată o metodă adaptată limitelor problemei. Înainte să alegi algoritmul, subliniază expresiile „toate numerele”, „oricare două” și „există două”. Ele descriu condiții diferite.

Exerciții cu răspuns explicat

Exercițiul întâi. Determină evoluția acumulatorului pentru 24, 36, 60. Pornind de la zero, obții succesiv 24, 12, 12. Răspunsul final este 12, iar ultimul pas nu modifică valoarea.

Exercițiul al doilea. Pentru 14, 21, 25, la ce pas devine rezultatul unu? După primele două valori acumulatorul este șapte. După citirea lui 25 devine unu, deoarece șapte nu divide 25 și cele două numere nu au alt divizor comun pozitiv.

Exercițiul al treilea. Un șir conține un singur element, 37. Rezultatul trebuie să fie 37. Testul depistează inițializările greșite cu unu, care ar forța răspunsul unu pentru orice șir.

Exercițiul al patrulea. Schimbarea ordinii elementelor schimbă rezultatul final? Nu. Mulțimea divizorilor comuni este aceeași. Se pot schimba însă valorile intermediare și momentul în care acumulatorul ajunge la unu.

Întrebări frecvente

De ce nu inițializez acumulatorul cu unu?

Fiindcă unu combinat prin CMMDC cu orice număr pozitiv rămâne unu. Ai pierde posibilitatea de a găsi un divizor comun mai mare. Folosește primul element sau zero, în condițiile precizate.

Pot folosi aceeași idee pentru un fișier?

Da. Se schimbă sursa citirii, nu regula de actualizare. Respectă însă dacă fișierul oferă întâi numărul elementelor sau dacă trebuie citit până la sfârșit; cele două formate cer bucle diferite.

Ce verific înainte de a preda rezolvarea?

Testează un singur element, numere egale, un rezultat mai mare decât unu și un rezultat egal cu unu. Explică semnificația acumulatorului și verifică formatul de intrare. Dacă ai nevoie de feedback pe această justificare, poți lucra punctual cu un profesor de meditații la informatică.