Viết chương trình tìm bội chung nhỏ nhất c++

Tiếp tục Series bài viết CTDL & Thuật toán, hôm nay hãy cùng blog TUICOCACH.COM tìm hiểu về thuật toán tìm UCLN và BCNN trong bài viết dưới đây nhé.

Giới thiệu bài toán UCLN, BCNN

Bài toán tìm ước chung lớn nhất, bội chung nhỏ nhất C/C++ là một bài toán rất hay trong lập trình cơ bản, hầu hết các bạn mới học lập trình đều rất hứng thú với nó.

Bài toán có thể được nêu lên dưới nhiều dạng khác nhau, nhưng tóm tắt lại là: Tìm ước chung lớn nhất hay Tìm bội chung nhỏ nhất của hai số nguyên A, B.

Ước của một số X là số Y mà X có thể chia hết cho Y, ví dụ 2 là ước của 4 . . . UCLN của hai số A, B là ước lớn nhất của cả hai số đó(Tức là số lớn nhất mà cả A và B đều chia hết). UCLN có thể là chính số A hoặc B, 1 hay bất kì số nguyên nào khác.

Tương tự, Bội của một số X là số Y mà Y có thể chia hết cho X, ví dụ 4 là bội của 2 . . . BCNN của hai số A, B là bội nhỏ nhất của cả hai số đó(Tức là số nhỏ nhất mà có thể chia hết cho cả A và B). BCNN có thể là chính số A hoặc B, hay bất kì số nguyên nào khác, tuy nhiên BCNN không thể nhỏ hơn A hoặc B.

Có 3 cách thường dùng nhất để tìm UCLN trong lập trình:

• Cách 1: Kiểm tra tuần tự.
• Cách 1: Tìm UCLN sử dụng phép trừ.
• Cách 2: Tìm UCLN sử dụng phép chia(Hay còn gọi là giải thuật Euclid).

Để tìm BCNN, sau khi đã có UCLN ta chỉ việc lấy tích A, B chia cho UCLN.

• Kiếm tiền Accesstrade, kiếm tiền tại nhà với Accesstrade.vn – Tiếp thị liên kết
• MegaURL – Rút gọn link kiếm tiền có giá cao tại Việt Nam
• Top 4 App kiếm tiền online trên điện thoại tốt nhất 2022

Giải thuật tìm UCLN và BCNN

Tìm UCLN bằng cách kiểm tra tuần tự

Ý tưởng tìm UCLN bằng cách kiểm tra tuần tự như sau:

• Bước 1: Tìm số minab = min(A,B) – Tìm số nhỏ hơn giữa 2 số A và B.
• Bước 2: Duyệt vòng lặp i chạy ngược từ minAB tới 1(tính cả số 1 và minAB).
• Bước 3: Nếu cả 2 số A, B đều chia hết i dừng thuật toán, và i chính là UCLN cần tìm.

Minh họa thuật toán

Giải thuật bằng vòng lặp

int GCD(int a, int b){
    int temp;
    if(b > a) {   // Nếu b > a ta chạy khối lệnh để chuyển b thành a và ngược lại
        temp = b;
        b = a;
        a = temp;
    }     // sau khối lệnh, a mặc định sẽ là số được gắn bằng số lớn hơn, b là số nhỏ hơn
    
    int i = b;  // i chạy từ b
    while(i >= 1) {
        if(a%i == 0 && b%i == 0)  // nếu a và b cùng chia hết cho i
            break;          // thoát vòng lặp
        i--;
    }
    return i;   // Trả về i, i là UCLN của A, B
}

Giải thuật bằng đệ quy

int GCD(int a, int b, int i){
    if(a%i==0 && b%i==0) return i; // nếu a và b cùng chia hết cho i trả về kq cho hàm
    return GCD(a,b,i-1); //Gọi đệ quy và i giảm đi 1
}

Lưu ý: Trong giải thuật bằng đệ quy phần này mặc định bạn phải tìm trước số i là min(a,b), sau đó mới gọi và truyền tham số cho hàm.

Tìm UCLN sử dụng phép trừ

Thuật toán này có ý tưởng như sau: Khi nào a != b thì lấy số lớn hơn trừ cho số bé hơn sau đó gán lại giá trị bằng chính hiệu vừa tính được. Khi hai số bằng nhau thì đó chính là ước chung lớn nhất.

Nói thì hơi khó hiểu, bạn chỉ cần nhớ thuật toán là được, cùng tham khảo code C/C++ phía dưới:

Minh họa giải thuật bằng vòng lặp

int GCD(int a, int b){
    while(a != b){  // Khi a còn khác b
        if(a > b)  // nếu a > b
            a = a - b;   // gán lại a
        else    // Trường hợp b > a
            b = b - a;   // Gán lại b
    }
    return a; // return b;
}

Minh họa giải thuật bằng đệ quy

int GCD(int a, int b){
	if(a==b) return a; //Nếu a bằng với b trả về qk là a hoặc b
	if(a>b) return GCD(a-b,b); // Nếu a > b Gọi hàm đệ quay lại bài toán tính UCLN  a-b và b
	if(aa Gọi hàm đệ quay lại bài toán tính UCLN a và b-a
}

Thuật toán tìm UCLN sử dụng phép chia(giải thuật Euclid)

Có một công thức toán học được nêu ra như sau: a = b*x + r
tức là: số a chia số b sẽ được x lần và dư r.

Với thuật toán này bạn có thể hiểu đơn giản như sau: Lấy a%b được r, gắn lại a = b, b=r, lúc này bài toán quay lại tìm UCLN của b và r. Thực hiện lặp cho tới khi r = 0 thì b chính là kết quả ta cần tìm.

Thuật toán này có độ phức tạp rất thấp nên thường được ưu tiên trong các bài toán thực tế.

Minh họa giải thuật bằng vòng lặp

int GCD(int a, int b ){
    int r = a % b;         // a = b*x + r;
    while (r!=0) {
        // Gán lại a = b, quay về bài toán tìm ucln của b và r
        a = b;  
        b = r;
        r = a % b;   // r là phần dư của phép chia a/b
    }
    
    return b;
}

Minh họa giải thuật bằng đệ quy

int GCD(int a, int b){
	if(b==0) return a; //Sau đệ quy lúc này kiểm tra b chính là a%b được truyền vào tức nó chính là r, còn a chính là b được truyền vào
	return GCD(b, a%b); // Gọi lại hàm đệ quy tính UCLN giữa b và r
}

Nếu bạn là người bắt đầu, với hàm Đệ quy này nhìn vào có thể bạn sẽ không hình dung ra được thuật toán chạy ra làm sao…bạn nên thăm khảo thêm bài viết dưới đây.

Tìm hiểu về Hàm đệ quy trong lập trình

Tìm bội chung nhỏ nhất

Đầu tiên chúng ta hãy chạy thử 1 chương trình tính UCLN với 1 trong các thuật toán bên trên như sau.

#include

using namespace std;

int GCD(int a, int b){
	if(b==0) return a;
	return GCD(b, a%b);
}
int main()
{
	int a=4,b=6;
	int c = GCD(a,b);
	cout<<"Uoc chung lon nhat A, B la: "<
Kết quả chương trình:
Chúng ta tìm được UCLN của 4 và 6 là 2. Như đã nêu ở trên để tìm BCNN ta sẽ lấy tích 2 số a, b chia cho UCLN. Tức là BCNN của 4 và 6 sẽ là (4*6)/2 = 12.