Python: for循环花费的时间太长
Python: for循环花费的时间太长
提问于 2018-07-22 05:09:18
我正在试着写一个代码来解决网上看到的减少分数的问题。对于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])回答 1
Stack Overflow用户
回答已采纳
发布于 2018-07-22 05:35:20
我猜可能有比我在这里介绍的更有效的方法，但至少当你意识到你不需要计算分子和分母都在1000000范围内的所有因子时，你可以避免双重循环。
您可以只对分母(从1开始，而不是0)执行该循环，然后递增分子(从0开始)，直到它超过给定的分数。在那一刻，分子递减一次，所以它代表了一个潜在的候选解。然后在下一次迭代中--当分母比1大时--没有必要再次将分子重置为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)以包含该限制。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51460131
复制相关文章
相似问题
腾讯云开发者
