求最大公约数

ZYM111

def gcd(x, y):
    while y:
        t = x % y
        x = y
        y = t

    return x
   
print(gcd(4, 6))
求这题有别的方法做？作者能不能发点刚入门的人一点一下能反应过来的代码？？？？？？？？？？？？？

新手·ing

1. def gcd(a, b):
   
2. if a < b:
   
3.   a, b = b, a
   
4. 
   
5. while b != 0:
   
6.   temp = a % b
   
7.   a = b
   
8.   b = temp
   
9. 
   
10. return a
    

复制代码

gopythoner

不知道你说的能看懂是个什么概念，我就按照数学的逻辑来写一个很长，但是很通俗易懂的吧
但愿我没有把公约数的概念记错

1. def gcd(x,y):
   
2.     # 公约数不止一个，所以应该是个列表，先定义这个列表为the_nums
   
3.     the_nums = []
   
4.     # 得到x的所有约数,也是个列表，定义为x_nums
   
5.     x_nums = []
   
6.     # 把a当做x的约数，那a肯定满足如下条件，即2<=a<=x,表达方式如下
   
7.     for a in range(2,x+1):
   
8.         # 约数还有一个条件就是整除，表达成这样
   
9.         if x % a == 0:
   
10.             # 好了，通过上述2个条件就得到了所有满足条件的a，也就是x的所有约数，加入的列表中
    
11.             x_nums.append(a)
    
12.     # 同理，可以得到y的约数集合
    
13.     y_nums = []
    
14.     for b in range(2,y+1):
    
15.         if y % b == 0:
    
16.             y_nums.append(b)
    
17.     # 接下来就是公约数了，定义为t，它应该满足同时在x和y的约数集合中，表达如下
    
18.     for t in x_nums:
    
19.         if t in y_nums:
    
20.             # 把所有满足条件的t加入到最开始定义的列表中
    
21.             the_nums.append(t)
    
22.     return the_nums
    
23. 
    
24. # 测试一下：
    
25. print(gcd(6,4))
    
26. # >>>[2]
    
27. print(gcd(20,40))
    
28. # >>>[3]

复制代码

gopythoner

gopythoner 发表于 2017-3-26 01:25
不知道你说的能看懂是个什么概念，我就按照数学的逻辑来写一个很长，但是很通俗易懂的吧
但愿我没有把公约 ...

gcd(20,40)的答案应该是这个，我复制错了
[2, 4, 5, 10, 20]

ZYM111

gopythoner 发表于 2017-3-26 01:25
不知道你说的能看懂是个什么概念，我就按照数学的逻辑来写一个很长，但是很通俗易懂的吧
但愿我没有把公约 ...

谢谢 很好懂

流月飞星

SuMo

那道课后习题的要求是让你根据那个啥公理的方式来求解.......
你把公理看懂了 ,也就知道大概的逻辑了
# def gcd(x,y):
#    if x == 0 or y ==0:
#        return max(x,y)
#    minx = x if x<y else y
#    return gcd(minx,x%y)   
#  
# print gcd(18,9)