#043 · Subiectul II · Programare

Să se calculeze şi să se afişeze cel mai mare divizor comun al elementelor vectorului

✓ Rezolvare explicatăDolj 2026 · nr. 18

Enunț

Se citesc de la tastatură un număr natural n şi cele n elemente ale unui vector X care memorează numere naturale nenule. Să se calculeze şi să se afişeze cel mai mare divizor comun al elementelor vectorului.

Exemple

Date de intrare	Date de ieșire	Explicații
`5` `42 8 36 24 6`	`2`	2 este singurul număr care îi împarte exact pe toți
`4` `43 20 15 7`	`1`	Nu au niciun divizor comun în afară de 1

Rezolvare

C++

#include <iostream>
using namespace std;

int cmmdc(int x, int y) {
    if (y == 0) return x;
    return cmmdc(y, x % y);
}

int main() {
    int n;
    cin >> n;

    int x[100];
    for (int i = 0; i < n; i++) cin >> x[i];

    int d = x[0];                       // pornim de la primul element
    for (int i = 1; i < n; i++)
        d = cmmdc(d, x[i]);             // il combinam pe rand cu urmatoarele

    cout << d;
    return 0;
}

Cum funcționează

Funcția cmmdc este exact cea de la c.m.m.d.c. a două numere — algoritmul lui Euclid, nemodificat. Tot ce se adaugă aici e modul în care o aplici pe mai mult de două numere.

Ideea: c.m.m.d.c.-ul se calculează în lanț. Nu există o formulă specială pentru un vector întreg; iei rezultatul parțial și îl combini cu următorul element:

d = 42
d = cmmdc(42, 8)  = 2
d = cmmdc(2, 36)  = 2
d = cmmdc(2, 24)  = 2
d = cmmdc(2, 6)   = 2

Funcționează pentru că operația este asociativă: cmmdc(a, b, c) este același lucru cu cmmdc(cmmdc(a, b), c). Aceeași structură se folosește și la c.m.m.m.c., și la suma sau maximul unui vector — un rezultat parțial care se actualizează la fiecare pas.

Pornirea se face de la x[0], nu de la 0 sau 1, iar bucla începe de la i = 1, ca să nu combini primul element cu el însuși. Când elementele nu au divizori comuni, lanțul ajunge la 1 și rămâne acolo — exact al doilea exemplu.

Greșeli frecvente

Inițializarea cu d = 0 sau d = 1 — cu d = 1 rezultatul e mereu 1, pentru că cmmdc(1, orice) este 1. Se pornește întotdeauna de la primul element.
Bucla de la i = 0 — calculează inutil cmmdc(x[0], x[0]). Nu dă rezultat greșit, dar arată că n-ai înțeles pornirea.
Încercarea de a descompune în factori primi — matematic corect, dar mult mai lung de scris și mai ușor de greșit decât Euclid aplicat în lanț.
Oprirea la primul d == 1 — e o optimizare validă, dar nu o scrie dacă nu ești sigur; fără ea programul e oricum destul de rapid.

Exersează mai departe

Probleme cu aceeași tehnică

#064ProgramareSă se afişeze numărul valorilor prime din vector #068ProgramareSă se afişeze numărul elementelor care sunt numere palindrom #069ProgramareSă se afişeze numerele perfecte din vector #174ProgramareCel mai mare divizor comun al celor n numere citite #275ProgramarePerechi de vecini cu aceeași sumă a cifrelor #276ProgramarePerechi de vecini în care primul e mai mic decât suma cifrelor celui de-al doilea