Hướng dẫn giải của Rút gọn phân số
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu rút gọn một phân số a/b về phân số tối giản. Phân số có thể là số nguyên nếu mẫu số chia hết cho tử số sau khi rút gọn. Nếu mẫu số b bằng 0, phân số không hợp lệ và cần in ra 'INVALID'. Các số a, b có thể âm, và phân số tối giản phải có mẫu số dương. Nếu phân số rút gọn là một số nguyên (mẫu số là 1), chỉ cần in ra số nguyên đó.
Các cách tiếp cận
Cách Tìm Ước Chung Lớn Nhất (UCLN) bằng Vòng lặp For
#include <stdio.h>
int ucln(int a, int b) {
if (a<0) a=-a;
if (b<0) b=-b;
if (a==0) return b;
if (b==0) return a;
int max = 1;
for (int i = 1; i <= a && i <= b; i++) {
if (a % i == 0 && b % i == 0) {
max = i;
}
}
return max;
}
int main() {
int a, b;
scanf("%d %d", &a, &b);
if (b == 0) {
printf("INVALID");
return 0;
}
int d = ucln(a, b);
a /= d;
b /= d;
if (b < 0) {
a = -a;
b = -b;
}
if (b == 1)
printf("%d", a);
else
printf("%d %d", a, b);
return 0;
}
- Time Complexity: O(min(|a|, |b|))
- Space Complexity: O(1)
Phương pháp này sử dụng một vòng lặp để tìm ước chung lớn nhất. Nó duyệt qua tất cả các số từ 1 đến số nhỏ hơn giữa |a| và |b| để tìm số chia hết cho cả hai. Đây là cách tiếp cận đơn giản nhất nhưng hiệu quả nhất về mặt thời gian chạy.
Cách Tìm Ước Chung Lớn Nhất (UCLN) bằng Thuật toán Euclid
#include <stdio.h>
#include <math.h>
int ucln(int a, int b){
while (b!=0){
a=abs(a);
b=abs(b);
int c=a%b;
a=b;
b=c;
} return a;
}
int main(){
int a,b;
scanf("%d%d", &a, &b);
if(a==0 &&b==0){
printf("INVALID");
return 0;
}
if(a!=0 && b==0){
printf("INVALID");
}
if(a==0 && b!=0){
printf("0");
}
if(a!=0 && b!=0){
int i=ucln(a,b);
a/=i;
b/=i;
if(b<0){
printf("%d %d\n", -a, -b);
return 0;
}
if(b==1){
printf("%d", a);
return 0;
}
if(b>0) printf("%d %d\n", a, b);
}
}
- Time Complexity: O(log(min(|a|, |b|)))
- Space Complexity: O(1)
Thuật toán Euclid dựa trên tính chất rằng UCLN(a, b) = UCLN(b, a % b). Phương pháp này nhanh hơn đáng kể so với vòng lặp duyệt toàn bộ, đặc biệt với các số lớn, vì số bước lặp giảm dần theo cấp số nhân.
Cách Tối ưu hóa thủ công
#include <stdio.h>
int main() {
int a, b;
int S = 0;
scanf("%d %d", &a, &b);
if (b == 0){
printf("INVALID");
return 0;
}
if (a == b){
printf ("1");
return 0;
}
if (a== 0){
printf ("%d" , a);
return 0;
}
if ( b < 0) {
b = -b;
a = -a;
}
if ( a % b == 0) {
printf ("%d" , a/b);
return 0;
}
for ( int i = 1 ; i <= b ; i++)
{
if ((a % i == 0) && (b % i == 0)) {
S = i;
}
}
printf("%d " , a/S);
printf ("%d" , b/S);
}
- Time Complexity: O(min(|a|, |b|))
- Space Complexity: O(1)
Đây là biến thể của phương pháp brute force với các kiểm tra điều kiện đặc biệt để xử lý nhanh các trường hợp đặc biệt (như a=0, b<0, a chia hết cho b). Tuy nhiên, phần lặp chính vẫn sử dụng vòng lặp for để tìm ước chung lớn nhất, nên độ phức tạp vẫn cao.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên | ||||
|---|---|---|---|---|---|---|---|
| 1 | O(min( | a | , | b | )) | O(1) | Tìm Ước Chung Lớn Nhất (UCLN) bằng Vòng lặp For |
| 2 | O(log(min( | a | , | b | ))) | O(1) | Tìm Ước Chung Lớn Nhất (UCLN) bằng Thuật toán Euclid |
| 3 | O(min( | a | , | b | )) | O(1) | Tối ưu hóa thủ công |
Bài học kinh nghiệm
- Luôn phải kiểm tra trường hợp mẫu số b bằng 0 trước, vì đây là trường hợp không hợp lệ.
- Phân số tối giản phải có mẫu số dương. Nếu mẫu số âm, ta cần đổi dấu cả tử số và mẫu số.
- Nếu sau khi rút gọn, mẫu số là 1, ta chỉ cần in ra tử số vì đó là một số nguyên.
Lỗi thường gặp
- Quên xử lý trường hợp tử số bằng 0 (kết quả là 0).
- Quên xử lý trường hợp mẫu số âm (phải đổi dấu).
- Sử dụng vòng lặp tìm UCLN không hiệu quả dẫn đến TLE với dữ liệu lớn (mặc dù ở đây giới hạn nhỏ).
Bình luận