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

Bài Toán: Tìm UCLN của 2 số. Ước chung lớn nhất  của hai số là số nguyên dương lớn nhất là ước số chung của 2 số đó.

Ví dụ: UCLN của 20 và 28 là 4 và UCLN của 98 và 56 là 14.

Thuật toán đơn giản nhất là thuật toán Euclid bằng phép trừ

Nó là một quá trình lặp lại phép trừ, mang kết quả về phía trước mỗi lần cho đến khi kết quả bằng với một số bất kỳ bị trừ. Nếu câu trả lời lớn hơn 1, có một GCD (bên cạnh 1). Nếu câu trả lời là 1, không có ước số chung (ngoài 1), và do đó cả hai số đều là số nguyên tố

mã giả cho cách tiếp cận trên:

def gcd(a, b):
 if a == b:
 return a
 if a > b:
 gcd(a – b, b)
 else:
 gcd(a, b – a)

Tại một thời điểm nào đó, một số trở thành thừa số của số kia, vì vậy thay vì trừ liên tục cho đến khi cả hai trở nên bằng nhau, chúng ta kiểm tra xem nó có phải là thừa số của số kia hay không.

Ví dụ 1: Giả sử a = 98 & b = 56 a> b nên đặt a = a-b và b không đổi. Vậy a = 98-56 = 42 & b = 56. Vì b> a nên ta kiểm tra xem b% a == 0 hay không. vì câu trả lời là không, chương trình tiếp tục lặp lại. Bây giờ b > a nên b = b-a và a không đổi. Vậy b = 56-42 = 14 & a = 42. Vì a > b nên chúng ta kiểm tra xem a % b == 0. Bây giờ câu trả lời là có. Vì vậy, UCLN là 14.

Ví Dụ 2: Giả sử a = 36 & b = 60, ở đây b > a nên b = 24 & a = 36 nhưng a% b != 0. Bây giờ a > b nên a = 12 & b = 24. và b % a == 0. UCLN là 12
Giải pháp đơn giản:

Phương Pháp 1: Để tìm UCLN của hai số, trước hết ta sẽ tìm số nhỏ nhất của hai số đó rồi tìm nhân tử chung lớn nhất của số nhỏ nhất đó cũng là nhân tử của số kia.

// C++ program to find GCD of two numbers
#include <iostream>
using namespace std;
// Function to return gcd of a and b
int gcd(int a, int b)
{
   int result = min(a, b); // Find Minimum of a nd b
   while (result > 0) {
      if (a % result == 0 && b % result == 0) {
         break;
      }
      result--;
   }
   return result; // return gcd of a nd b
}

// Driver program to test above function
int main()
{
   int a = 98, b = 56;
   cout << "GCD of " << a << " and " << b << " is "
      << gcd(a, b);
   return 0;
}
// This code is contributed by Suruchi Kumari

Output:

GCD of 98 and 56 is 14

Độ phức tạp về thời gian: O (min (a, b))

Phương Pháp 2: Sử dụng thuật toán Euclide, đây là thuật toán chính được sử dụng cho mục đích này. Ý tưởng là,UCLN của hai số không thay đổi nếu số nhỏ hơn bị trừ cho số lớn hơn. Tức là UCLN (a, b) <=> UCLN(a-b, b) nếu a > b OR UCLN(a, b – a) nếu a < b

// C++ program to find GCD of two numbers
#include <iostream>
using namespace std;
// Recursive function to return gcd of a and b
int gcd(int a, int b)
{
   // Everything divides 0
   if (a == 0)
   return b;
   if (b == 0)
   return a;

   // base case
   if (a == b)
      return a;

   // a is greater
   if (a > b)
      return gcd(a-b, b);
   return gcd(a, b-a);
}

// Driver program to test above function
int main()
{
   int a = 98, b = 56;
   cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
   return 0;
}

Output:

GCD of 98 and 56 is 14

Độ phức tạp về thời gian: O (min (a, b))

Phương pháp 3: Lập trình động

// C++ program to find GCD of two numbers
#include <bits/stdc++.h>
using namespace std;

int static dp[1001][1001];

// Function to return gcd of a and b
int gcd(int a, int b)
{
   // Everything divides 0
   if (a == 0)
      return b;
   if (b == 0)
      return a;

   // base case
   if (a == b)
      return a;
   
   // if a value is already
   // present in dp
   if(dp[a][b] != -1)
      return dp[a][b];

   // a is greater
   if (a > b)
      dp[a][b] = gcd(a-b, b);
   
   // b is greater
   else
      dp[a][b] = gcd(a, b-a);
   
   // return dp
   return dp[a][b];
}

// Driver program to test above function
int main()
{
   int a = 98, b = 56;
   memset(dp, -1, sizeof(dp));
   cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
   return 0;
}

Output:

GCD of 98 and 56 is 14

Độ phức tạp về thời gian: O (min (a, b))

Phương Pháp 4: Thay vì thuật toán Euclide bằng phép trừ, chúng ta có thể liên tục chia số lớn hơn với số nhỏ hơn. Có thể tìm hiểu thêm về thuật toán hiệu quả này bằng cách sử dụng toán tử modulo trong thuật toán Euclide.

// C++ program to find GCD of two numbers
#include <iostream>
using namespace std;
// Recursive function to return gcd of a and b in single line
int gcd(int a, int b)
{
   return b == 0 ? a : gcd(b, a % b);
}

// Driver program to test above function
int main()
{
   int a = 98, b = 56;
   cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
   return 0;
}

Output:

GCD of 98 and 56 is 14

Độ phức tạp về thời gian: O (log (min (a, b))

The post Tìm Ước Chung Lớn Nhất Trong C++ first appeared on Techacademy.

source https://techacademy.edu.vn/tim-uoc-chung-lon-nhat-trong-c/