Thứ Tư, 28 Tháng Chín 2022
Trang chủLập trìnhCTDL & Thuật toánCách tìm UCLN và BCNN trong lập trình C/C++

Cách tìm UCLN và BCNN trong lập trình C/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 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ố YX 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 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.

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.

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ố imin(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(a<b) return GCD(a,b-a); // Nếu b>a 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 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<bits/stdc++.h>

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: "<<c;
	
}

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.

Vậy ta có code tìm BCNN như sau:

CHƯƠNG TRÌNH MẪU

#include<bits/stdc++.h>

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: "<<c;
	int tich = a*b;
	cout<<"\nBoi chung nho nhat A, B la: "<<tich/c;
}

Kết quả chương trình:

Cảm ơn bạn đã theo dõi bài viết, chúc bạn học tốt!!

[XEM THÊM NHIỀU BÀI VIẾT LẬP TRÌNH C/C++ TẠI ĐÂY]

XEM THÊM
Thuật toán tìm kiếm nhị phân trong C/C++
Thuật toán tính dãy số Fibonacci bằng 3 cách trong C/C++
Thuật toán đếm số lượng chữ số của số nguyên dương n bằng C / C++
Thuật toán sắp xếp nhanh (Quick Sort)
0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x