Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Cel mai mare divizor comun (CMMDC) a două numere în C++

Se dau două numere naturale a și b și se cere să aflăm CMMDC-ul celor două numere (cel mai mare divizor comun).

Exemplu: pentru a = 14, b = 6, cmmdc(a, b) = 2.

În acest articol vorbim despre varianta normală (pentru clasa a IX-a). Pentru varianta recursivă (clasa a X-a), puteți intra pe această lecție.

Ce este CMMDC-ul a două numere?

CMMDC-ul, sau Cel Mai Mare Divizor Comun a două numere naturale a și b este un alt număr natural d cu proprietățile:

  • d | a și d | b (d divide a și d divide b);
  • d este cel mai mare număr posibil.

Cmmdc-ul a două numere poate avea diverse notații: cmmdc(a, b), gcd(a, b)greatest common divisor, sau chiar mai scurt, (a, b).

Determinarea celui mai mare divizor comun în C++

Există câteva metode de a determina cel mai mare divizor comun a două numere naturale nenule a și b. Vom prezenta două variante, ambele bazate pe același algoritm, algoritmul lui Euclid.

Metoda 1. Algoritmul lui Euclid cu scăderi

Algoritmul lui Euclid cu scăderi este o metodă mai puțin eficientă, însă mai ușor de înțeles. Acest algoritm se bazează pe principiul următor: dacă d | a și d | b, atunci d | a - b (unde a ≥ b) — dacă d divide ambele numere, atunci divide și diferența lor.

Iată algoritmul propriu zis:

  • cât timp numerele sunt diferite, se scade numărul mai mic din cel mai mare;
  • când numerele devin egale, atunci CMMDC-ul lor este chiar numărul lor.

Iată implementarea algoritmului în C++:

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim cele două numere
    int a, b;
    cin >> a >> b;
    while(a != b) {
        if(a > b) a = a - b;
        else b = b - a;
    }
    cout << "cmmdc-ul este " << a;
    return 0;
}

Metoda 2. Algoritmul lui Euclid clasic (cu împărțiri)

Algoritmul lui Euclid cu împărțiri este mai dificil de înțeles, însă este mai eficient (acesta este algoritmul recomandat pentru rezolvarea problemelor).

Pe scurt, observăm că în codul anterior facem scăderi repetate. Aceste scăderi se pot înlocui cu împărțiri, astfel că algoritmul este următorul:

  • cât timp b este diferit de 0, a primește b, iar b primește restul împărțirii lui a la b;
  • răspunsul în final se află în a.
#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim cele două numere
    int a, b;
    cin >> a >> b;
    while(b != 0) {
        int r = a % b; //Restul împărțirii lui a la b
        a = b;
        b = r;
    }
    cout << "cmmdc-ul este " << a;
    return 0;
}

