Project Euler 第255题

Question

Project euler问题#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

90,000,000,000,000 这个数字实在是太庞大了，要检查这么多数字可不是件简单的事。我试着每一百万个数字检查一次，想着这样得到的平均值应该差不多，但结果并没有成功。

Answer 2

即使对每个数字进行非常快速的计算，所需的时间也会太长。为了满足每分钟的要求，你需要每秒处理1.5万亿个数字。

我觉得一定有更直接的方法来计算结果。

Answer 3

不要使用 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 这么多结果会花很长时间。也许你可以考虑其他方法来优化一下 (提示，提示)