Viết chương trình Python để tìm GCD của hai số bằng Vòng lặp While, Hàm và Đệ quy. Để tìm GCD hoặc HCF, chúng ta phải chuyển ít nhất một giá trị khác 0
Ước số chung lớn nhất còn được gọi là Thừa số chung cao nhất [HCF], hoặc Thừa số chung lớn nhất [GCF], hoặc Ước số chung cao nhất [HCD], hoặc Số đo chung lớn nhất [GCM]
Trong Toán học, Ước chung lớn nhất của hai hay nhiều số nguyên là số nguyên dương lớn nhất chia hết các giá trị nguyên đã cho mà không lấy phần dư. Ví dụ: giá trị GCD của số nguyên 8 và 12 là 4 vì cả 8 và 12 đều chia hết cho 1, 2 và 4 [số dư là 0] và số nguyên dương lớn nhất trong số đó là 4
Chương trình Python để tìm GCD của hai số Ví dụ 1
Chương trình python này cho phép người dùng nhập hai giá trị nguyên dương. Tiếp theo, chúng tôi đang sử dụng vòng lặp While để hạn chế giá trị i không vượt quá các giá trị do người dùng chỉ định
Trong vòng lặp While, chúng tôi đã sử dụng Câu lệnh If để kiểm tra xem a%i và %i có phần dư bằng 0 hay không. Nếu đúng, Hệ số chung cao nhất = Tôi bỏ qua giá trị đó
a = float[input[" Please Enter the First Value a: "]]
b = float[input[" Please Enter the Second Value b: "]]
i = 1
while[i val2]:
val1 = val1 - val2
else:
val2 = val2 - val1
return val1
a = float[input[" Please Enter the First Value a: "]]
b = float[input[" Please Enter the Second Value b: "]]
result = findresult[a, b]
print["\n HCF of {0} and {1} = {2}".format[a, b, result]]GCD của hai số sử dụng đệ quy
Nó cho phép người dùng nhập hai giá trị số nguyên dương và tính Ước chung lớn nhất của hai giá trị đó bằng cách gọi hàm findGreatestCD theo cách đệ quy
Trong chương trình trước, chúng ta đã phát triển một chương trình Python để tìm lcm [Bội chung nhỏ nhất hoặc bội số chung nhỏ nhất] của hai số. Bây giờ trong bài đăng này, chúng tôi sẽ phát triển chương trình HCF hoặc GCD bằng Python để tìm HCF hoặc GCD của hai số
Thừa số chung lớn nhất [HCF] của hai hay nhiều số là số lớn nhất chia chính xác từng số đó. Số đo chung lớn nhất [GCM] và Ước số chung lớn nhất [GCD] là các thuật ngữ khác được sử dụng để chỉ HCF
Thí dụ. HCF của 60 và 75 = 15 vì 15 là số cao nhất chia hết cho cả 60 và 75
GCD trong Python
Đây là một phương pháp bình thường để tìm HCF hoặc GCD của hai số trong python. Chúng tôi sẽ lấy hai số trong khi khai báo các biến. Chương trình Python tìm GCD của hai số bằng vòng lặp for và câu lệnh if-else
# Python program to find GCD of two numbers
# take inputs
x = int[input['Enter First Number: ']]
y = int[input['Enter Second Number: ']]
# choose the smaller number
if x > y:
smaller = y
else:
smaller = x
# find gcd of the number
for i in range [1,smaller+1]:
if[[x % i == 0] and [y % i == 0]]:
gcd = i
# display result
print['The GCD of',x,'and',y,'is',gcd]Đầu ra cho giá trị đầu vào khác nhau. -
Nhập số đầu tiên. 2
Nhập số thứ hai. 10
GCD của 2 và 10 là 2
Nhập số đầu tiên. 8
Nhập số thứ hai. 100
GCD của 8 và 100 là 4
Trong mỗi lần lặp lại, chúng tôi kiểm tra xem số của chúng tôi có chia hoàn toàn cho cả hai số đầu vào không. Nếu vậy, chúng tôi lưu số dưới dạng GCD. Khi hoàn thành vòng lặp, chúng tôi kết thúc với số lớn nhất chia hoàn hảo cả hai số
Ước chung lớn nhất Chương trình Python
Trong chương trình trước, tìm GCD hoặc HCF của hai số bằng vòng lặp for nhưng trong chương trình này, tìm giai thừa của hai số bằng vòng lặp while
________số 8đầu ra. -
Nhập số đầu tiên. 45
Nhập số thứ hai. 16
GCD của 45 và 16 là 1
Chương trình HCF hoặc GCD trong Python bằng Hàm
Chúng ta cũng có thể nhờ sự trợ giúp của hàm tìm HCF hoặc GCD của hai số trong python. Hàm là một khối mã thực hiện một tác vụ cụ thể
# Python program to find GCD of two numbers using function
def compute_gcd[x, y]: #user-defined function
# choose the smaller number
if x > y:
smaller = y
else:
smaller = x
for i in range[1, smaller+1]:
if[[x % i == 0] and [y % i == 0]]:
gcd = i
return gcd
# take inputs
num1 = int[input['Enter First Number: ']]
num2 = int[input['Enter Second Number: ']]
# calling function & display result
print['The GCD of',num1,'and',num2,'is',compute_gcd[num1, num2]]đầu ra. -
Nhập số đầu tiên. 75
Nhập số thứ hai. 80
GCD của 75 và 80 là 5
Chương trình Python để tìm GCD của hai số bằng cách sử dụng đệ quy
Chúng tôi cũng có thể sử dụng kỹ thuật đệ quy để tìm GCD hoặc HCF của hai số. Một kỹ thuật xác định phương thức/hàm chứa lệnh gọi đến chính nó được gọi là đệ quy. Hàm/phương thức đệ quy cho phép chúng ta chia vấn đề phức tạp thành các trường hợp đơn giản giống hệt nhau có thể xử lý dễ dàng. Đây cũng là một kỹ thuật lập trình máy tính nổi tiếng. phân chia và chinh phục
Please Enter the First Value a: 8
Please Enter the Second Value b: 12
HCF of 8.0 and 12.0 = 4đầu ra. -
Nhập số đầu tiên. 50
Nhập số thứ hai. 1200
GCD của 50 và 1200 là 50
HCF trong Python sử dụng Thuật toán Euclide
Phương pháp này hiệu quả hơn nhiều để tìm GCD của hai số trong python. Thuật toán này dựa trên thực tế là GCD của hai số cũng chia hiệu của chúng. Chúng tôi chia lớn hơn cho nhỏ hơn và lấy phần còn lại. Sau đó, chia nhỏ hơn cho phần còn lại này. Lặp lại cho đến khi phần còn lại là 0
Please Enter the First Value a: 8
Please Enter the Second Value b: 12
HCF of 8.0 and 12.0 = 4đầu ra. -
Nhập số đầu tiên. 15
Nhập số thứ hai. 145
GCD của 15 và 145 là 5
Câu lệnh này x, y = y, x%y thực hiện hoán đổi các giá trị. Nhấp vào đây để tìm hiểu thêm về Cách hoán đổi biến trong python