Alte resurse sau bibliografie

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidăCum să calculezi instant 2 la puterea N în C++Numărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Maximul și minimul a trei valori în C++Citirea și afișarea matricelor în C++Suma elementelor unui vector recursiv în C++Inversarea unui vector în C++Cifra maximă și minimă a unui număr în C++Verifică dacă un caracter este literă în C++Verificare număr prim în C++ (Clasa a IX-a)Indicatorul lui Euler în C++Vectorii în C++: citire și afișareMaximul și minimul a două valori în C++Al N-lea termen Fibonacci în C++Numărul de cifre ale factorialului unui numărMatrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicCifra de control a unui numărStructuri repetitive (while, do while, for, etc)Șiruri de caractere în C++. Tot ce trebuie să știiRecursivitate în C++Calculul combinărilor de n luate câte k (nCk) în C++Transformarea unei litere mari în literă mică în C++Interschimbarea a două variabile în C++ (3 metode)Radicalul unui număr în C++ (rădăcina pătrată)Divide et Impera (metodă de programare C++)Distanța dintre două puncte în C++Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Prima cifră a unui număr în C++Verifică dacă un caracter este cifră în C++Tipuri de date în C++: numere întregi, reale, caractere și alteleComplexitatea unui algoritm (timp și spațiu) în C++Codul ASCII (tabel complet)Ce înseamnă endl în C++?Cum să citești și să afișezi în fișiere în C++Factorialul unui număr în C++Numărul permutărilor în C++ (formula permutărilor)Al N-lea termen dintr-o progresie geometricăVerifică dacă trei puncte sunt coliniare C++Cel mai frecvent element dintr-un șir în C++Instrucțiunea do while (structuri repetitive)Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortValoarea absolută (modulul) unui număr în C++Șirul lui Fibonacci în C++Cel mai puțin semnificativ bit în C++Cel mai mic număr cu suma cifrelor N în C++Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Generarea șirului Fibonacci generalizat în C++Transformarea unui număr din baza 10 în baza 2 în C++Ce înseamnă variabilă globală și locală în C++?Instrucțiunea continue (structuri repetitive)Suma divizorilor unui număr în C++Numărul de divizori primi ai unui număr în C++Maximul și minimul unui vector în C++Numere triunghiulare. Verificarea unui număr triunghiularVerifică dacă o literă este mică sau mare în C++CMMMC a două numere în C++ (cel mai mic multiplu comun)Cea mai lungă secvență de elemente crescătoare în C++Matrice pătratice în C++. Diagonala principală și secundarăAflă secolul unui an citit de la tastatură în C++Operații cu numere mari în C++ - Toate funcțiile explicateAlgoritm recursiv pentru căutare binară (clasa a X-a)Aria unui triunghi folosind coordonatele acestora în C++Suma numerelor naturale dintr-un interval dat în C++Interclasarea a doi vectori în C++Ce este o funcție void în C++?Funcții în C++. Ce sunt subprogrameleCMMDC recursiv a două numere naturale în C++Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorSuma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Aflarea sumei primelor N sume GaussNumărul de divizori al unui număr în C++Verifică dacă o literă este vocală în C++Suma 1 + 2 + 3 + ... + N în C++Oglinditul recursiv al unui număr în C++Afișarea elementelor unui vector recursiv în C++Tipul struct în C++. Ce sunt structurile de date neomogeneAfișarea divizorilor primi ai unui număr în C++Aria și circumferința unui cerc în C++Do while vs while în C++ - Care e diferența?Vectori de frecvență (de apariții) în C++Verifică dacă un număr este par sau impar fără modulo în C++Transformarea unei litere mici în literă mare în C++Mediana unui șir de valori în C++Numărul combinărilor în C++ (formula combinărilor)Pointer în C++. Variabile de tipul char * (char steluță)Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Cum să afișezi partea întreagă a unui număr real în C++Cel mai mare divizor comun (CMMDC) a două numere în C++Verificare dacă un număr este palindrom în C++Ciurul lui Eratostene în C++Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Instrucțiunea break (structuri repetitive)Instrucțiunea for (structuri repetitive)Câte numere naturale sunt într-un interval dat? (C++)Al N-lea termen dintr-o progresie aritmeticăCombinatorică în C++: permutări, aranjamente, combinări și alteleTransformarea unui număr din baza 2 în baza 10 în C++Numărul aranjamentelor în C++ (formula aranjamentelor)Ce este o variabilă unsigned în C++?Cel mai semnificativ bit în C++Verifică dacă un număr dat este o putere de 2 în C++Rădăcina cubică a unui număr în C++ (cube root)Verifică dacă un număr aparține șirului Fibonacci în C++Verificarea unui an bisect în C++Numărul de apariții al unui număr într-un vector în C++Comentarii în C++Materia pentru olimpiada de informatică - tot ce trebuie să știiVerificare dacă șir de caractere este palindrom în C++Bordarea unei matrice în C++Instrucțiunea de decizie în C++: if, else, switch, caseCifra maximă a unui număr recursiv în C++Citește un șir de caractere cu spații în C++Matrice în C++. Declararea și parcurgerea tablourilor bidimensionaleInversarea unui șir de caractere în C++Maximul și minimul a n valori în C++Vectorii în C++: declarare și parcurgereOglinditul unui număr în C++Instrucțiunea while (structuri repetitive)Căutare binară în C++Copiuțe: Cifrele unui numărNumărul minim de peroane pentru o gară în C++Funcții predefinite în C++ (matematice, șiruri de caractere)

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont