Peteryo01223 发表于 2021-1-7 18:10:22

第17课 函数：求最大公约数（习题）

本帖最后由 Peteryo01223 于 2021-1-7 18:13 编辑

原题目：
编写一个函数，利用欧几里得算法（脑补链接）求最大公约数，例如 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 # a 是一个 0 到 x 之间的整数
        b = range # 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 # a 是一个 0 到 x 之间的整数
TypeError: 'type' object is not subscriptable

再次请教各位高手。

jackz007 发表于 2021-1-7 18:14:12

本帖最后由 jackz007 于 2021-1-7 18:16 编辑

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

Peteryo01223 发表于 2021-1-7 18:19:00

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))

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

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

本帖最后由 昨非 于 2021-1-7 20:48 编辑

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

def gcd(x,y): #定义
    for a in range(int(x)): # a 是一个 0 到 x 之间的整数
      for b in 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 也行吧（有点奇怪，应该是返回相应的a，b值吧）
print(gcd(x,y))#具体运行要看你这个x y是啥

三柒得拾 发表于 2021-1-7 18:46:35

本帖最后由 三柒得拾 于 2021-1-7 18:54 编辑

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

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

jackz007 发表于 2021-1-7 19:47:02

本帖最后由 jackz007 于 2021-1-7 20:29 编辑

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 数能够同时整除枚举出来的某一个数，那么，这个除数自然就是最大公约数了。

       楼主试试这个代码
#coding:gbk

def gcd(x , y): #定义
    if x > y :
      x , y = y , x
    for a in range(x , 1 , -1):
      if x % a == 0 and y % a == 0:
            break
    return a

print(gcd(6,8))
print(gcd(96,80))

Peteryo01223 发表于 2021-1-8 07:21:09

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

       不过， ...

哇 厉害

Peteryo01223 发表于 2021-1-8 07:23:19

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


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

Peteryo01223 发表于 2021-1-8 07:24:42

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

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

jackz007 发表于 2021-1-8 08:50:40

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

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

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

Peteryo01223 发表于 2021-1-8 10:04:45

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

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

jackz007 发表于 2021-1-8 10:30:37

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

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

Peteryo01223 发表于 2021-1-8 10:34:12

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

哦 原来如此 好的
页: [1]
查看完整版本: 第17课 函数：求最大公约数（习题）