Algoritmi Cmmdc

[Kid Koder]

"Se dau doua numere a si b. Sa se afle cmmdc al celor doua numere."
 
Exista doua metode de rezolvare:
 
1. Scaderi repetate:

/* Author : Kid Koder
   Create Date: 23-Jul-14, 14:49
   Language: C++
   Euclid - CMMDC
*/

#include <fstream>


using namespace std;


ifstream fin("date.in");
ofstream fout("date.out");


int a, b;


int main() {
    fin >> a >> b;


    while(a != b) {
        if(a > b) {
            a -= b;
        }
        else {
            b -= a;
        }
    }


    fout << a << 'n';


    fin.close();
    fout.close();


    return 0;
}

2. Algoritmul lui Euclid
 
 

/* Author : Kid Koder
   Create Date: 23-Jul-14, 14:51
   Language: C++
   Euclid - CMMDC
*/

#include <fstream>


using namespace std;


ifstream fin("cmmdc.in");
ofstream fout("cmmdc.out");


int main() {
    int a, b;


    fin >> a >> b;


    int r = 0;


    while(b) {
        r = a % b;
        a = b;
        b = r;
    }


    if(a == 1) a = 0;


    fout << a << 'n';


    fin.close();
    fout.close();


    return 0;
}

A doua metoda este mult mai eficienta. Puteti incerca exemplul urmator:

date.in 2 2000003

date.out


1