Bài viết share 3 thuật toán tìm ước chung khủng 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 lôi cuốn cho việc rèn bốn duy xúc tích với C/C++, java, c#. . .

Bạn đang xem: Tìm ước chung lớn nhất trong c


1. Reviews bài toán UCLN

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

Bài toán rất có thể được đặt ra dưới nhiều dạng không giống nhau, tuy vậy tóm tắt lại là: Tìm cầu chung lớn số 1 của nhị số nguyên A, B.

Ước của một trong những là số mà lại số đó có thể chia hết, lấy ví dụ 2 là ước của 4 . . . UCLN của nhì số A, B là ước lớn số 1 của cả nhị số đó. UCLN rất có thể là chủ yếu số đó, 1 hay bất kì số nguyên nào khác.

Có 3 phương pháp để tìm UCLN trong lập trình:

Cách 1: tìm UCLN áp dụng vòng lặpCách 2: search UCLN áp dụng phép trừCách 3: tìm kiếm UCLN thực hiện 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 giải pháp thông dụng nhất.

Tham khảo 6 thuật toán bố trí thông dụng trong lập trình.


*

2. Tìm cầu 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: xem xét i trường đoản cú phần tử bé dại hơn về 1, ví như cả nhì số A, B rất nhiều chia hết đến i thì chấm dứt vòng lặp. I đó 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 những được. Ở đây mình sử dụng vòng lặp while đến dễ hình dung.

Code C/C++ hàm tra cứu 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ự bwhile(i >= 1) if(a%i == 0 && b%i == 0) // giả dụ a với b cùng phân chia hết cho ibreak; // bay vòng lặpi--;return i; // Trả về i, i là UCLN của A, B

3. Tìm kiếm UCLN thực hiện phép trừ

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

Nói thì hơi khó khă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) // khi a còn khác bif(a > b) // ví như a > tía = a - b; // gán lại aelse // Trường hợp b > ab = b - a; // Gán lại breturn a; // return b;

4. Thuật toán tìm kiếm UCLN thực hiện 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ẽ được x lần với dư r.

Xem thêm: Tính Tổng 1+1/2+1/3+...+1/N Trong C, Lập Trình C++ Tính Tổng S=1

Lúc này công dụng bài toán tìm ucln của a, b đó là bài toán kiếm tìm UCLN của b và r. Tính đến khi r = 0 thì b chính là kết quả ta yêu cầu tìm.

Thuật toán này còn có độ phức hợp thấp hơn 2 thuật toán nêu trên (tốc độ cấp tốc 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 kiếm tìm ucln của b và ra = b; b = r;r = a % b; // r là phần dư của phép phân chia a/breturn b;

Lời kết

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