我正在尝试编写代码,以解决在线上看到的减少分数的问题。对于n和d较小的值,我得到了答案,但是,当尝试求解n和d的较大值时,for循环花费的时间太长,以至于我得到一个内存错误(在等待代码运行约一个小时之后) )。
“通过按大小的升序列出d≤1,000,000的约简分数集...”
有没有办法在不使用冗长的for循环的情况下检查所有可能的分数以获取较大的n?
fraction_list = []
for d in range(1000000):
for n in range(1000000):
if n<d and n/d ==0 :
frac = float(n) / float(d)
#print(frac)
fraction_list.append(frac)
index_num = (fraction_list.index(float(2.0/7.0)))
sorted(fraction_list, key=float)
print(fraction_list[index_num])
print("the fraction which is to the left is" + fraction_list[index_num -1])
我猜可能有比我在这里介绍的方法更有效的方法,但是当您意识到不需要用分子和分母都在0..1000000范围内的所有因子进行计算时,至少可以避免使用双循环。
您可以只对分母执行循环(从1开始,而不是0),然后增加分子(从0开始),直到超过给定的分数。那时该分子递减一次,因此它代表了潜在的候选解。然后在下一次迭代中-当分母更大时-不必再次将分子重置为0,它可以从其剩余位置继续进行,因为可以确定新的分数将小于给定的分数:那是您真正获得时间的地方。
这意味着您可以使用线性方法而不是二次方法:
def get_prev_fraction(num, denom, limit = 1000000):
bestnum = 0
bestdenom = 1
a = 0
for b in range(1,limit+1):
while a*denom < b*num:
a += 1
a -= 1
if a*bestdenom > b*bestnum:
bestnum, bestdenom = a, b
return bestnum, bestdenom
num, denom = get_prev_fraction(2, 7)
print("the fraction which is to the left of {}/{}={} is {}/{}={}".format(2, 7, 2.0/7, num, denom, num/denom))
输出:
2/7 = 0.2857142857142857左侧的分数是285713/999996 = 0.28571414285657143
请注意,引号中提到d≤1,000,000,因此您需要range(1000001)
包括该限制。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句