anothel의 지식 창고
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)
'연습장' 카테고리의 다른 글
Can you get the loop? (0) | 2021.10.28 |
---|---|
Human Readable Time (0) | 2021.10.28 |
Greed is Good (0) | 2021.10.27 |
Decode the Morse code (0) | 2021.10.27 |
정렬 > K번째수 (0) | 2021.10.26 |