Hàm Tìm Ước Chung Lớn Nhất Trong C

     

Bài viết share 3 thuật toán tìm ước chung to nhất của 2 số nguyên a b trong lập trình C/C++. UCLN là bài xích toán rất hấp dẫn cho việc rèn bốn duy xúc tích và ngắn gọn với C/C++, java, c#. . .

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


1. Trình làng bài toán UCLN

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

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

Ước của một số trong những là số nhưng số đó có thể chia hết, ví dụ 2 là ước của 4 . . . UCLN của nhì 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 như thế nào khác.

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

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

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

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

Xem thêm: Sử Dụng Phần Mềm Vẽ Sơ Đồ Erd Tool, Sử Dụng Phần Mềm Vẽ Erd


*

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

Ý tưởng tìm UCLN sử dụng vòng lặp như sau: cẩn thận i từ bỏ phần tử bé dại hơn về 1, trường hợp cả nhị số A, B những chia hết đến i thì xong xuôi vòng lặp. I đó là ucln của nhì số đó.

Với phát minh này chúng ta có thể sử dụng vòng lặp for hoặc while đầy đủ được. Ở trên đây mình dùng vòng lặp while mang đế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 bao gồm a >= bint i = b; // i chạy tự bwhile(i >= 1) if(a%i == 0 && b%i == 0) // nếu như a với b cùng chia hết cho ibreak; // thoát vòng lặpi--;return i; // Trả về i, i là UCLN của A, B

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

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

Nói thì hơi khó 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 UCLN áp dụng phép chia

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

Xem thêm: Chồng Cung Ly Lấy Vợ Cung Cấn, Chồng Cung Ly Lấy Vợ Cung Gì, Tốt Hay Xấu:

Lúc này kết quả bài toán tra cứu ucln của a, b đó là bài toán kiếm tìm UCLN của b và r. Cho tới khi r = 0 thì b đó là kết trái ta buộc phải tìm.

Thuật toán này có độ tinh vi 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, trở lại 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 chia a/breturn b;

Lời kết

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