Ví dụ về các cách khác nhau để tính GCD của hai số nguyên (cho cả số nguyên dương và số nguyên âm) bằng cách sử dụng vòng lặp và các câu lệnh ra quyết định.
Để hiểu ví dụ này, bạn nên có kiến thức về các chủ đề lập trình C sau:
- Toán tử lập trình C
- C cho Vòng lặp
- Câu lệnh C if… else
- C while và do… while Loop
HCF hoặc GCD của hai số nguyên là số nguyên lớn nhất có thể chia chính xác cả hai số (không có phần dư).
Có nhiều cách để tìm ước số chung lớn nhất trong lập trình C.
Ví dụ # 1: GCD Sử dụng vòng lặp for và câu lệnh if
#include int main() ( int n1, n2, i, gcd; printf("Enter two integers: "); scanf("%d %d", &n1, &n2); for(i=1; i <= n1 && i <= n2; ++i) ( // Checks if i is factor of both integers if(n1%i==0 && n2%i==0) gcd = i; ) printf("G.C.D of %d and %d is %d", n1, n2, gcd); return 0; )
Trong chương trình này, hai số nguyên do người dùng nhập vào được lưu trong biến n1 và n2, sau đó, forvòng lặp được lặp lại cho đến khi i nhỏ hơn n1 và n2.
Trong mỗi lần lặp, nếu cả n1 và n2 đều chia hết cho i thì giá trị của i được gán cho gcd.
Khi forhoàn tất vòng lặp, ước số chung lớn nhất của hai số được lưu trữ trong biến gcd.
Ví dụ # 2: GCD Sử dụng vòng lặp while và câu lệnh if… else
#include int main() ( int n1, n2; printf("Enter two positive integers: "); scanf("%d %d",&n1,&n2); while(n1!=n2) ( if(n1> n2) n1 -= n2; else n2 -= n1; ) printf("GCD = %d",n1); return 0; )
Đầu ra
Nhập hai số nguyên dương: 81 153 GCD = 9
Đây là cách tốt hơn để tìm GCD. Trong phương pháp này, số nguyên nhỏ hơn bị trừ khỏi số nguyên lớn hơn và kết quả được gán cho biến chứa số nguyên lớn hơn. Quá trình này được tiếp tục cho đến khi n1 và n2 bằng nhau.
Hai chương trình trên chỉ hoạt động như dự định nếu người dùng nhập số nguyên dương. Đây là một chút sửa đổi của ví dụ thứ hai để tìm GCD cho cả số nguyên dương và số nguyên âm.
Ví dụ # 3: GCD cho cả số dương và số âm
#include int main() ( int n1, n2; printf("Enter two integers: "); scanf("%d %d",&n1,&n2); // if user enters negative number, sign of the number is changed to positive n1 = ( n1> 0) ? n1 : -n1; n2 = ( n2> 0) ? n2 : -n2; while(n1!=n2) ( if(n1> n2) n1 -= n2; else n2 -= n1; ) printf("GCD = %d",n1); return 0; )
Đầu ra
Nhập hai số nguyên: 81 -153 GCD = 9
Bạn cũng có thể sử dụng đệ quy để tìm GCD.
