python - 欧拉计划 #255

Question

Project euler problem #255是相当数学的。对于给定的示例，我想出了它是如何完成的。由于我是 Python 的新手，我不确定如何处理长范围值。以下是我的解决方案。但它如何适用于 10^13 和 10^14？

def ceil(a, b):
 return (a + b - 1) / b;

def func(a, b):
 return (b + ceil(a, b)) / 2;

def calculate(a):
 ctr = 1;
 y = 200;
 while 1:
  z = func(a, y);
  if z == y:
   return ctr;
  y = z;
  ctr += 1;

result = sum(map(calculate, xrange(10000, 100000))) / 9e4;
print "%.10f" % result;

这给出 3.2102888889。

Answer 1

不要使用 map 。它会在内存中生成一个大列表。

不要使用xrange。它仅限于短整数。

改用生成器。

# No changes on `ceil()`, `func()` and `calculate()`

def generate_sequence(start, stop):
    while start < stop:
        yield start
        start += 1

result = sum(calculate(n) for n in generate_sequence(10**13, 10**14))
print "%.10f" % result;

那会运行。但是要对 10**14 - 10**13 = 90,000,000,000,000 结果求和需要很长时间。也许您还可以做一些其他事情来优化(hint, hint)