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

CMMDC recursiv a două numere naturale în C++

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

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

Dându-se două numere naturale a și b, vrem să aflăm CMMDC-ul (cel mai mare divizor comun) al celor două numere.

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

În acest articol vom aborda o soluție folosind o funcție recursivă.

Soluția 1

În primul rând, căutăm cazurile de bază:

  • Pentru a = 0 sau b = 0, cmmdc(a, 0) = cmmdc(0, b) = 0;
  • Pentru a = b, cmmdc(a, b) = cmmdc(a, a) = a;

De asemenea, observăm că cmmdc(a, b) = cmmdc(a - b, b) (considerând a > b).

Cu aceste observații, putem să construim ușor funcția de CMMDC recursiv:

#include <iostream>

using namespace std;

int cmmdcRec(int a, int b) {
    if(a == 0 || b == 0) {
        //Primul caz de bază: cmmdc(a, 0) = 0
        return 0;
    }
    if(a == b) {
        //Al doilea caz de bază: cmmdc(a, a) = a
        return a;
    }
    //Conform observației de mai sus,
    //cmmdc(a, b) = cmmdc(a - b, b), pt a > b
    //cmmdc(a, b) = cmmdc(a, b - a), pt a < b
    if(a > b) {
        return cmmdcRec(a - b, b);
    } else {
        return cmmdcRec(a, b - a);
    }
}

int main()
{
    int a, b;
    cin >> a >> b;
    cout << "cmmdc(" << a << ", " << b << ") = " << cmmdcRec(a, b);
    return 0;
}

Soluția 2 (algoritmul lui Euclid)

Prima soluție merge, însă are complexitate liniară (O(n)). Folosind algoritmul lui Euclid, putem să optimizăm soluția de mai devreme, astfel:

#include <iostream>

using namespace std;

int cmmdcRec(int a, int b) {
    if(b == 0) {
        return a;
    }
    return cmmdcRec(b, a % b);
}

int main()
{
    int a, b;
    cin >> a >> b;
    cout << "cmmdc(" << a << ", " << b << ") = " << cmmdcRec(a, b);
    return 0;
}

A doua soluție poate fi un pic mai greu de înțeles, însă este mai scurtă.

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

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

© 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