Python 基础综合练习 1

第 1 关：最小公倍数算法

编写一个能计算给定的所有正整数的最小公倍数的小程序。

相关知识

为了完成本关任务，你需要掌握：

1. 如何求任意两个正整数的最大公约数；

2. 如何求任意两个正整数的最小公倍数。

3. 如何求任意两个正整数的最大公约数

• 最大公约数(GCD, Greatest Common Divisor)，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。

比如数 12 和数 18 的最大公约数是 6，因为 12 的约数有 1、2、3、4、6、12，而 18 的约数有 1、2、3、6、9、18，通过比较，显然 6 是数 12 和数 18 的最大公约数。

• 通过上述过程，显然我们可以通过枚举这两个数的所有约数，考虑这两个数共有的约数，然后选择最大的就是这两个数的最大公约数。因为一个数的约数必然是不大于该数的，所以我们可以通过枚举不超过这两个数中的最大者的正整数，来达到上述效果，具体代码如下述所示：

• def gcd_1(x, y):

  ed = max(x, y)+1

  divisor = 1

  for i in range(2, ed):

  if x % i == 0 and y % i == 0:

  divisor = i

  return divisor

其实在古代就有能求解出最大公约数的算法了，《九章算术》是中国古代的数学专著，其中的“更相减损术”就可以用来求两个数的最大公约数，原文是：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”大致所描述的算法步骤是：

1. 任意给定两个正整数；判断它们是否都是偶数。若是，则用 2 约简；若不是则执行第二步；

2. 以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止；

3. 第一步中约掉的若干个 2 与第二步中最后得到的差（或减数）的乘积就是所求的最大公约数。

• 实际编程中，我们可以省略第一步，这样第二步最后得到的差（或减数）就是这两个数的最大公约数，其具体实现如下述代码所示：

def gcd_2(x, y):

while True:

if x < y:

x, y = y, x

elif x == y:

return x

x -= y

• 尽管前面已经介绍了两种求最大公约数的方法，但实际生活中，我们更倾向于使用辗转相除法，来求解任意两个正整数的最大公约数，以求解 30 和 12 的最大公约数为例，按 gcd_2 代码，其过程为：

30 - 12 = 18 -> 18 - 12 = 6 -> 12 - 6 = 6

最后因为减数和差相等，即 6 - 6 = 0，故 6 就是 30 和 12 的最大公约数，仔细观察上述过程，我们可以发现第一步和第二步实际上就是被减数 30 减了 2 次 12，然后在第三步，用上次计算的余数 6 继续与 12 进行比较。显然，我们可以通过整数求余运算，直接一步求得 30 和 12 的余数 6，此时余数绝对是比除数小的，那么则将除数代替被除数的位置，余数代替除数的位置，然后重复上述过程，直至余数为 0，那么此时的除数就是原来两个数的最大公约数了。上述过程用递归方式实现的话，代码是非常简短的，具体代码如下：

def gcd(x, y):

return x if y == 0 else gcd(y, x%y)

最后，推荐大家也去实现下求解任意两正整数的最大公约数的非递归版本。

如何求任意两个正整数的最小公倍数

• 几个数共有的倍数叫做这几个数的公倍数，其中除 0 以外最小的一个公倍数，叫做这几个数的最小公倍数（LCM，Least Common Multiple）。

• 如 3 和 7 的最小公倍数是 21，因为不存在一个比 21 还小的正整数，既是 3 的倍数，也是 7 的倍数。

• 显然对任意两个正整数 a 和 b，a*b 必是他们的公倍数。假设 g 为 a 和 b 的最大公约数，那么 a、b 可以分别写成一个正整数与他们最大公约数的乘积的形式，即 a = p * g，b = q * g。那么显然 c = p * q * g，是 a 和 b 的一个公倍数，而且是最小公倍数。因为 p 和 q 必定不共有大于 1 的公约数，所以若减小 p、q、g 这三个任意一个数的话，都不能使其乘积还是 a 和 b 的倍数。

编程要求：

计算并输出给定的所有正整数的最小公倍数，参数 x 为整数列表。测试输入：

1,2,3,4,5

预期输出：

60

测试输入：

15,25,20

预期输出：

300

上代码：

//如果注释理解有误，请大佬们多多评论指教！！