Cho hai số nguyên Num1 và Num2 làm đầu vào. Các số có thể biểu diễn dưới dạng phân số Num1/Num2. Mục tiêu là rút gọn phân số này về dạng tối giản.
Sử dụng GCD để tìm ước chung lớn nhất
Tính ước chung lớn nhất (GCD) của hai số.
Chia cả hai số cho GCD đó.
Gán cả hai biến bằng thương sau chia.
Phân số tối giản sẽ là Num1/Num2.
Ví dụ
Đầu vào - Num1 = 22, Num2 = 10
Đầu ra - Num1 = 11, Num2 = 5
Phân số tối giản: 11/5
Giải thích - GCD của 22 và 10 là 2.
22/2 = 11 và 10/2 = 5
Phân số tối giản là 11/5
Đầu vào - Num1 = 36, Num2 = 40
Đầu ra - Num1 = 9, Num2 = 10
Phân số tối giản: 9/10
Giải thích - GCD của 36 và 40 là 4.
40/4 = 10 và 36/4 = 9
Phân số tối giản là 9/10
Phương pháp sử dụng trong chương trình dưới đây
Tính GCD của hai số đầu vào bằng đệ quy. Chia cả hai cho GCD lấy thương. Các thương này tạo thành phân số tối giản.
Nhập biến Num1, Num2.
Hàm findGCD(int a, int b) trả về GCD của a, b.
Nếu b = 0 trả về a, ngược lại trả về findGCD(b, a%b).
Hàm lowestFraction(int num1, int num2) in phân số tối giản.
Biến denom lưu GCD.
num1 /= denom, num2 /= denom.
In num1, num2 và phân số num1/num2.
Ví dụ mã
#include <bits/stdc++.h> using namespace std; int findGCD(int a, int b) { if (b == 0) return a; return findGCD(b, a % b); } void lowestFraction(int num1, int num2){ int denom; denom = findGCD(num1,num2); num1/=denom; num2/=denom; cout<< "Num1 = " << num1<<endl; cout<< "Num2 = " << num2<<endl; cout<< "Phân số tối giản : "<<num1<<"/"<<num2; } int main(){ int Num1 = 14; int Num2 = 8; lowestFraction(Num1,Num2); return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Num1 = 7 Num2 = 4 Phân số tối giản : 7/4