Thuật toán tìm ước chung lớn nhất trong C / C++

Trong bài viết này, codehow sẽ giới thiệu các bạn thuận toán tìm ước chung lớn nhất trong C / C++. Đây là bài toán áp dụng kiến thức toán học cơ sở và kiến thức lập trình căn bản trong C / C++.

Ví dụ: Mình có hai số 10 và 20 thì UCLN của hai số này là 10. Vì 10 và 20 đều chia hết cho 10 (đây cũng là số lớn nhất mà cả hai chia hết).

Đến đây chắc các bạn cũng đã hiểu sơ qua về UCLN rồi đúng không ạ, vậy ngay bây giờ hãy bắt đầu cùng mình viết thuật toán thôi nào.

Thuật toán tìm ước chung lớn nhất trong C / C++

Đối với bài toán này có rất nhiều cách thực hiện, trong bài viết này mình sẽ thực hiện hai cách đơn giản nhất để các bạn lựa chọn và sử dụng.

Tìm UCLN bằng vòng lặp for

Dưới đây là thuật toán tìm ước chung lớn nhất trong C / C++ sử dụng vòng lặp for. Đây là cách căn bản nhất khi chúng ta làm việc với vòng lặp.

Các bạn hãy xem qua thuật toán rồi mình sẽ giải thích ngay bên dưới nhé.

//Hàm tìm ước chung lớn nhất
int UCLN(int A, int B) {
  int hcf;
    for(int i = 1; i <= A || i <= B; i++) {
     if( A%i == 0 && B%i == 0 )
      hcf = i;
   }
  return hcf;
}

Giải thích thuật toán:

1. Khai báo biến hcf để lưu kết quả là UCLN của hàm trả về.
2. Sử dụng vòng lặp for để lặp từ 1 đến A hoặc lặp từ 1 đến B, với bước nhảy là i++.
3. Bên trong vòng lặp, nếu A và B đều chia hết cho i thì hcf = i. Cứ như vậy cho đến khi kết thúc vòng lặp, ta được hcf là UCLN.

//Hàm tìm ước chung lớn nhất
int UCLN(int A, int B) {
    for(int i = min(A, B); i > 0; --i) {
        if (A % i == 0 && B % i ==0)
            return i;
    }
    //Không chạy tới đây vì A, B luôn chia hết cho 1
}

Giải thích thuật toán:

• Sử dụng vòng lặp for lặp từ min(A, B) về i > 0, với bước nhảy i--.
• Nếu A và B chia hết cho i thì đây là ước số chung lớn nhất của A và B.

Tìm UCLN bằng cách sử dụng hàm có sẵn

Ngoài cách sử dụng vòng lặp for, các bạn có thể sử dụng hàm __gcd() có sẵn trong thư viện <algorithm> của C / C++. Đây là cách nhanh nhất để tìm UCLN của hai số A và B, chỉ cần khai báo thư viện <algorithm> là có thể sử dụng nó rồi.

Ví dụ: Mình cần tìm ước chung lớn nhất của hai số A = 10 và B = 20.

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int A,B;
    A = 10;
    B = 20;
    cout <<"UCLN(10,20) = "<< __gcd(A, B);

    cout<<"\n---------------------------\n";
    cout<<"Chương trình này được đăng tại codehow.net";
}

Kết quả:

Vi dụ thuật toán tìm ước chung lớn nhất trong C / C++

Trong phần này, mình sẽ sử dụng thuật toán tìm ước chung lớn nhất trong C / C++ để thực hiện chương trình tìm UCLN của hai số do người dùng nhập. Để các bạn có thể lựa chọn, mình sẽ áp dụng cả hai thuật toán luôn nhé.

Ví dụ 1: Tìm UCNL của hai số do người dùng nhập sử dụng vòng lặp for.

Chương trình C:

#include <stdio.h>
#include <stdbool.h>

//Hàm tìm ước chung lớn nhất
int UCLN(int A, int B) {
  int hcf;
    for(int i = 1; i <= A || i <= B; i++) {
     if( A%i == 0 && B%i == 0 )
      hcf = i;
   }
  return hcf;
}

int main() {
    int A,B;
    printf("Nhập vào số A = ");
    scanf("%d", &A);
    printf("Nhập vào số B = ");
    scanf("%d", &B);

    printf("Ước chung lớn nhất của hai số %d và %d là:\n",A,B);
    printf("UCLN(%d,%d) = %d",A,B,UCLN(A,B));

    printf("\n---------------------------\n");
    printf("Chương trình này được đăng tại codehow.net");
}

Kết quả:

Chương trình C++:

#include <bits/stdc++.h>
using namespace std;
 
//Hàm tìm ước chung lớn nhất
int UCLN(int A, int B) {
    for(int i = min(A, B); i > 0; --i) {
        if (A % i == 0 && B % i ==0)
            return i;
    }
    //Không chạy tới đây vì A, B luôn chia hết cho 1
}
int main() {
  //khai báo hai số A và B
  int A,B;
  //yêu cầu người dùng nhập vào hai số A và B
  cout<<"Nhập số A: ";
  cin>>A;
  cout<<"Nhập số B: ";
  cin>>B;
  //Gọi hàm UCLN() rồi truyền hai số A và B vào hàm để tìm UCLN
  cout<<"Ước chung lớn nhất của hai số "<<A<<" và "<<B<<" là:\n";
  cout <<"UCLN("<<A<<","<<B<<") = "<< UCLN(A, B);

  cout<<"\n---------------------------\n";
  cout<<"Chương trình này được đăng tại codehow.net";
}

Kết quả:

Ví dụ 2: Tìm UCLN của hai số do người dùng nhập sử dụng hàm có sẵn.

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int A,B;
    cout<<"Nhập vào số A = ";
    cin>>A;
    cout<<"Nhập vào số B = ";
    cin>>B;
    cout<<"Ước chung lớn nhất của hai số "<<A<<" và "<<B<<" là:\n";
    cout <<"UCLN("<<A<<","<<B<<") = "<< __gcd(A, B);

    cout<<"\n---------------------------\n";
    cout<<"Chương trình này được đăng tại codehow.net";
}

Kết quả:

Như vậy là chúng ta đã cùng nhau tìm hiểu về thuật toán tìm ước chung lớn nhất trong C / C++. Các bạn hãy luyện tập thật nhiều để có thể sử dụng các thuật toán một cách thành thạo nhé. Chúc các bạn thành công !!!