重拾算法

最近一些事比较打击信心，所以需要充实一下。。好多东西忘记了的话，再看一遍，重新整理一遍。

最大公约数

输入两个数，输出这两个数的最大公约数

例：
input:  319，377
output: 29

实现思路：辗转相除法

若 r 是 a ÷ b 的余数，且r不为0， 则
gcd(a,b) = gcd(b,r)

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
def gcd(a, b):
    if a < b:
        tmp = a
        a = b
        b = tmp
    while(b != 0):
        r = a % b
        a = b
        b = r
    return a


print(gcd(319, 377))

输出

python GCD.py
29