Ước chung lớn nhất – Lập trình tìm ƯCLN trong Python và Scratch
Ước chung lớn nhất – Lập trình tìm ƯCLN trong Python và Scratch
Ước chung lớn nhất là gì?
Ước chung lớn nhất (greatest common divisor – GCD) của hai số a và b là số lớn nhất mà cả a và b đều chia hết cho nó
Để tìm ước chung lớn nhất của hai số, ta có thể sử dụng một số phương pháp như:
- Phương pháp Euclid: Sử dụng thuật toán Euclid để lặp lại việc chia lấy dư giữa hai số cho đến khi số thứ hai bằng 0. Khi đó, số thứ nhất chính là ước chung lớn nhất của hai số ban đầu.
- Phân tích thừa số nguyên tố: Phân tích hai số thành các thừa số nguyên tố và lấy các thừa số nguyên tố chung với mũ nhỏ nhất.
Dưới đây là một ví dụ về cách lập trình tính ước chung lớn nhất trong Python và Scratch sử dụng thuật toán Euclid:
Tìm ƯCLN của hai số trong Python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
# Tính ước chung lớn nhất
num1 = int(input("Nhập số thứ nhất: "))
num2 = int(input("Nhập số thứ hai: "))
result = gcd(num1, num2)
print("Ước chung lớn nhất của", num1, "và", num2, "là:", result)
Trong chương trình trên, chúng ta sử dụng hàm gcd(a, b) để tính ước chung lớn nhất của hai số a và b bằng thuật toán Euclid. Trong vòng lặp, chúng ta liên tục thay đổi giá trị của a và b bằng b và a % b cho đến khi b bằng 0. Cuối cùng, giá trị của a chính là ước chung lớn nhất của hai số ban đầu.
Chương trình yêu cầu người dùng nhập vào hai số và sau đó sử dụng hàm gcd để tính ước chung lớn nhất. Cuối cùng, chương trình in ra kết quả.
Tìm ƯCLN của hai số trong Scratch
Đây là một ví dụ về cách lập trình tính ước chung lớn nhất (GCD) trong Scratch:
- Mở trình soạn thảo Scratch và tạo một dự án mới.
- Tạo hai biến “number1” và “number2” để lưu trữ hai số cần tính GCD.
- Tạo một biến “gcd” để lưu trữ kết quả GCD.
- Tạo một khối “when green flag clicked” để bắt đầu chương trình.
- Trong khối này, sử dụng khối “ask and wait” để yêu cầu người dùng nhập số thứ nhất và số thứ hai. Khi người dùng nhập xong, đặt giá trị của biến “number1” và “number2” tương ứng với hai số nhập vào.
- Tiếp theo, tạo một khối “set gcd to number1” để đặt giá trị ban đầu của biến “gcd” là số thứ nhất.
- Tạo một khối “repeat until” để thực hiện thuật toán Euclid cho đến khi số thứ hai bằng 0.
- Trong khối “repeat until”, tạo một biến tạm thời “temp” và đặt giá trị của “temp” bằng số thứ hai.
- Đặt giá trị của số thứ hai bằng phần dư của số thứ nhất chia cho số thứ hai.
- Đặt giá trị của số thứ nhất bằng “temp”.
- Sau khi kết thúc khối “repeat until”, số thứ nhất chính là GCD của hai số ban đầu.
- Sử dụng khối “say” để in ra màn hình giá trị của GCD.
- Kết thúc chương trình.
Lưu ý rằng việc tính GCD trong Scratch phụ thuộc vào cách bạn triển khai thuật toán Euclid. Bạn có thể sử dụng một thuật toán khác nhau tùy thuộc vào sự linh hoạt của Scratch và yêu cầu cụ thể của bạn.
Tìm ước chung lớp nhất của ba số
Để tìm ước chung lớn nhất của ba số, ta có thể sử dụng phương pháp tương tự như tìm ước chung lớn nhất của hai số.
Dưới đây là một ví dụ về cách lập trình tính ước chung lớn nhất của ba số trong Python:
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
def gcd_of_three(a, b, c):
return gcd(gcd(a, b), c)
# Tính ước chung lớn nhất của ba số
num1 = int(input("Nhập số thứ nhất: "))
num2 = int(input("Nhập số thứ hai: "))
num3 = int(input("Nhập số thứ ba: "))
result = gcd_of_three(num1, num2, num3)
print("Ước chung lớn nhất của", num1, ",", num2, "và", num3, "là:", result)
Trong chương trình trên, chúng ta định nghĩa hai hàm gcd và gcd_of_three. Hàm gcd tính ước chung lớn nhất của hai số bằng thuật toán Euclid tương tự như trước đó. Hàm gcd_of_three sử dụng hàm gcd để tính ước chung lớn nhất của ba số bằng cách lần lượt tính ước chung lớn nhất của cặp số đầu tiên, sau đó tính ước chung lớn nhất với số thứ ba.
Chương trình yêu cầu người dùng nhập vào ba số và sau đó sử dụng hàm gcd_of_three để tính ước chung lớn nhất của ba số đó. Cuối cùng, chương trình in ra kết quả.
