[已解决]第17课 函数：求最大公约数（习题）

Peteryo01223

原题目：
编写一个函数，利用欧几里得算法（脑补链接）求最大公约数，例如 gcd(x, y) 返回值为参数 x 和参数 y 的最大公约数。

小甲鱼的标准答案：
def gcd(x, y):
    while y:
        t = x % y
        x = y
        y = t

    return x
   
我的问题：如果不用欧几里得算法，我这个思路行么？为何报错了呀？

def gcd(x,y): #定义
        a = range[0:int(x)] # a 是一个 0 到 x 之间的整数
        b = range[0:int(y)] # b 是一个 0 到 x 之间的整数
        if a == b and x%a == 0 and y%b == 0: # a和b相等的时候，且 a 和 b 分别能被 x 和 y 整除
                return x # 返回 x，或者返回 y 也行吧
print (gcd(6,8))

报错内容：
Traceback (most recent call last):
  File "C:/Users/user/Desktop/20210107c.py", line 6, in <module>
    print (gcd(6,8))
  File "C:/Users/user/Desktop/20210107c.py", line 2, in gcd
    a = range[0:int(x)] # a 是一个 0 到 x 之间的整数
TypeError: 'type' object is not subscriptable

再次请教各位高手。

最佳答案

月排行榜 / 总排行榜

jackz007

2021-1-7 19:47:02

Peteryo01223 发表于 2021-1-7 18:19
def gcd(x,y): #定义
    a = range(int(x)) # a 是一个 0 到 x 之间的整数
    b = range(int(y)) # b ...

       你这个代码既没有循环，又没有对 x 的处理，最后却要返回 x，怎么能够做到？

       不过，我似乎明白了你的意思，就是通过枚举的方法，从 x，y 中较小的那一个起，从大往小逐一枚举，到 1 终止，如果 x、y 数能够同时整除枚举出来的某一个数，那么，这个除数自然就是最大公约数了。

       楼主试试这个代码

1. #coding:gbk
   
2. 
   
3. def gcd(x , y): #定义
   
4.     if x > y :
   
5.         x , y = y , x
   
6.     for a in range(x , 1 , -1):
   
7.         if x % a == 0 and y % a == 0:
   
8.             break
   
9.     return a
   
10. 
    
11. print(gcd(6,8))
    
12. print(gcd(96,80))

复制代码

跳转到最佳答案楼层

jackz007

        range() 是函数，不可以写成 range[]
        你为什么总是充满怀疑，不喜欢站在巨人的肩膀上，难道你吃的面粉不可以是农民伯伯种出来的，一定要亲自去种才能放心？？？

Peteryo01223

jackz007 发表于 2021-1-7 18:14
range() 是函数，不可以写成 range[]
        你为什么总是充满怀疑，不喜欢站在巨人的肩膀上，难 ...

def gcd(x,y): #定义
    a = range(int(x)) # a 是一个 0 到 x 之间的整数
    b = range(int(y)) # b 是一个 0 到 x 之间的整数
    if a == b and x%a == 0 and y%b == 0: # a和b相等的时候，且 a 和 b 分别能被 x 和 y 整除
        return x # 返回 x，或者返回 y 也行吧
    print(gcd(x,y))

改为了（），不过还是报错~

昨非

Peteryo01223 发表于 2021-1-7 18:19
def gcd(x,y): #定义
    a = range(int(x)) # a 是一个 0 到 x 之间的整数
    b = range(int(y)) # b ...

1. def gcd(x,y): #定义
   
2.     for a in range(int(x)): # a 是一个 0 到 x 之间的整数
   
3.         for b in range(int(y)): # b 是一个 0 到 x 之间的整数
   
4.             if a == b and x%a == 0 and y%b == 0: # a和b相等的时候，且 a 和 b 分别能被 x 和 y 整除
   
5.                 return x # 返回 x，或者返回 y 也行吧  （有点奇怪，应该是返回相应的a，b值吧）
   
6. print(gcd(x,y))  #具体运行要看你这个x y是啥

复制代码

三柒得拾

Peteryo01223 发表于 2021-1-7 18:19
def gcd(x,y): #定义
    a = range(int(x)) # a 是一个 0 到 x 之间的整数
    b = range(int(y)) # b ...

楼主，这报错应该是这个SyntaxError:&#160;invalid&#160;character&#160;in&#160;identifier
出现这个报错一般是在注释#之间混入了中文输入法模式下的空格，检查下就好了。print后面的也是这样检查

jackz007

Peteryo01223 发表于 2021-1-7 18:19
def gcd(x,y): #定义
    a = range(int(x)) # a 是一个 0 到 x 之间的整数
    b = range(int(y)) # b ...

       你这个代码既没有循环，又没有对 x 的处理，最后却要返回 x，怎么能够做到？

       不过，我似乎明白了你的意思，就是通过枚举的方法，从 x，y 中较小的那一个起，从大往小逐一枚举，到 1 终止，如果 x、y 数能够同时整除枚举出来的某一个数，那么，这个除数自然就是最大公约数了。

       楼主试试这个代码

1. #coding:gbk
   
2. 
   
3. def gcd(x , y): #定义
   
4.     if x > y :
   
5.         x , y = y , x
   
6.     for a in range(x , 1 , -1):
   
7.         if x % a == 0 and y % a == 0:
   
8.             break
   
9.     return a
   
10. 
    
11. print(gcd(6,8))
    
12. print(gcd(96,80))

复制代码

Peteryo01223

jackz007 发表于 2021-1-7 19:47
你这个代码既没有循环，又没有对 x 的处理，最后却要返回 x，怎么能够做到？

       不过， ...

哇 厉害

Peteryo01223

昨非 发表于 2021-1-7 18:30

你的我刚才试了试，也报错了。。。

Peteryo01223

三柒得拾 发表于 2021-1-7 18:46
楼主，这报错应该是这个SyntaxError:&#160;invalid&#160;character&#160;in&#160;identifier
出现这个 ...

哦。我目前还解读不了报错内容。

jackz007

Peteryo01223 发表于 2021-1-8 07:21
哇 厉害

       完全照你的思路版本，就是运行效率有点低。

1. #coding:gbk
   
2. 
   
3. def gcd(x,y): #定义
   
4.     for a in range(x , 1 , - 1):                     # a 是一个 0 到 x 之间的整数
   
5.         for b in range(y , 1 , - 1):                 # b 是一个 0 到 x 之间的整数
   
6.             if a == b and x % a == 0 and y % b == 0: # a 和 b相等的时候，且 a 和 b 分别能被 x 和 y 整除
   
7.                 return a
   
8. print(gcd(80,96))

复制代码

Peteryo01223

jackz007 发表于 2021-1-8 08:50
完全照你的思路版本，就是运行效率有点低。

嗯嗯。看来我写的 range(int(x)), 或者 range(1 , x), 在Python中，都是不合法的。 必须写 range(x,1,-1) 才对。

jackz007

Peteryo01223 发表于 2021-1-8 10:04
嗯嗯。看来我写的 range(int(x)), 或者 range(1 , x), 在Python中，都是不合法的。 必须写 range(x,1,-1) ...

        因为是最大公约数，为了确保最大，因子必须从大往小枚举。

Peteryo01223

jackz007 发表于 2021-1-8 10:30
因为是最大公约数，为了确保最大，因子必须从大往小枚举。

哦 原来如此 好的