Hàm HCF trong Python

Tìm HCF hoặc gcd của hai số trong python;

HCF (Thừa số chung cao nhất) của hai số là số cao nhất trong số tất cả các ước chung của các số đã cho. Ví dụ: HCF của 12 và 36 là 12 vì 12 là ước chung cao nhất của 12 và 36

Các chương trình tìm HCF hoặc GCD

Hãy sử dụng thuật toán sau để viết chương trình tìm gcd hoặc hcf của hai số trong python

• HCF của hai số trong Python bằng vòng lặp While
• Chương trình Python để tìm HCF của hai số bằng vòng lặp For
• Chương trình Python để tính toán HCF (GCD) bằng hàm đệ quy

HCF của hai số trong Python bằng vòng lặp While

Làm theo các bước dưới đây và viết chương trình tìm hcf hoặc gcd của hai số bằng hàm đệ quy trong python

Ví 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 toàn 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

# Python program to find GCD of two numbers

# take inputs
x = int(input('Enter First Number: '))
y = int(input('Enter Second Number: '))

# find gcd of the numbers
i = 1
while(i <= x and i <= y):
    if(x % i == 0 and y % i == 0):
        gcd = i
    i += 1

# display result
print('The GCD of',x,'and',y,'is',gcd)

đầ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

# Python program to find GCD of two numbers using recursion

def recur_gcd(x, y):  # user-defined function
    if(y == 0):
        return x
    else:
        return recur_gcd(y, x%y)

# 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',recur_gcd(num1, num2))

đầ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

# Python program to find GCD of two numbers 
# using Euclidean Algorithm

def compute_gcd(x, y):  # user-defined function
    while(y):
        x, y = y, x%y
    return x

# 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. 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

Nếu bạn thích bài đăng này, hãy chia sẻ nó với bạn bè của bạn. Bạn có muốn chia sẻ thêm thông tin về chủ đề đã thảo luận ở trên hay bạn có thấy điều gì không đúng không? . Cảm ơn bạn

Làm cách nào để tính HCF bằng Python?

HCF có nghĩa là gì trong Python?

gcd có phải là một hàm trong Python không?

Làm thế nào để tính HCF?