N-е значение последовательности Фибоначчи JavaScript (ошибка тайм-аута) - PullRequest
Новая
       28

N-е значение последовательности Фибоначчи JavaScript (ошибка тайм-аута)

0 голосов
/ 18 октября 2018

У меня есть рабочее решение для этого Ката (найдите n-е значение последовательности Фибоначчи), однако я получаю сообщение об ошибке тайм-аута.Кто-нибудь может дать совет о том, как реорганизовать этот процесс для более эффективной работы?Заранее спасибо!

Вот ссылка с описанием - https://www.codewars.com/kata/simple-fun-number-395-fibonacci-digit-sequence/train/javascript

Вам даны три неотрицательных целых числа a, b и n, и вы создаете бесконечную последовательность, аналогичную последовательности Фибоначчи, используйтеследующие правила:

step1: используйте ab в качестве начальной последовательности.шаг 2: вычислите сумму двух последних цифр последовательности и добавьте ее в конец последовательности.повторить шаг2 Ваша задача завершить поиск функции.Возврат n-й цифры (начиная с 0) последовательности. 

function find(a,b,n){
  let start = ("" + a + b);
  let next = a + b;
  let seq = start + next;
  
  while (seq.length <= n) {
    seq += (parseInt(seq[seq.length-2]) + parseInt(seq[seq.length-1]));
  }
  return parseInt(seq[n]);
}

console.log(find(7,8,9))

// should return 5

Ответы [ 2 ]

0 голосов
/ 18 октября 2018

Когда вы конвертируете и выполняете строковую операцию, она обычно медленнее. 

function nextVal(num){
    const last = (num%10);
    const lastButOne = (num - last)/10 % 10;
    const sum = last + lastButOne;
    return sum < 10 ? num * 10 + sum : num *100 + sum;
}
function find(a,b,n){
  let num = a * 10 + b;
  const above = Math.pow(10, n);// anything less than we don't have enough digits


  while (num < above) {
    num = nextVal(num);
  }
  return Number(`${num}`.charAt(n));
}

Приведенный выше код основан на проверке числа и преобразует его только в строку (чего также можно избежать)

0 голосов
/ 18 октября 2018

Во-первых.,,не используйте строки, не используйте parseInt, не держите всю последовательность сразу.Вам нужны только цифры, и вам нужны только две последние цифры.Для числа x от 10 до 18 (которое является максимально возможной суммой из двух цифр) его место в десятках составляет 1, а в его местах - x - 10.Одно это будет значительным улучшением.

Во-вторых.,,поскольку вся последовательность после заданной точки определяется первыми двумя цифрами в этой точке, 1 и имеется только 100 возможных последовательностей из двух цифр, каждая последовательность должна повторяться в пределах 200 цифр;то есть, в пределах не более 200 цифр, он обязательно войдет в цикл повторяющихся цифр, из которого он никогда не выйдет, где длина этого цикла меньше 200 цифр. 2 Так что если n больше чемнесколько сотен можно существенно оптимизировать, найдя длину этого цикла и "пропустив" большое кратное этой длины.

1.На самом деле, это не совсем так, как написано.Например, последовательности 69156… и 79167… bot содержат 91, но за ними следуют разные вещи.Это связано с тем, что «1» относится к двузначному числу, оба , чьи цифры определяются двумя предыдущими цифрами.Я не уверен, как это выразить лучше, но, надеюсь, вы понимаете, о чем я.Это не влияет на общий аргумент, но вы должны быть осторожны при применении идеи.
2.На самом деле гораздо меньше;проверяя все возможные значения a и b , я обнаружил, что последовательность всегда входит в цикл и завершает свою первую итерацию всего за 25 цифр!Но я не уверен, как строго обосновать эту гораздо меньшую цифру, кроме исчерпывающего тестирования;так что, вероятно, было бы обманом писать код так, чтобы он опирался на него.

...