Thuật toán tìm ước chung lớn nhất của 2 số

     

Bài viết chia sẻ 3 thuật toán tìm ước chung to nhất của 2 số nguyên a b vào lập trình C/C++. UCLN là bài xích toán rất thú vị cho câu hỏi rèn tứ duy xúc tích và ngắn gọn với C/C++, java, c#. . .

Bạn đang xem: Thuật toán tìm ước chung lớn nhất của 2 số


1. Reviews bài toán UCLN

Bài toán search ước chung lớn số 1 C/C++ là một trong những bài toán rất hay trong lập trình cơ bản, hầu hết chúng ta mới học tập lập trình thường rất hứng thú với nó.

Bài toán hoàn toàn có thể được nêu lên dưới những dạng khác nhau, mà lại tóm tắt lại là: Tìm mong chung lớn nhất của nhì số nguyên A, B.

Ước của một số là số mà lại số đó rất có thể chia hết, lấy mộ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à bao gồm số đó, 1 hay bất cứ số nguyên làm sao khác.

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

Cách 1: tìm UCLN thực hiện vòng lặpCách 2: tra cứu UCLN sử dụng phép trừCách 3: tìm kiếm UCLN sử dụng phép chia

Ngoài ra còn có khá nhiều cách khác như sử dụng tủ sách . . . Trong nội dung bài viết này mình chỉ đề cập cho 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 vào lập trình.

Xem thêm: Top 15+ Hoa Bàng Nở Vào Mùa Nào ? Tháng Mấy? Vẻ Đẹp Mùa Hoa Ban Đỏ,Trắng


*

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

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

Với phát minh này bạn có thể sử dụng vòng lặp for hoặc while rất nhiều được. Ở phía trên mình cần sử dụng vòng lặp while đến dễ hình dung.

Code C/C++ hàm search ucln1:

int ucln1(int a, int b)int temp;if(b > a) // dùng làm chuyển b thành atemp = b;b = a;a = temp; // sau khối lệnh, ta có a >= bint i = b; // i chạy từ bỏ bwhile(i >= 1) if(a%i == 0 && b%i == 0) // nếu a cùng b cùng phân chia hết mang đến ibreak; // bay vòng lặpi--;return i; // Trả về i, i là UCLN của A, B

3. Tra cứu UCLN sử dụng phép trừ

Thuật toán này còn có ý tưởng chừng như sau: lúc nào a != b thì rước số lớn hơn trừ mang lại số nhỏ nhiều hơn sau đó gán lại cực hiếm bằng chính hiệu vừa tính được. Khi nhì số bằng nhau thì đó chính là ước chung khủng nhất.

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

int ucln2(int a, int b)while(a != b) // lúc a còn không giống bif(a > b) // giả dụ a > cha = a - b; // gán lại aelse // Trường vừa lòng b > ab = b - a; // Gán lại breturn a; // return b;

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

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

Xem thêm: Top 15 Bài Nghị Luận Ngắn Về Bạo Lưc Học Đường Hay Nhất, Nghị Luận Về Vấn Đề Bạo Lực Học Đường Hiện Nay

Lúc này kết quả bài toán kiếm tìm ucln của a, b đó là bài toán kiếm tìm UCLN của b với r. Cho tới khi r = 0 thì b chính là kết trái ta cần tìm.

Thuật toán này còn có độ tinh vi 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 cùng ra = b; b = r;r = a % b; // r là phần dư của phép chia a/breturn b;

Lời kết

Bài viết về UCLN trong lập trình của chính bản thân mình đến đó là hết. Mong muốn rằng các bạn sẽ làm công ty đượ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 chúng ta thành công!