Python 基础教程

Python 流程控制

Python 函数

Python 数据类型

Python 文件操作

Python 对象和类

Python 日期和时间

Python 高级知识

Python 参考手册

Python程序查找最大公因数(HCF)或最大公约数(GCD)

Python 实例大全

在此示例中,您将学习使用两种不同的方法查找两个数字的GCD:函数和循环以及欧几里得算法

要理解此示例,您应该了解以下Python编程主题:

两个数的最大公因数(H.C.F)或最大公约数(G.C.D)是能完美地将两个给定数相除的最大正整数。例如,H.C.F(12, 14)等于2。

源代码:使用循环

# Python程序查找两个数字的H.C.F

# 定义一个函数
def compute_hcf(x, y):

# 选择较小的数字
    if x > y:
        smaller = y
    else:
        smaller = x
    for i in range(1, smaller+1):
        if((x % i == 0) and (y % i == 0)):
            hcf = i 
    return hcf

num1 = 54 
num2 = 24

print("H.C.F. 是", compute_hcf(num1, num2))

输出结果

H.C.F. 是 6

这里,存储在变量num1和num2中的两个整数被传递给compute hcf()函数。该函数计算H.C.F.这两个数字并返回它。

在这个函数中,我们首先确定两个数字中较小的那个F只能小于或等于最小的数。然后我们使用一个for循环从1到那个数字。

在每次迭代中,我们检查我们的数字是否完美地将两个输入数字相除。如果是这样,我们将这个数字存储为H.C.F.,在循环结束时,我们得到的最大的数字完美地将两个数字相除。

上述方法易于理解和实施,但是效率不高。查找HCF的一种更有效的方法是欧几里得算法。

欧几里得算法

该算法基于以下事实:两个数字的HCF也将它们的差除。

在此算法中,我们将较大者除以较小者,然后取余数。现在,将较小者除以该余数。重复直到剩余为0。

例如,如果我们想求54和24的hcf,我们用54除以24。余数是6。24除以6,余数是0。因此,6是必需的hcf

源代码:使用欧几里得算法

# 函数查找HCF的使用欧几里德算法
def compute_hcf(x, y):
   while(y):
       x, y = y, x % y
   return x

hcf = compute_hcf(300, 400)
print("The HCF is", hcf)

在这里我们循环直到y变为零。该语句x, y = y, x % y在Python中交换值。单击此处以了解有关在Python中交换变量的更多信息。

在每次迭代中,我们同时将y的值放在x中,其余的(x % y)放在y中。当y变为0时,我们得到x的hcf。

Python 实例大全