Немного изменен вопрос на основе последовательности Фибоначчи
Недавно мне задали этот вопрос в одном из моих интервью, которое я, конечно же, провалил.
Я просто хочу знать, как это будет решено. Код, который я пытался использовать, был следующим:
def gibonacci(n, x, y):
# Base case
if n == 0:
return x
elif n == 1:
return y
else:
sequence = [x, y]
for i in range(2, n):
next_term = sequence[i-1] - sequence[i-2]
sequence.append(next_term)
return sequence[-1]
Любая помощь, даже просто логическая помощь будет достаточно. Спасибо!
Вы ошиблись на единицу: for i in range(2, n+1):
Иначе говоря: "небольшое" изменение Фибоначчи (точнее, - вместо +) вовсе не "небольшое". Это меняет все в динамике последовательности. И я почти уверен, что тест предназначен для того, чтобы увидеть, кто может его обнаружить, и утверждение, что gibonnaci является «похожей» последовательностью, было здесь ловушкой. Это может быть похоже по письму, но совсем не по поведению.
Ответы 2
Ваш вопрос был для меня немного расплывчатым, но попробуйте следующий код, он может вам помочь.
Попробуй это:
def gibonacci(n,x,y):
if n == 0:
return x
elif n == 1:
return y
else:
for i in range(1, n):
c = y - x
x = y
y = c
return y
print(gibonacci(2,0,1))
Это слишком экспансивный способ вычисления. Я имею в виду, что мое собственное первое решение, вероятно, было бы таким. Но потом я бы проследил результат на некоторых примерах и увидел бы, что возможна оптимизация. Я почти уверен, что весь смысл интервью заключался в том, чтобы проверить, кто может определить закономерность.
Как я сказал в комментариях, я почти уверен, что интервью было сделано, чтобы проверить, кто может подумать о проблеме, прежде чем думать о решении.
Посмотрите, какая у вас последовательность
г₀ = х
г₁ = у
г₂ = у-х
г₃ = у-х - у = -х
г₄ = -х - (ух) = -у
г₅ = -у - (-х) = х-у
г₆ = х-у - (-у) = х
г₇ = х - (х-у) = у
...
Как только вы получили 2 повторяющихся элемента в последовательности, вы не можете ничего сделать, кроме как повторить остальные. Другими словами, gₙ₊₆=gₙ навсегда. Таким образом, шаблон всегда имеет одинаковую длину - 6 циклов: x, y, y-x, -x, -y, x-y.
Следовательно, более быстрое решение без какой-либо итерации
def gibonacci(n, x, y):
if n%3==0:
r=x
elif n%3==1:
r=y
else:
r=y-x
if (n//3)%2:
return -r
else:
return r
Работает за O(1) (в отличие от итерационных методов за O(n)).
Более «сырой» (быстрее, но менее явный с логикой. В любом случае, все варианты O (1)) могут существовать. Например, этот однострочный:
def gibonacci(n, x, y):
return [x,y,y-x,-x,-y,x-y][n%6]
Я не интервьюер. Так что я не могу предположить, что они искали. Но мое чутье подсказывает, что принятый ответ провалил бы собеседование, даже если бы он сработал, и что ожидаемый ответ был похож на этот.
Обновлено: рассмотрение времени
Извините, что возвращаюсь к этому; но из-за недавнего уведомления - благодаря голосующему: D - я снова увидел этот вопрос и заметил то, на что я не обратил достаточно внимания в первую очередь. Вопрос содержит заманчивое утверждение о том, что вы можете предположить, что n<10⁹. Я сказал «trappy» (я имею в виду, что это сделано, чтобы обмануть), потому что это выглядит так, как будто это означает «не волнуйтесь, n не слишком велико». Но 10⁹ велико, и на самом деле это означает «осторожно, n может быть до 10⁹».
Итак, из любопытства, на моем (довольно старом, конечно, но все же, современная машина не будет в 10 раз быстрее, и даже тогда я все еще понимаю свою точку зрения) я замерил принятый ответ с n = 10⁹. На моем компьютере это занимает 78 секунд.
Мой, конечно (без итерации), занимает 370 нс. Это в 200 миллионов раз быстрее. Мы не говорим здесь о простой оптимизации. Такая разница есть разница между "быстро" и "практически невозможно".
Таким образом, это замечание (n<10⁹) в утверждении является еще одним доказательством того, что вы никогда не должны были использовать итеративные вычисления.
Я не думаю, что целью интервью было реализовать итеративную функцию. Вероятно, это было сделано для того, чтобы посмотреть, кто увидит закономерность в результате.