[已解决]关于欧几里得算法求最大公约数

仙子追随者

def gcd(x, y):
    while y:
        t = x % y
        x = y
        y = t
    return x，
没看明白，请大神帮忙讲解一下

最佳答案

月排行榜 / 总排行榜

lanshj

2020-2-10 14:59:01

def gcd(x, y):#传入两个数
    while y:#直到y=0前都在循环
        t = x % y
        x = y
        y = t#这一段就是欧几里得的算法
    return x #最后返回最大公约数


其实还可以这样
def gcd(x, y):#传入两个数
    while y:#直到y=0前都在循环
        x,y = y,x%y#这一段就是欧几里得的算法
    return x #最后返回最大公约数

跳转到最佳答案楼层

一个账号

 是什么？

Stubborn

一个账号 发表于 2020-2-10 13:02
 是什么？

html里面俗称空格

一个账号

Stubborn 发表于 2020-2-10 14:12
html里面俗称空格

@zltzlt 帮他把 "&nbsp;" 去掉并且用 "<>" 括起来。

lanshj

def gcd(x, y):#传入两个数
    while y:#直到y=0前都在循环
        t = x % y
        x = y
        y = t#这一段就是欧几里得的算法
    return x #最后返回最大公约数


其实还可以这样
def gcd(x, y):#传入两个数
    while y:#直到y=0前都在循环
        x,y = y,x%y#这一段就是欧几里得的算法
    return x #最后返回最大公约数

shangjiecat

欧几里得算法又叫辗转相除法，我给你举个栗子理解一下:
假如 x = 15 , y = 21
则程序x,y会呈现以下变动

	x	y
1	21	15%21=15
2	15	21%15=6
3	6	15%6=3
4	3	0,退出循环

所以最后可求得gcd=3
数学表达式看这个过程:
21 = 1*15 + 6
15 = 2*6 +3
6 = 2*3 +0
这个过程就是辗转相除的过程
反过来看就是
15 + 6 = 21
1*（2*（0+2*3）+3）+ 6 = 21
故3是两数最大公约数
严格的证明辗转相除法要用数学知识，可参考:
https://blog.csdn.net/qq_25847123/article/details/95753295

仙子追随者

lanshj 发表于 2020-2-10 14:59
def gcd(x, y):#传入两个数
    while y:#直到y=0前都在循环
        t = x % y

非常感谢大神，看明白了

仙子追随者

shangjiecat 发表于 2020-2-10 22:40
欧几里得算法又叫辗转相除法，我给你举个栗子理解一下:
假如 x = 15 , y = 21
则程序x,y会呈现以下变动

非常感谢大神，看明白了