Product of consecutive Fib numbers

September 11th 2018

Product of consecutive Fib numbers

이번 문제는 피보나치 수와 관련된 문제입니다. 문제를 먼저 살펴보겠습니다.

Fibonacci-문제

Given a number, say prod (for product), we search two Fibonacci numbers F(n) and F(n+1) verifying

F(n) * F(n+1) = prod.

Your function productFib takes an integer (prod) and returns an array:

[F(n), F(n+1), true] or {F(n), F(n+1), 1} or (F(n), F(n+1), True)

depending on the language if F(n) * F(n+1) = prod.

If you don't find two consecutive F(m) verifying F(m) * F(m+1) = prod, you will return

[F(m), F(m+1), false] or {F(n), F(n+1), 0} or (F(n), F(n+1), False)

F(m) being the smallest one such as F(m) * F(m+1) > prod.

//Example
productFib(714);
// should return [21, 34, true],
// since F(8) = 21, F(9) = 34 and 714 = 21 * 34

productFib(800);
// should return [34, 55, false],
// since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55

Notes: Not useful here but we can tell how to choose the number n up to which to go: we can use the "golden ratio" phi which is (1 + sqrt(5))/2 knowing that F(n) is asymptotic to: phi^n / sqrt(5). That gives a possible upper bound to n.

문제가 꽤 깁니다. 요약하면, 임의의 수가 주어지면 '임의의 수 = F(n) x F(n +1)'이 성립하는 수를 찾아 Boolean값과 함께 반환하는 함수를 만드는 것입니다. 성립하는 수가 없으면 'F(m) * F(m+1) > prod'이 성립하는 가장 작은 수를 찾아 위 Example의 형식과 같이 반환하는 것입니다.

피보나치-개념

이렇게 피보나치를 만난 것도 인연이니까, 피보나치에 대한 기본적인 개념에 대해 먼저 인지하고 문제를 풀어봅시다! 알고리즘 문제에도 자주 활용되는 개념인 것 같으니 알아두면 좋을 것 같습니다. 유튜브에 괜찮은 소개 영상이 있어 공유합니다.

피보나치 수는 0과 1로 시작해, 두 연속된 숫자를 더함으로써 무한하게 확장되는 수를 나열한 것입니다.

ex ) 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

피보나치는 오늘날 다양한 분야에서 적용되고 사용하고 있습니다. 검색 알고리즘, 주식거래, 건축, 미술, 음악, 카지노 등에서도 사용을 하고 있습니다. 하지만, 가장 쉽게 접할수 있는 부분은 황금비라고 불리는 비율입니다.

황금비는 어떠한 두 형태의 비율을 나타내는 수학적 용어입니다. 그림과 같이 a대 b의 비율과 a + b의 합과 a의 비율, 두 비율이 서로 유사하면 이 비율을 황금비(1.618)라고 합니다.

피보나치 수의 비율을 확인해 보면 황금비율과 근접한 것을 확인할 수 있습니다. 또한, 피보나치 수가 더 커질수록 황금비에 더 가까워 집니다.

나의풀이

여기까지 본론같은 서론이었습니다. 다시 문제로 돌아가 피보나치 수의 곱의 값이 함수에 주어진 숫자와 일치하는지 확인을 하도록 하겠습니다.

function productFib(prod) {
  // 내부함수 fib를 이용해, 피보나치 값을 캐싱할 객체를 생성함.
  var cache = {};
  var result = 0;

  // 피보나치 수열을 생성함. loop 범위를 줄일수 있을것 같은데..더 고민해 보겠습니다..
  for (var i = 0; result < prod; i++) {
    cache[i] = fib[i];
    result = cache[i];
  }

  // 저장된 피보나치 수열을 순차적으로 두 항목씩 더하며, 인자와 값이 같은지 확인후 반환함.
  for (var key in cache) {
    var sum = cache[key] * cache[parseInt(key) + 1];
    if (sum === prod) {
      return [cache[key], cache[parseInt(key) + 1], true];
    } else if (sum > prod) {
      return [cache[key], cache[parseInt(key) + 1], false];
    }
  }

  // 피보나치 수를 생성하는 내부함수
  function fib(n) {
    if (cache.hasOwnProperty(n)) {
      return cache[n];
    } else {
      if (n === 0) {
        return 0;
      }
      if (n === 1) {
        return 1;
      }
      cache[n] = fib(n - 1) + fib(n - 2);
      return cache[n];
    }
  }
}

Handmade with .