Nội dung chính
- Đề bài
- Định nghĩa
- Lời giải
- 1. Tìm USCLN và BSCNN của 2 số nguyên dương trong Python bằng giải thuật Euclid
- 2. Tìm USCLN và BSCNN của 2 số nguyên dương trong Python bằng cách khác
Bài tập Python: Viết chương trình tìm ước số chung lớn nhất [USCLN] và bội số chung nhỏ nhất [BSCNN] của 2 số nguyên dương a và b nhập từ bàn phím.
Định nghĩa
USCLN của 2 số nguyên dương a và b là một số k lớn nhất, sao cho a và b đều chia hết cho k.
BSCNN của 2 số nguyên dương a và b là một số h nhỏ nhất, sao cho h chia hết cho cả a và b.
Lời giải
Một phương pháp đơn giản đề tìm USCLN của a và b là duyệt từ số nhỏ hơn trong 2 số a và b cho đến 1, khi gặp số nào đó mà cả a và b đều chia hết cho nó thì đó chính là USCLN của a và b. Tuy vậy phương pháp này chưa phải là hiệu quả nhất.
Vào thế kỷ 3 TCN, nhà toán học Euclid [phiên âm tiếng Việt là Ơ-clit] đã phát minh ra một giải thuật tìm USCLN của hai số nguyên dương rất hiệu quả được gọi là giải thuật Euclid. Cụ thể về ý tưởng của bài toán, giả sử a lớn hơn b, khi đó việc tính UCSLN của a và b sẽ được đưa về bài toán tính USCLN của a mod b và b vì USCLN[a, b] = USCLN[a mod b, b].
Khi đã tìm được USCLN thì việc tìm BSCNN của hai số nguyên dương a và b khá đơn giản. Khi đó BSCNN[a, b] = [a * b] / UCSLN[a, b].
1. Tìm USCLN và BSCNN của 2 số nguyên dương trong Python bằng giải thuật Euclid
Ví dụ dưới đây sử dụng giải thuật Euclid để giải quyết bài toán tìm ước số chung lớn nhất [USCLN] và bội số chung nhỏ nhất [BSCNN] của hai số nguyên dương a và b bằng cách sử dụng giải thuật Euclid.
"""
* Tìm ước số chung lớn nhất [USCLN]
*
* @param a: số nguyên dương
* @param b: số nguyên dương
* @return USCLN của a và b
"""
def uscln[a, b]:
if [b == 0]:
return a;
return uscln[b, a % b];
"""
* Tìm bội số chung nhỏ nhất [BSCNN]
*
* @param a: số nguyên dương
* @param b: số nguyên dương
* @return BSCNN của a và b
"""
def bscnn[a, b]:
return int[[a * b] / uscln[a, b]];
a = int[input["Nhập số nguyên dương a = "]];
b = int[input["Nhập số nguyên dương b = "]];
#tính USCLN của a và b
print["Ước số chung lớn nhất của", a, "và", b, "là:", uscln[a, b]];
#tính BSCNN của a và b
print["Bội số chung nhỏ nhất của", a, "và", b, "là:", bscnn[a, b]];
Kết quả:
Nhập số nguyên dương a = 15 Nhập số nguyên dương b = 20 Ước số chung lớn nhất của 15 và 20 là: 5 Bội số chung nhỏ nhất của 15 và 20 là: 60
2. Tìm USCLN và BSCNN của 2 số nguyên dương trong Python bằng cách khác
"""
* Tìm ước số chung lớn nhất [USCLN]
*
* @param a: số nguyên dương
* @param b: số nguyên dương
* @return USCLN của a và b
"""
def uscln[a, b]:
temp1 = a;
temp2 = b;
while [temp1 != temp2]:
if [temp1 > temp2]:
temp1 -= temp2;
else:
temp2 -= temp1;
uscln = temp1;
return uscln;
"""
* Tìm bội số chung nhỏ nhất [BSCNN]
*
* @param a: số nguyên dương
* @param b: số nguyên dương
* @return BSCNN của a và b
"""
def bscnn[a, b]:
return int[[a * b] / uscln[a, b]];
a = int[input["Nhập số nguyên dương a = "]];
b = int[input["Nhập số nguyên dương b = "]];
#tính USCLN của a và b
print["Ước số chung lớn nhất của", a, "và", b, "là:", uscln[a, b]];
#tính BSCNN của a và b
print["Bội số chung nhỏ nhất của", a, "và", b, "là:", bscnn[a, b]];
Kết quả:
Nhập số nguyên dương a = 15 Nhập số nguyên dương b = 20 Ước số chung lớn nhất của 15 và 20 là: 5 Bội số chung nhỏ nhất của 15 và 20 là: 60
Giải thích hoạt động của chương trình trên: Trong chương trình này, tôi nhập vào hai số 15 và 20 thì trình biên dịch sẽ thực thi hàm uscln[] với các bước như sau:
- Gán giá trị biến temp1 = 15 và temp2 = 20.
- Kiểm tra điều kiện bên trong while: Vì 15 != 20 nên sẽ thực thi lệnh bên trong while. Lúc này 15 < 20 nên lệnh bên trong else sẽ được thực thi và lúc này biến temp2 = 5.
- Quay lại bước 3, kiểm tra điều kiện bên trong while: Vì 15 != 5 nên sẽ thực thi lệnh bên trong while. Lúc này 15 > 5 nên lệnh bên trong if sẽ được thực thi và lúc này biến temp1 = 10.
- Quay lại bước 3, kiểm tra điều kiện bên trong while: Vì 10 != 5 nên sẽ thực thi lệnh bên trong while. Lúc này 10 > 5 nên lệnh bên trong if sẽ được thực thi và lúc này biến temp1 = 5.
- Quay lại bước 3, kiểm tra điều kiện bên trong while: Vì 5 == 5 nên sẽ không thực thi lệnh bên trong while. Vòng lặp kết thúc, trả về giá trị uscln = 5.