项目Euler # 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结果求和需要很长时间。也许你还可以做一些其他的事情来优化(提示，提示)

Answer 2

即使对每个数字进行非常快速的计算也会花费太长的时间。要满足1分钟规则，您需要每秒求解/添加1.5万亿个数字。

我认为一定有一种方法可以更直接地计算结果。

Answer 3

90,000,000,000,000是一个很大的数字，我试着检查每一个百万分之一的数字，并认为平均值将足够接近，但无济于事。