出于教育目的,我试图构建一种有效的算法来查找最小公倍数。我已经有了二次方且缓慢的实现方式。我正在尝试建立一个新的。我的新实现使用涉及最大公除数(GCD)和最小公倍数(LCM)的数学属性。
基本上:对于任意两个正整数a和b,
LCM(a, b) * GCD(a, b) = a * b
我正在为此使用Python 3。
对于GCD,我有一个非常有效的实现(它使用另一个数学属性,但是谈论这一点毫无意义):
def euclidean_gcd(a,b):
if b == 0:
return a
else:
a_prime = a%b
return euclidean_gcd(b,a_prime)
我对LCM的实现是:
def lcm_fast(a,b):
return (int((a*b)/(euclidean_gcd(a,b))))
但是,当我打电话时:
lcm_fast(1023473145,226553150)
我得到的输出:
46374212988031352
正确答案应该是一个接近的数字:
46374212988031350
我是初学者(应用数学专业的第二年),为什么会这样?
我不确定是否可以理解整数溢出的概念,但是根据我对上面所做的一些研究的了解,Python中没有整数溢出。
我进行了压力测试,并试图在一个更容易理解的案例中发现此错误。但是,问题似乎只在数量很大的情况下才会发生。在下面您可以检查一下我的压力测试:
import random
#defina a fronteira máxima dos testes randômicos
print ("insira um número para ser o final do intervalo de testes aleatórios")
bound_right = int(input())
#versão lenta, ou naive
def check_elem_in_list(list_1,list_2):
for element in list_1:
if element in list_2:
return element
else:
return False
#nested loops, vai ter comportamento quadrático
def lcm_slow(num_1,num_2):
list_of_num_1_prod = []
list_of_num_2_prod = []
max_nums = max(num_1,num_2)
end_range = max_nums +1
for i in range(1, end_range):
list_of_num_1_prod.append(i*num_1)
list_of_num_2_prod.append(i*num_2)
if check_elem_in_list(list_of_num_1_prod,list_of_num_2_prod) != False:
return (check_elem_in_list(list_of_num_1_prod,list_of_num_2_prod))
def euclidean_gcd(a,b):
if b == 0:
return a
else:
a_prime = a%b
return euclidean_gcd(b,a_prime)
def lcm_fast(a,b):
return (int((a*b)/(euclidean_gcd(a,b))))
# está dando pau com os inputs 1023473145, 226553150
# vou fazer stress testing
#primeiro, fazer função para gerar testes
a_in = random.randint(1,bound_right)
b_in = random.randint(1,bound_right)
while (lcm_slow(a_in,b_in)==lcm_fast(a_in,b_in)):
a_in = random.randint(1,bound_right)
b_in = random.randint(1,bound_right)
print (a_in,b_in,"OK",lcm_fast(a_in,b_in),lcm_slow(a_in,b_in))
if (lcm_slow(a_in,b_in)!=lcm_fast(a_in,b_in)):
print (a_in, b_in,"OPS",lcm_fast(a_in,b_in),lcm_slow(a_in,b_in))
break
#
在对原始问题进行一些评论/回答后进行编辑
在此问题内部,出现了一个新问题。
我正在为此构建平台。我的解决方案是正确的。在Blender发表评论后。我做到了(这是我最初的解决方案):
def lcm_fast(a,b):
a = ((a*b)/(euclidean_gcd(a,b)))
return a
问题是我在平台的测试用例上收到此消息失败:
Failed case #1/42: Cannot check answer. Perhaps output format is wrong.
Input: 18 35 Your output: 630.0 Correct output: 630 (Time used: 0.01/5.00, memory used: 9613312/536870912.)
那很好笑。如果我避免使用
int()
近似,则该代码适用于大数。但是,如果没有从float
到int
的转换,则无法提供所需格式的答案。 最佳答案
您正在使用int()
将除法的结果转换回整数,因为“常规”整数除法会产生浮点数。 CPython的浮点数具有固定的精度,因此来回转换将导致丢失足够大数量的信息。
避免损失精度,并使用//
执行地板除法,该方法将返回整数:
def lcm_fast(a,b):
return (a * b) // euclidean_gcd(a,b)