首页 › 题库 › GESP编程能力等级认证 › 1.2 最大公约数与最小公倍数

GESP-Python五级 题库

共 12 道题 · 按题型筛选,点「查看答案」核对解析
章节 1.2 最大公约数与最小公倍数 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 1.2 最大公约数与最小公倍数

下面代码实现了欧几里得算法,下面有关说法,错误的是()。

def gcd1(a: int , b : int) -> int :
    return a if b == 0 else gcd1(b , a % b)
def gcd2(a: int , b : int) -> int :
    while b != 0 :
        temp = b
        b = a % b
        a = temp
    return a
A
gcd1() 实现为递归方式。
B
gcd2() 实现为迭代方式。
C
当数值较大时, gcd1() 实现会多次调用自身,需要较多额外的辅助空间。
D
当数值较大时, gcd1() 的实现比 gcd2() 执行效率更高。
答案与解析
正确答案:D
递归会产生函数调用栈开销,迭代无需栈空间,同等数据下迭代gcd2效率更高,D描述错误。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 1.2 最大公约数与最小公倍数

以下代码计算两个数的最大公约数(GCD),横线上应填写( )。

A

b

B

a

C

temp

D

a+b

答案与解析
正确答案:B
这道题暂未补解析。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 1.2 最大公约数与最小公倍数

下列Python代码用于求解两个正整数的最大公约数,相关说法中错误的是( )

A

gcd0()函数的时间复杂度为 O(logN)

B

gcd1()函数的时间复杂度为 O(N)

C

一般说来, gcd0() 的效率高于 gcd1()

D

gcd1() 中的代码 range(small, 0, -1) 应该修改为range(small, 1, -1)

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 1.2 最大公约数与最小公倍数

用以下辗转相除法(欧几里得算法)求gcd(84, 60)的步骤中,第二次调用gcd()函数计算的数是( )。

def gcd(a, b):
	big = max(a, b)
	small = min(a, b)
	if big % small == 0:
		return small
	return gcd(small, big % small)
A
84和60
B
60和24
C
24和12
D
12和0
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 1.2 最大公约数与最小公倍数

下列程序中实现的是( )

def chenadai(x, y):
	return x * y // (x,y的最大公约数)
A
实现了求x,y的最小公约数
B
实现了求x,y的最大公约数
C
实现了求x,y的最小公倍数
D
实现了求x,y的平均值
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 1.2 最大公约数与最小公倍数

欧几里得算法又称作辗转相除算法,下面程序中是这种算法的是( )

A
def gcd(a,b):
	if b == 0:
		return a
	return gcd(b, a % b)
B
def gcd(a, b):
	if a < b:
		a, b = b, a
	while b != 0:
		a,b = b,a%b
	return b
C
def gcd(a,b):
	if b == 0:
		return a
	return gcd(a, a % b)
D
def gcd(a,b):
	if b == 0:
		return a
	return gcd(b, b % a)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
7 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 1.2 最大公约数与最小公倍数

假设函数 gcd() 函数能正确求两个正整数的最大公约数,则下面的 lcm(a ,b) 函数能正确找到两个正整数 a 和 b 的最小公倍数。()

import math
def lcm(a, b):
    if a == 0 or b == 0:
        return 0
    return abs(a) // math.gcd(abs(a), abs(b)) * abs(b)
A
对
B
错
答案与解析
正确答案:对
公式 lcm(a,b) = a*b // gcd(a,b),可正确计算最小公倍数。
题目详情
8 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 1.2 最大公约数与最小公倍数

假设函数 gcd() 函数能正确求两个正整数的最大公约数,则下面的findMusicalPattern(4,6) 函数返回2。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
9 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 1.2 最大公约数与最小公倍数

下面Python代码是用欧几里得算法(辗转相除法)求两个大于0的正整数的最大公约数,a大于b还是小于b都适用。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
10 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 1.2 最大公约数与最小公倍数

假设函数 gcd() 函数能正确求两个正整数的最大公约数,则下面的 lcm() 函数能求相应两数的最小公倍数。 ( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
11 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 1.2 最大公约数与最小公倍数

两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
12 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 1.2 最大公约数与最小公倍数

1997和615用欧几里得算法计算最大公约数的过程如下:

1997/615=3(余152)
615/152=4(余7)
152/7=21(余5)
7/5=1(余2)
5/2=2(余1)
2/1=2(余0)
得出最大公约是是1


A
对
B
错
答案与解析
正确答案:对

欧几里得算法也是辗转相除法,两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数

题目详情