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 và BCNN trong bài viết dưới đây nhé.

DANH SÁCH BÀI VIẾT Chương trình cộng trừ 2 số phức trong Lập trình C/C++ Cách tìm UCLN và BCNN trong lập trình C/C++ Thuật toán tính dãy số Fibonacci bằng 3 cách trong C/C++ Kiểm tra số chẵn lẻ trong lập trình C/C++ Cách kiểm tra Số hoàn hảo trong Lập trình C/C++

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(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 + rtứ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ế.

• Khóa học lập trình C/C++ từ A-Z cho người mới – Giảm giá 40% hôm nay
• Khóa học Java cơ bản dành cho người mới bắt đầu- Giảm 40% hôm nay
• Khóa học lập trình Android từ cơ bản đến thành thạo – Giảm ngay 40%

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<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) 3.8 10 Phiếu bình chọn Xếp hạng bài viết