#python #optimization #fibonacci
Вопрос:
У нас есть входное целое число, скажем, 13. Мы можем найти последовательный подмассив чисел Фибоначчи, который суммируется с 10 — [2,3,5]. Мне нужно найти следующее число, которое не является суммой последовательного подмассива. В данном случае это число будет равно 14. У меня есть этот код, но загвоздка в том, что его можно оптимизировать, чтобы не перебирать все N начиная с указателя влево = 1 и указателя вправо = 1, а каким-то образом «импортировать» из предыдущего N, и я понятия не имею, как это сделать, так что, возможно, кто-то поумнее может помочь.
def fib(n): if n == 1: return 1 if n == 2: return 1 return fib(n-1) fib(n-2) def fibosubarr(n): L_pointer = 1 R_pointer = 2 sumfibs = 1 while sumfibs != n: if sumfibs gt; n and L_pointer lt; R_pointer: sumfibs -= fib(L_pointer) L_pointer = 1 elif sumfibs lt; n and L_poiner lt; R_pointer: sumfibs = fib(R_pointer) R_pointer = 1 else: return False return True n = int(input()) while fibosubarr(n): n = 1 print(n) Комментарии:
1. Да, ваш код очень расточителен. Вы должны построить весь ряд Фибоначчи до вашего целевого числа (этого более чем достаточно, но это нормально) и сохранить его в списке, а не воссоздавать его каждый раз. Используйте этот список (
fib[n]) вместо вызова функции (fib(n)).
Ответ №1:
Вот техника, называемая «запоминание». fib Функция здесь отслеживает текущий список и расширяет его только по мере необходимости. Как только он сгенерировал номер, ему не нужно делать это снова.
_fib = [1,1] def fib(n): while len(_fib) lt;= n: _fib.append( _fib[-2] _fib[-1] ) return _fib[n] С вашей схемой 200000 вызвали заметную задержку. С помощью этой схемы даже 2 миллиарда запускаются мгновенно.
Ответ №2:
Чтобы получить следующую сумму подмножества, вам нужен только один вызов функции-при условии, что вы отслеживаете наименьшее значение суммы, которое было превышено n .
Я бы также использовал генератор чисел Фибоначчи:
def genfib(): a = 1 b = 1 while True: yield b a, b = b, a b def fibosubarr(n): left = genfib() right = genfib() sumfibs = next(right) closest = float("inf") while sumfibs: if sumfibs gt; n: closest = min(sumfibs, closest) sumfibs -= next(left) elif sumfibs lt; n: sumfibs = next(right) else: return n return closest Теперь вы можете сделать то, что вы сделали-вывести следующую допустимую сумму, которая является, по крайней мере, входным значением:
n = int(input()) print(fibosubarr(n)) Вы также можете циклически переходить от одной такой суммы к другой:
n = 0 for _ in range(10): # first 10 such sums n = fibosubarr(n 1) print(n)