tìm ước chung lớn nhất c++

Trong nội dung bài viết này tôi tiếp tục nằm trong chúng ta lần hiểu về những thuật toán lần ước cộng đồng lớn số 1 của nhị số nguyên vẹn và minh họa code vì chưng ngôn từ C/C++.

Định nghĩa ước cộng đồng rộng lớn nhất

Bạn đang xem: tìm ước chung lớn nhất c++

Ước cộng đồng lớn số 1 (GCD – Greatest Common Divisor) của 2 số nguyên  và  là số nguyên vẹn rộng lớn nhất  thỏa mãn đặc điểm cả a và b đều phân chia không còn mang lại d.

Dưới đó là một trong những cơ hội thông thường được dùng nhằm giải quyết và xử lý Việc lần ước cộng đồng lớn số 1 của nhị số.

Cách 1. Tìm UCLN dùng phép tắc trừ

Đây là sơ thiết bị của thuật toán này

Code minh họa

// Code from https://indonesia-hanoi.org.vn

int gcd(int a, int b){
    // Nếu a = 0 => ucln(a,b) = b
    // Nếu b = 0 => ucln(a,b) = a
    if (a == 0 || b == 0){
        return a + b;
    }
    while (a != b){
        if (a > b){
            a -= b; // a = a - b
        }else{
            b -= a;
        }
    }
    return a; // return a or b, cũng chính vì thời điểm này a và b vì chưng nhau
}

Giải thích:

Tại từng bước một lặp nó sẽ bị đánh giá độ quý hiếm lúc này của a và b coi thằng này to hơn. 
Ví dụ với nhị số a = 7, b = 5

L1: a > b => a = 2, b = 5
L2: b > a => a = 2, b = 3
L3: b > a => a = 2, b = 1
L4: a > b => a = 1, b = 1
L5: a == b => trả về a hoặc b đều được => KQ là 1

Xem thêm: Các share hoặc được đúc rút kể từ kinh nghiệm tay nghề của tác giả

Cách 2. Tìm UCLN dùng phép tắc phân chia dư

Sơ thiết bị thuật toán tương tự động như cơ hội 1. Chỉ thay cho thay đổi phép tắc trừ thanh lịch phép tắc phân chia dư.

Code minh họa

// Code from https://indonesia-hanoi.org.vn

int gcd(int a, int b){
    // Lặp cho tới Lúc một trong những 2 số vì chưng 0
    while (a*b != 0){ 
        if (a > b){
            a %= b; // a = a % b
        }else{
            b %= a;
        }
    }
    return a + b; // return a + b, cũng chính vì thời điểm này hoặc a hoặc b đang được vì chưng 0.
}

Cách 3. Tìm UCLN dùng giải thuật Euclid

Cho a, b là nhị số nguyên vẹn (giả sử a ≥ b), nhằm lần ước cộng đồng lớn số 1 của nhị số a và b tớ cần thiết triển khai phân chia a mang lại b được thương q và số dư r (r ≥ 0) tức là a = b*q + r, Lúc cơ tớ có:

Xem thêm: Bất động sản Thị Xã Phú Mỹ, BRVT có gì nổi bật? Căn hộ Tumys Phú Mỹ có đáng để đầu tư?

Cài đặt điều thuật toán dùng đệ quy.

// Code from https://indonesia-hanoi.org.vn

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

Cài đặt điều khử đệ quy

// Code from https://indonesia-hanoi.org.vn

int gcd(int a, int b) {
    int tmp;
    while(b != 0) {
        tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

Gợi ý: Một số nội dung bài viết về giải thuật tương tự

Cách 4. Tìm UCLN dùng hàm đã có sẵn của C++

Để rất có thể sử người sử dụng hàm lần ucln nhập C++ tớ cần thiết thêm thắt thư viện algorithm.

Ví dụ minh họa:

// Code from https://indonesia-hanoi.org.vn
#include <algorithm>
#include <stdio.h>
int main(){
    int a = 5, b = 9;
    printf("ngcd(%d, %d) = %d", a, b, std::__gcd(a,b));
}

Tổng kết toàn bộ cơ hội liệu pháp bên trên trong một công tác.

Xem thêm: những danh lam thắng cảnh ở việt nam

// Code from https://indonesia-hanoi.org.vn

#include <stdio.h>
#include <algorithm>
int gcd1(int a, int b){
    // Nếu a = 0 => ucln(a,b) = b
    // Nếu b = 0 => ucln(a,b) = a
    if (a == 0 || b == 0){
        return a + b;
    }
    while (a != b){
        if (a > b){
            a -= b; // a = a - b
        }else{
            b -= a;
        }
    }
    return a; // return a or b, cũng chính vì thời điểm này a và b vì chưng nhau
}

int gcd2(int a, int b){
    // Nếu a = 0 => ucln(a,b) = b
    // Nếu b = 0 => ucln(a,b) = a
    if (a == 0 || b == 0){
        return a + b;
    }
    // Lặp cho tới Lúc một trong những 2 số vì chưng 0
    while (a*b != 0){
        if (a > b){
            a %= b; // a = a % b
        }else{
            b %= a;
        }
    }
    return a + b; // return a + b, cũng chính vì thời điểm này hoặc a hoặc b đang được vì chưng 0.
}

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

int gcd4(int a, int b) {
    int tmp;
    while(b != 0) {
        tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

int main(){
    int a = 5, b = 9;
    printf("ngcd1(%d, %d) = %d", a, b, gcd1(a,b));
    printf("ngcd2(%d, %d) = %d", a, b, gcd2(a,b));
    printf("ngcd3(%d, %d) = %d", a, b, gcd3(a,b));
    printf("ngcd4(%d, %d) = %d", a, b, gcd4(a,b));
    printf("ngcd5(%d, %d) = %d", a, b, std::__gcd(a,b));
}

Kết trái ngược chạy thử

gcd1(5, 9) = 1
gcd2(5, 9) = 1
gcd3(5, 9) = 1
gcd4(5, 9) = 1
gcd5(5, 9) = 1

Trên trên đây tôi đang được trình diễn cụ thể về những thuật toán lần ước cộng đồng lớn số 1 của nhị số. Nếu độc giả quan hoài hoặc sở hữu vướng mắc gì. Vui lòng nhằm lại ở phản hồi phía cuối nội dung bài viết.

Nếu chúng ta quan hoài cho tới lần BCNN của 2 số, vui sướng lòng chuyển sang nội dung bài viết lần BCNN của 2 số nhé.