JavaScript로 Fibonacci 구현하기

 

1. fibonacci sequence N개 구하기

function fibonacci(number) {
  if (number < 1) {
    return;
  }

  const fibonacciSequence = [1];

  if (number === 1) {
    return fibonacciSequence;
  }

  let currentValue = 1;
  let previousValue = 0;

  for (let i = 2; i <= number; i++) {
    currentValue += previousValue;
    previousValue = currentValue - previousValue;

    fibonacciSequence.push(currentValue);
  }

  return fibonacciSequence;
}

 

2. fibonacci N번째 수 구하기

function fibonacci(number) {
  if (number < 1) {
    return;
  }

  if (number === 1) {
    return number;
  }

  let currentValue = 1;
  let previousValue = 0;

  for (let i = 2; i <= number; i++) {
    currentValue += previousValue;
    previousValue = currentValue - previousValue;
  }

  return currentValue;
}

 

3. fibonacci Closed-form expression (Binet's formula)

https://jjycjnmath.tistory.com/369

피보나치 수(Fibonacci number) 판별법

=> 어렵네 알고리즘 이해가 좀 필요

/**
 * Calculate fibonacci number at specific position using closed form function (Binet's formula).
 * @see: https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression
 *
 * @param {number} position - Position number of fibonacci sequence (must be number from 1 to 75).
 * @return {number}
 */
export default function fibonacciClosedForm(position) {
  const topMaxValidPosition = 70;

  // Check that position is valid.
  if (position < 1 || position > topMaxValidPosition) {
    throw new Error(`Can't handle position smaller than 1 or greater than ${topMaxValidPosition}`);
  }

  // Calculate √5 to re-use it in further formulas.
  const sqrt5 = Math.sqrt(5);
  // Calculate φ constant (≈ 1.61803).
  const phi = (1 + sqrt5) / 2;

  // Calculate fibonacci number using Binet's formula.
  return Math.floor((phi ** position) / sqrt5 + 0.5);
}

- 주석은 position parameter 값이 1~75라면서 왜 max 값은 70으로 설정되었지?

- 왜 1부터 75까지만 가능하지?

 

 

https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/fibonacci