Trong hướng dẫn này, chúng tôi sẽ phân tích các mẫu khác nhau để tìm GCD bằng các phương thức trong C++.
Chương trình C++ để tìm GCD
Trong C++, để lấy số nguyên dương lớn nhất chia hai số đã cho mà không để lại phần dư, hãy sử dụng GCD (Số chia chung lớn nhất). Nó hỗ trợ đơn giản hóa các phân số và giải quyết các vấn đề liên quan đến các yếu tố chung. Hàm GCD trong một chương trình trả về thừa số chung lớn nhất giữa hai số nguyên đầu vào.
C++ cung cấp nhiều phương pháp để tính GCD của hai số. Một số trong số họ được mô tả dưới đây.
Phương pháp 1: Tìm GCD bằng Thuật toán Euclide trong C++
Các ' Thuật toán Euclid ” là một phương pháp được sử dụng rộng rãi và đáng tin cậy để xác định GCD của hai số khác nhau. Nó dựa trên thực tế là GCD cho hai số nguyên không thay đổi nếu một số nhỏ hơn (số nguyên) bị trừ khỏi số lớn hơn và cách tiếp cận này tiếp tục cho đến khi bất kỳ số nguyên nào trở thành số không.
Hãy cùng xem ví dụ dưới đây, ở đây chúng ta đang tìm (GCD) của hai số bằng thuật toán Euclide. Đầu tiên, bao gồm các thư viện cần thiết:
#include
sử dụng không gian tên tiêu chuẩn ;
Đây:
- “
” tệp tiêu đề bao gồm các luồng đầu vào và đầu ra, cho phép thực hiện các thao tác đầu vào và đầu ra. - “ sử dụng không gian tên std ” là một lệnh giúp sử dụng các tên đến từ không gian tên std dễ dàng hơn.
Sau đó, tuyên bố “ find_GCD() ” hàm nhận hai tham số nguyên “ giá trị1 ' Và ' giá trị2 ' tương ứng. Tiếp theo, sử dụng “ nếu như ” tuyên bố để kiểm tra “ giá trị1 ” bao giờ cũng lớn hơn và bằng “ giá trị2 ”. Sau đó, một “ trong khi ” vòng lặp được sử dụng tiếp tục trả về giá trị cho đến khi điều kiện “ giá trị2 != 0 ” trở thành sai. Bên trong vòng lặp “while”, “value1” được chia cho “value2” và lưu kết quả vào “ phần còn lại ' Biến đổi.
Các giá trị của “value1” và “value2” được cập nhật khi “value1” trở thành giá trị hiện tại của “value2” và “value2” trở thành “phần còn lại” được tính toán. Vòng lặp tiếp tục cho đến khi “value2” trở thành 0, tại thời điểm đó, GCD đã được tìm thấy bằng thuật toán Euclide. Cuối cùng, trả lại “value1” cho hàm “find_GCD”.
int tìm_GCD ( int giá trị1, int giá trị2 ) {nếu như ( giá trị2 > giá trị1 ) {
tráo đổi ( giá trị1, giá trị2 ) ;
}
trong khi ( giá trị2 ! = 0 ) {
int phần còn lại = giá trị1 % giá trị2 ;
giá trị1 = giá trị2 ;
giá trị2 = phần còn lại ;
}
trở lại giá trị1 ;
}
Bên trong ' chủ yếu() ” hàm, khai báo “ số1 ' Và số1 ' biến. Sau đó, sử dụng “ cout ” để nhận đầu vào từ người dùng. Tiếp theo, phần “ Ăn ” đối tượng được sử dụng để đọc các số nguyên đã nhập từ đầu vào tiêu chuẩn và lưu chúng trong các biến “num1” và “num2”. Sau đó, được gọi là “ find_GCD() ” lấy “num1” và “num2” làm tham số và lưu trữ kết quả trong “ my_result ' Biến đổi. Cuối cùng, sử dụng “ cout ” với “ << ” toán tử chèn để in GCD ước tính trên bảng điều khiển:
int chủ yếu ( ) {int số1, số2 ;
cout << 'Nhập hai số' << kết thúc ;
Ăn >> số1 >> số2 ;
int my_result = tìm_GCD ( số1, số2 ) ;
cout << 'GCD của hai số nguyên sử dụng Thuật toán Euclide:' << my_result << kết thúc ;
trở lại 0 ;
}
đầu ra
Phương pháp 2: Tìm GCD đệ quy trong C++
Một phương pháp khác để tính toán GCD trong C++ là sử dụng đệ quy câu lệnh if. Hãy xem ví dụ về chương trình đơn giản dưới đây trong C++.
Trong đoạn mã dưới đây, xác định “ tính_Gcd() ” để tính GCD của hai số. Nó nhận hai tham số nguyên, “ Một ' Và ' b ”. Nó sẽ kiểm tra xem “ b ” bằng với “ 0 ”, sau đó trả lại “ Một ”. Nếu không ' tính_Gcd() ” hàm gọi đệ quy có tham số “ b ' Và ' a%b ”:
#includesử dụng không gian tên tiêu chuẩn ;
int tính_Gcd ( int Một, int b )
{
nếu như ( b == 0 )
trở lại Một ;
trở lại tính_Gcd ( ba % b ) ;
}
Tiếp theo, khai báo các biến “num1” và “num2” bên trong “ chủ yếu() ' chức năng. Sau đó, sử dụng “ cout ” tuyên bố để hiển thị “ Nhập hai số ” tin nhắn, sau đó là “ Ăn ” đối tượng đọc và lưu các biến do người dùng nhập vào. Tiến về phía trước, gọi “ tính_Gcd() ” với giá trị đầu vào là “num1” và “num2”. Được lưu bên trong “ kết quả ” biến và sử dụng “ cout ” để hiển thị giá trị kết quả:
int chủ yếu ( ){
int số1, số2 ;
cout << 'Nhập hai số:' <> số1 >> số2 ;
int kết quả = tính_Gcd ( số1, số2 ) ;
cout << 'GCD của hai số sử dụng phương pháp đệ quy' << kết quả << kết thúc ;
trở lại 0 ;
}
đầu ra
Phương pháp 3: Tìm GCD bằng for Loop trong C++
Chương trình dưới đây đã sử dụng vòng lặp “for” để tìm ước chung lớn nhất:
#bao gồmsử dụng không gian tên tiêu chuẩn ;
int chủ yếu ( ) {
int giá trị1, giá trị2, gcd ;
cout << 'Nhập hai giá trị kiểu số nguyên' <> giá trị1 >> giá trị2 ;
nếu như ( giá trị2 > giá trị1 ) {
int nhiệt độ = giá trị2 ;
giá trị2 = giá trị1 ;
giá trị1 = nhiệt độ ;
}
vì ( int Tôi = 1 ; Tôi <= giá trị2 ; ++ Tôi ) {
nếu như ( giá trị1 % Tôi == 0 && giá trị2 % Tôi == 0 ) {
gcd = Tôi ;
}
}
cout << 'GCD của hai giá trị sử dụng cho Vòng lặp:' << gcd ;
trở lại 0 ;
}
Trong đoạn mã trên, đầu tiên, khai báo ba biến số nguyên “ giá trị1 ”, “ giá trị2 ', Và ' gcd ” bên trong “ chủ yếu() ' chức năng. Tiếp theo, sử dụng “ cout ” để nhận các giá trị đầu vào từ người dùng. Các giá trị đầu vào của người dùng được lưu trong “value1” và “value2” bằng cách sử dụng “ >> ” toán tử với “ Ăn ' sự vật. Sau đó, sử dụng “ nếu như ” câu lệnh để kiểm tra xem “ giá trị1 ' là ' > ' hơn ' giá trị2 ” bằng cách kiểm tra xem “ nhiệt độ ” biến giữ “value2” và sau đó gán nó cho “value1” cho “value2” và “temp” cho “value1”. Sau đó, vòng lặp “for” lặp lại cho đến bên trong “ nếu như ” điều kiện được thỏa mãn. Cuối cùng, sử dụng “ cout ” để in kết quả. Như sau:
Bạn đã học về các phương pháp lập trình C++ để tìm GCD.
Phần kết luận
GCD là một khái niệm toán học quan trọng giúp người dùng xác định số nguyên dương lớn nhất chia hết cả hai số mà không có số dư phía sau. Nhiều phương pháp được sử dụng để tìm GCD trong C++, chẳng hạn như “ Thuật toán Euclid”, “ đệ quy ', Và ' vì ' vòng. Trong hướng dẫn này, chúng tôi đã minh họa các phương pháp lập trình C++ để tìm GCD.