Product of consecutive Fib numbers ( 5 kyu )

문제

The Fibonacci numbers are the numbers in the following integer sequence (Fn):

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …
such as

F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.
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) = prodyou 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.

Examples

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

피보나치 수열중 연속된 수의 곱으로 인자 값이 나올수 있는지 판별하는 문제

풀이

function productFib(prod){
  let arr = [0, 1], multi = 0, i = 2;
  while ( multi <= prod ) {
    arr[i] = arr[i-1] + arr[i-2];
    multi = arr[i]*arr[i-1];
    if ( multi === prod ) return [arr[i-1], arr[i], true]
    i++
  }
  return [arr[i-2], arr[i-1], false]
}

피보나치 수열을 arr에 담고, 연속된 수의 곱을 multi에 담아 prod보다 작을 때까지 반복하고, 일치하면 해당 값을 리턴, 일치하지 않다면 다음 두개의 수를 리턴

다른 사람의 풀이

function productFib(prod){
  var n = 0;
  var nPlus = 1;  
  while(n*nPlus < prod) {
    nPlus = n + nPlus;
    n = nPlus - n;
  }
  return [n, nPlus, n*nPlus===prod];
}

따로 공간을 만들지 않고도 이런식으로 풀이가 가능하군


+ Recent posts