2020-04
11

辗转相除法

By xrspook @ 20:51:51 归类于: 扮IT

题目是这样的

Exercise 5: The greatest common divisor (GCD) of a and b is the largest number that divides both of them with no remainder. One way to find the GCD of two numbers is based on the observation that if r is the remainder when a is divided by b, then gcd(a, b) = gcd(b, r). As a base case, we can use gcd(a, 0) = a. Write a function called gcd that takes parameters a and b and returns their greatest common divisor.

为什么从前我学最大公约数的时候就不是用这个方法呢?如果数字很大,这个应该很快吧,以前我们用的是质因数分解法,我一直没用过其它方法。这里用的是辗转相除法,也叫欧几里德算法,估计在外国这是基础算法,否则Excel也不会有GCD(A, B)这个求最大公约数的公式……

深感自己的无知……

1
2
3
4
5
6
7
8
9
10
11
12
def gcd(a, b): # 可以在Excel里用GCD(a, b)函数测试结果
    if b == 0:
        return a 
    else:
        return gcd(b, a%b) # b不断取代a,b不断被a%b取代
a = int(input('a is '))
b = int(input('b is '))
print(gcd(a, b))
# result
# a is 1024
# b is 480
# 32
© 2004 - 2024 我的天 | Theme by xrspook | Power by WordPress