Project 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

90.000.000.000.000 много чисел, чтобы проверить, я попытался проверить каждый миллионный номер и думал, что в среднем будет достаточно близко, но безрезультатно.

Answer 3

Даже очень быстрый расчет для каждого номера займет слишком много времени. Чтобы удовлетворить 1-минутное правило, вам нужно будет решить/добавить 1,5 триллиона чисел в секунду.

Я думаю, что должен быть способ более точно вычислить результат.

Answer 4

3.6.3 XRange Type:.

«Тип 3.6.3 XRange

Тип xrange представляет собой неизменное последовательность, которая обычно используется для цикла Преимущество типа xrange является то, что объект xrange будет всегда брать тот же объем памяти, независимо от его диапазона . Не существует согласованных преимуществ производительности.

Объекты XRange имеют очень мало поведения : они поддерживают только индексирование, итерацию и функцию len(). "

возможно ... оптимизируйте свои функции пола и потолка? : P