TÌM ƯỚC CHUNG LỚN NHẤT TRONG C

     

Bài viết chia sẻ 3 thuật toán tìm mong chung bự nhất của 2 số nguyên a b vào lập trình C/C++. UCLN là bài bác toán rất hấp dẫn cho bài toán rèn tư duy sú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 tìm kiếm ước chung lớn nhất C/C++ là 1 bài toán rất lôi cuốn trong lập trình sẵn cơ bản, hầu hết chúng ta mới học lập trình đều rất hứng thú với nó.

Bài toán rất có thể được nêu lên dưới các dạng không giống nhau, cơ mà 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 số trong những là số nhưng mà số đó có thể chia hết, lấy mộ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 hoàn toàn có thể là bao gồm số đó, 1 hay bất kỳ số nguyên làm sao 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 thực hiện phép trừCách 3: search UCLN áp dụng phép chia

Ngoài ra còn có tương đối nhiều cách khác ví như sử dụng thư viện . . . Trong nội dung bài viết này tôi chỉ đề cập cho tới 3 phương pháp 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: Ngày 15 Tháng 1 Năm 2021 Là Ngày Bao Nhiêu Âm Ngày 15 Tháng 1 Năm 2021


*

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: chăm sóc i từ bỏ phần tử bé dại hơn về 1, nếu như cả nhì số A, B đều chia hết mang đến i thì dứt vòng lặp. I đó là ucln của nhì số đó.

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

3. Search UCLN áp dụng phép trừ

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

Nói thì hơi khó khăn hiểu, bạn chỉ việc 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 hợp b > ab = b - a; // Gán lại breturn a; // return b;

4. Thuật toán kiếm 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 chia số b sẽ tiến hành x lần cùng dư r.

Xem thêm: 65 Câu Trắc Nghiệm Khúc Xạ Ánh Sáng Có Đáp Án H Sáng Có Đáp Án

Lúc này công dụng bài toán search ucln của a, b đó là bài toán tìm UCLN của b và r. Tính đến khi r = 0 thì b đó là kết trái ta đề xuất 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 độ 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 phân tách a/breturn b;

Lời kết

Bài viết về UCLN trong lập trình của chính mình đến đó 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 vấn đề này rất dễ dàng và đơn giản 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!