在此示例中,您将学习使用两种不同的方法查找两个数字的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。