所属作业: hw7
算法: 递归
1
2
3
4
| def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
|
1
2
3
4
5
6
7
| def gcd(a, b):
# 如果b为0，返回a
if b == 0:
return a
# 否则，递归调用gcd函数，用b和a对b的余数作为参数
else:
return gcd(b, a % b)
|
看看下面这个 Wrong Answer 的写法哪里出错了？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| def yueshu(x, y):
if x>y or x==y:
if x%y==0:
yue=y
else:
return yueshu(x,x%y)
return yue
elif y>x:
if y%x==0:
yue=x
else:
return yueshu(y,y%x)
return yue
m,n=map(int,input().split())
yue=0
print(yueshu(m, n))
|
用枚举的方法，会 Time Limit Exceeded：
1
2
3
4
5
6
7
| n,m=map(int,input().split())
for i in range(n): #对于n的取值范围从0到n-1，下同
for j in range(m):
if n % (i+1) ==0 and m % (j+1) ==0 and (i+1)==(j+1) : #判断条件
gcd = i+1 #将最大公约数保存在变量gcd中
print(gcd)
|