#python #python-3.x
#python #python-3.x
Вопрос:
12-й член, F12, является первым членом, содержащим три цифры.
Какой индекс первого члена в последовательности Фибоначчи должен содержать 1000 цифр?
a = 1
b = 1
i = 2
while(1):
c = a b
i = 1
length = len(str(c))
if length == 1000:
print(i)
break
a = b
b = c
Я получил ответ (работает достаточно быстро). Просто смотрю, есть ли лучший способ для этого вопроса
Комментарии:
1. вы можете использовать dis для проверки своих версий
2. Если ваш код работает и вам нужны советы о том, как его улучшить, попробуйте форум Code Review SE .
3. Конечно, производительность можно улучшить. Вы можете решить проблему намного быстрее, потому что есть точная формула для вычисления n-го числа Фибоначчи — math.hmc.edu/funfacts/ffiles/10002.4-5.shtml . Я думаю, возможен даже алгоритм O (1).
Ответ №1:
Если вы ответили на вопрос, вы найдете множество объяснений ответов в теме проблемы. Решение, которое вы опубликовали, в значительной степени в порядке. Вы можете получить небольшое ускорение, просто проверяя, что ваш c>=10^999
на каждом шаге вместо того, чтобы сначала преобразовывать его в строку.
Лучший метод — использовать тот факт, что, когда числа Фибоначчи становятся достаточно большими, числа Фибоначчи сходятся к round(phi**n/(5**.5))
где phi=1.6180...
золотое сечение и round(x)
округляется x
до ближайшего целого числа. Давайте рассмотрим общий случай нахождения первого числа Фибоначчи, состоящего из более чем m
цифр. Затем мы ищем n
такое, чтобы round(phi**n/(5**.5)) >= 10**(m-1)
Мы можем легко решить эту проблему, просто взяв лог обеих сторон и наблюдая за этим log(phi)*n - log(5)/2 >= m-1
, а затем решая для n
.
Если вам интересно: «Откуда мне знать, что он сошелся на число n
th?» Ну, вы можете проверить сами, или вы можете посмотреть в Интернете.
Кроме того, я думаю, что подобные вопросы относятся либо к Code Review SE, либо к Computer Science SE. Даже Math Overflow может быть хорошим местом для вопросов Project Euler, поскольку многие из них основаны на теории чисел.
Ответ №2:
Ваше решение полностью подходит для # 25 в project euler. Однако, если вы действительно хотите оптимизировать скорость здесь, вы можете попытаться вычислить Фибоначчи, используя тождества, о которых я писал в этом сообщении в блоге: https://sloperium.github.io/calculating-the-last-digits-of-large-fibonacci-numbers.html
from functools import lru_cache
@lru_cache(maxsize=None)
def fib4(n):
if n <= 1:
return n
if n % 2:
m = (n 1) // 2
return fib4(m) ** 2 fib4(m - 1) ** 2
else:
m = n // 2
return (2 * fib4(m - 1) fib4(m)) * fib4(m)
def binarySearch( length):
first = 0
last = 10**5
found = False
while first <= last and not found:
midpoint = (first last) // 2
length_string = len(str(fib4(midpoint)))
if length_string == length:
return midpoint -1
else:
if length < length_string:
last = midpoint - 1
else:
first = midpoint 1
print(binarySearch(1000))
Этот код тестируется примерно в 12 раз быстрее, чем ваше решение. (хотя для этого требуется первоначальное предположение о максимальном размере)