Chuyển đến nội dung chính

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.



Nhận xét

Bài đăng phổ biến từ blog này

Học Lập Trình Android Ở Đâu TpHCM, Hà Nội, Đà Nẵng ? Tốt Nhất, Uy Tín Nhất

Học lập trình Android là một trong những khóa học lập trình được nhiều bạn trẻ tìm kiếm nhất hiện nay bởi mực lương hấp dẫn và ổn định của một lập trình viên android. Đối với các bạn trẻ bắt đầu theo học android việc suy nghĩ học lập trình android ở đâu luôn là vấn đề được rất nhiều quan tâm. Để biết được câu trả lời khách quan nhất về học lập trình android ở đâu tại TpHCM, Hà Nội, Đà Nẵng? Mời bạn tham khảo ngay ý kiến từ Techacademy đưa ra dưới đây nhé! I. Học lập trình android ở đâu tốt nhất Hà Nôi, TpHCM, Đà Nẵng Dưới đây là danh sách các trung tâm đào tạo lập trình android hàng đầu Việt Nam hiện nay. 1, Techacademy Sử dụng phương pháp giảng dạy lập trình android được hiệu quả, giúp học viện hiểu bài và áp dụng thục hành ngay trong thực tế. Đây là phương pháp dạy lập trình android hiệu quả nhất hiện nay, giúp học viên xây dựng sự tự tin khi thực hành. Techacademy là trung tâm đào tạo lập trình android hàng đầu tại Việt Nam, được thành lập với đội ngũ giảng viên, chuyên gia lậ...

Phím Tắt Eclipse Thông Dụng Và Tiện Lợi Nhất ! Đọc Ngay Nếu Bạn Vẫn Đang Dùng Chuột

Việc sử dụng các thao tác click chuột nhiều lần trong Eclipse khiến các coder nhàm chán và tốn thời gian, hãy cải tạo nó bằng các phím tắt trong Eclipse. Dưới đây là danh sách một số những phím tắt thông dụng bạn nên biết. phím tắt eclipse (1) Đầu tiên hãy sử dụng phím tắt Ctrl + Shift + L để hiển thị danh sách các phím tắt trong Eclipse. phím tắt eclipse (2) Danh sách tất cả những phím tắt trong Eclipse bạn có thể áp dụng, được chia thành 12 mục khác nhau tùy thuộc vào tác dụng của phím tắt: 1. Quản lý tập tin và dự án Ctrl + N Tạo dự án mới bằng Wizard Ctrl + Alt + N Tạo dự án , tập tin, lớp, vv Alt + F Mở dự án, tệp, v.v. Ctrl + Shift + R Mở Resource (tệp, thư mục hoặc dự án) Alt + Enter Hiển thị và truy cập các thuộc tính tệp Ctrl + S Save tập tin hiện tại Ctrl + Shift + S Save tất cả các tập tin Ctrl + W Đóng tệp hiện tại Ctrl + Shift + W Đóng tất cả các tệp F5 Làm mới nội dung của phần tử đã chọn bằng hệ thống tệp cục bộ 2. Cửa sổ trình chỉnh sửa F1...

Hướng Dẫn Cài Đặt Python Trên Máy Tính?

Python là một ngôn ngữ lập trình phổ biến và được sử dụng rộng rãi trong lĩnh vực phát triển phần mềm và khoa học dữ liệu. Để bắt đầu sử dụng Python trên máy tính của bạn, bạn cần cài đặt nó. Trong bài viết này, chúng tôi sẽ hướng dẫn bạn cách cài đặt Python trên máy tính một cách dễ dàng. I. Cài Đặt Python Trên Vscode Python là một ngôn ngữ lập trình phổ biến và VS Code là một trình soạn thảo mã nguồn được ưa chuộng. Kết hợp cả hai, bạn có thể tận dụng lợi ích của cả hai công cụ để phát triển ứng dụng Python một cách hiệu quả. Trong bài viết này, chúng tôi sẽ hướng dẫn cách cài đặt Python trên VS Code. Bước 1: Cài đặt VS Code Trước khi bắt đầu, bạn cần cài đặt VS Code trên máy tính của mình. Truy cập trang web vscode.com, tải xuống phiên bản phù hợp với hệ điều hành của bạn và làm theo hướng dẫn trên màn hình để hoàn tất quá trình cài đặt. Bước 2: Cài đặt Extension Python cho VS Code Sau khi cài đặt VS Code, bạn cần cài đặt extension Python để hỗ trợ phát triển ứng dụng Python t...