Product of consecutive Fib numbers

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(n) verifying F(n) * F(n+1) = prodyou will return

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

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

 

Some Examples of Return:

(depend on the language)

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 ----- productFib(714) # should return [21, 34, true],  productFib(800) # should return [34, 55, false],  ----- productFib(714) # should return {21, 34, 1},  productFib(800) # should return {34, 55, 0},         ----- productFib(714) # should return {21, 34, true},  productFib(800) # should return {34, 55, false},

 

Solution

#include <vector>
typedef unsigned long long ull;
class ProdFib {
 public:
  static std::vector<ull> productFib(ull prod);
};

ull f(ull n) {
  if (n <= 1) return n;

  return f(n - 1) + f(n - 2);
}

std::vector<ull> ProdFib::productFib(ull prod) {
  ull n = 0;
  ull f1 = 0, f2 = 0;
  ull result = 0;
  std::vector<ull> vResult;

  while (true) {
    f1 = f(n);
    f2 = f(n + 1);
    result = f1 * f2;
    if (result < prod) {
      n++;
      continue;
    } else if (result == prod) {
      vResult.push_back(f1);
      vResult.push_back(f2);
      vResult.push_back(1);
    } else {
      vResult.push_back(f1);
      vResult.push_back(f2);
      vResult.push_back(0);
    }
    break;
  }

  return vResult;
}

 

user5715875의 코드

#include <vector>
typedef unsigned long long ull;
class ProdFib
{
public:
  static std::vector<ull> productFib(ull prod)
  {
      ull a = 0, b = 1;
      while (a * b < prod) {
          std::swap(a, b);
          b += a;
      }
      return {a, b, ((a*b == prod) ? true : false)};
  }
};

 

MikeD32의 코드

#include <vector>
#include <array>
typedef unsigned long long ull;

template <ull I>
struct Fib
{
  static const ull val = Fib<I-1>::val + Fib<I-2>::val;
};

template<>
struct Fib<0>
{
  static const ull val = 0;
};

template<>
struct Fib<1>
{
  static const ull val = 1;
};

template<size_t ... I>
int fib_impl(std::index_sequence<I...>, const ull i)
{
  constexpr std::array<ull, sizeof...(I)> a = 
  {
    Fib<I>::val...
  };
  
  return a[i];
}

ull fib(const ull i)
{
  return fib_impl(std::make_index_sequence<55>(), i);
}

class ProdFib
{
public:
  static std::vector<ull> productFib(ull prod);
};

std::vector<ull> ProdFib::productFib(ull prod)
{
  const unsigned int maxSeq = 55;
  std::vector<ull> result = {};
  
  for(unsigned int i = 1; i < maxSeq; ++i)
  {
    const ull fib1 = fib(i-1);
    const ull fib2 = fib(i);
    if(fib1*fib2 == prod)
    {
      result.emplace_back(fib1);
      result.emplace_back(fib2);
      result.emplace_back(true);
      
       return result;
    }
    else
    {
      if(fib1*fib2 > prod)
      {
        result.emplace_back(fib1);
        result.emplace_back(fib2);
        result.emplace_back(false);
        
         return result;
      }
    }
  }
  
  return result;
}

 

후기

문제에 피보나치수열 얘기가 있길래 피보나치수열을 써서 풀어야 한다고 생각했다. 그런데 꼭 그렇지만은 않더라는 거예요. 우리가 꼭 문제에 나온 것을 반드시 그대로 받아들여야 하는 것만은 아니었더라는 거예요. 그래도 내가 푼 문제를 먼저 되돌려 보겠다는 거예요. 연속적인 2개의 피보나치 수를 곱한 값이 인수로 받은 정수와 비교했을 때, 같은지 작은지 큰지를 비교해봐야겠다는 거예요. 그리고 그나마 곱셈 연산을 줄이기 위해서 지역변수를 더 선언해봤다는 거예요. 나는 같은 연산을 두 번 이상 할 때부터 함수 혹은 변수에 담겠다고 오래전에 다짐했다는 거예요. 다시 코드를 말해보자면 작으면 다음으로, 같으면 1 크면 0을 벡터의 세 번째 값에 넣겠다는 거예요. 이렇게 푸는 게 딱 문제를 코드로 옮기겠다는 거예요.

그래서 남의 코드를 한번 훑어봤다는 거예요. 첫 번째 남의 코드에서 이 사람은 굳이 피보나치수열을 재귀로 하나 빼지 않고 그냥 막 갖다가 구현했다는 거예요. 아주 깔끔하고 피보나치를 정확하게 알고 있다는 거예요. 5 kyu 전까지만 해도 나도 이렇게 간결하게 구현이 가능했었다는 거예요. 이제 이렇게 짤 수도 있다는 걸 알았으니 앞으로는 나도 더 아름다워지기 위해서 노려해 봐야겠다는 거예요.

두 번째 남의 코드에서 이 사람은 이상한 사람이에요. 왜 자꾸 소 잡는 칼로 닭을 잡는지 모르겠다는 거예요. 사실 템플릿으로 털렸던 면접이 두 번이라는 거예요. 그런데도 아직도 템플릿이 나오면 너무 두렵다는 거예요. 공부를 좀 더 하고 코드를 다시 분석해봐야겠다는 거예요..

 

(url: https://www.codewars.com/kata/5541f58a944b85ce6d00006a)