3 thuật toán tìm ước chung lớn nhất C/C – friend.com.vn

Bài viết chia sẻ 3 thuật toán tìm ước chung lớn nhất của 2 số nguyên a b trong lập trình C/C++. UCLN là bài toán rất hay cho việc rèn tư duy logic với C/C++, java, c#. . .

Mục lục bài viết

1. Giới thiệu bài toán UCLN

Bài toán tìm ước chung lớn 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 của hai số nguyên A, B.

Ước của một số là số mà số đó có thể chia hết, 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ố đó. UCLN có thể là chính số đó, 1 hay bất kì số nguyên nào khác.

Có 3 cách để tìm UCLN trong lập trình:

• Cách 1: Tìm UCLN sử dụng vòng lặp
• Cách 2: Tìm UCLN sử dụng phép trừ
• Cách 3: Tìm UCLN sử dụng phép chia

Ngoài ra còn có rất nhiều cách khác như sử dụng thư viện . . . Trong bài viết này mình chỉ đề cập tới 3 cách thông dụng nhất.

Tham khảo 6 thuật toán sắp xếp thông dụng trong lập trình.

2. Tìm ước chung lớn nhất sử dụng vòng lặp

Ý tưởng tìm UCLN sử dụng vòng lặp như sau: Duyệt i từ phần tử nhỏ hơn về 1, nếu cả hai số A, B đều chia hết cho i thì kết thúc vòng lặp. i chính là ucln của hai số đó.

Với ý tưởng này bạn có thể sử dụng vòng lặp for hoặc while đều được. Ở đây mình dùng vòng lặp while cho dễ hình dung.

Code C/C++ hàm tìm ucln1:

int ucln1(int a, int b) int temp; if(b > a) // Dùng để chuyển b thành a temp = b; b = a; a = temp; // sau khối lệnh, ta có a >= b 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

3. 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:

int ucln2(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;

4. Thuật toán tìm UCLN sử dụng phép chia

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.

Lúc này kết quả bài toán tìm ucln của a, b chính là bài toán tìm UCLN của b và r. 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 thấp hơn 2 thuật toán nêu bên trên (tốc độ nhanh hơn 1 tí).

Code C/C++:

int ucln3(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;

Lời kết

Bài viết về UCLN trong lập trình của mình đến đây là hết. Hi vọng rằng bạn sẽ làm chủ được cả 3 thuật toán này. Tưởng chừng bài toán này rất đơn giản nhưng bạn sẽ học đc nhiều từ nó đấy. Chúc bạn thành công!

Xem thêm các bài viết về lập trình C/C++ tại đây