递归实现——最大公约数

Description

输入Num组正整数M和N，输出它们的最大公约数X。要求使用递归方式实现。提示：input()语句是以str的形式读取一整行的的数据，所以需要在input()语句读取一整行的输入后，先用split()对读取的字符串进行切割，然后再做进一步的处理转化成int类型。

Input
首先输入一个正整数num，代表接下来将输入num组测试数据。然后接下来将分别输入每一组的两个正整数M和N。（M>0,N>0）

Output
分别输出每组正整数的最大公约数X。

Sample Input 1	Sample Output 1
4
45 15	15
60 20	20
70 80	10
100 99	1

coding：

def greatest_common_divisor(x,y): if x >= y: if x % y == 0: return y else: return greatest_common_divisor(x-y,y) else: if y % x == 0: return x else: return greatest_common_divisor(y-x,x)n = input()for i in range(int(n)): temp = list(map(int, input().split(' '))) print(greatest_common_divisor(temp[0], temp[1]))

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18