Технические интервью: N-й Фибоначчи

(2 разных решения в JavaScript)

Последовательность Фибоначчи определяется следующим образом: первое число последовательности — 0, второе число — 1, а nе число — это сумма (n - 1)-го и (n - 2)-го чисел. Напишите функцию, которая принимает целое число n и возвращает n число Фибоначчи.

Первые несколько чисел последовательности Фибоначчи: 0, 1, 1, 2, 3, 5, 8..

Мы собираемся использовать нулевую индексацию для серии.

// Input: n = 0
// Expected output: 0

// Input: n = 2
// Expected output: 1

// Input: n = 6
// Expected output: 8

Решение №1

Во-первых, давайте создадим функцию fibonacci. Если n меньше 2, функция должна вернуть n .

function fibonacci(num) {

  // if num is 0 or 1, return itself
  if (num < 2) {
    return num;
  }
}

Чтобы сохранить значения двух предыдущих чисел, давайте создадим переменную.

function fibonacci(num) {

  if (num < 2) {
    return num;
  }

  // create a variable to store last 2 numbers
  let lastTwo = [0, 1];
}

При переборе всех чисел до заданного n функция должна вычислить сумму последних 2 чисел и переназначить значения переменной.

function fibonacci(num) {

  if (num < 2) {
    return num;
  }

  let lastTwo = [0, 1];

  // iterate through all the numbers less than (num - 1)
  for (let i = 0; i < num - 1; ++i) {

   // calculate a sum of last 2 numbers
   const sum = lastTwo[0] + lastTwo[1];

   // reassign new values to last 2 numbers
   lastTwo = [lastTwo[1], sum];
  }
}

Наконец, верните последнее число из переменной lastTwo.

function fibonacci(num) {

  if (num < 2) {
    return num;
  }

  let lastTwo = [0, 1];

  for (let i = 0; i < num - 1; ++i) {

   const sum = lastTwo[0] + lastTwo[1];
   lastTwo = [lastTwo[1], sum];

  // return last number
  return lastTwo[1];
  }
}

Решение №2. Рекурсивный

Рекурсивное решение короче. Первый шаг такой же. Если n меньше 2, функция должна вернуть n.

function fibonacci(num) {

  // if num is 0 or 1, return itself
  if (num < 2) {
    return num;
  }
}

После этого функция должна вернуть сумму 2 fibonacci функций, вызванных рекурсивно с (n - 1) и (n - 2) параметрами.

function fibonacci(num) {

  if (num < 2) {
    return num;
  }

  // calculate each of two last n's separately with recursion and make a sum
  return fibonacci(n - 1) + fibonacci(n - 2);
}

Вы можете узнать больше о рекурсивных функциях по ссылке ниже: