Проект Эйлера # 255

Question

Задача Эйлера проекта # 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

3.6.3 Тип XRange :

"3.6.3 Тип XRange

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

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

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

Answer 4

90 000 000 000 000 - это много цифр для проверки, я пробовал проверять каждое миллионное число и думал, что среднее будет достаточно близко, но безрезультатно.