计算Fibonacci的模板元编程
计算Fibonacci的模板元编程
提问于 2020-01-03 14:33:12
最近在一次面试中，我被要求给出一个三级Fibonacci序列的第100元素的结果(Fib(N)=Fib(n-1)+Fib(n-2)+Fib(n-3))。我完成了数学归纳法，并构造了一个课程来表示大于长的数字。然后我被要求通过模板元编程来实现它。问题是，结果将超过长时间的范围，我不知道如何解决这个问题。下面是我使用模板元编程的代码。
template<long long num>
struct fib
{
enum { result = fib<num - 1>::result + fib<num - 2>::result + fib<num - 3>::result};
};
template<>
struct fib<0>
{
enum { result = 1 };
};
template<>
struct fib<1>
{
enum { result = 1 };
};
template<>
struct fib<2>
{
enum { result = 2 };
};
template<>
struct fib<3>
{
enum { result = 4 };
};
int main()
{
cout << fib<100>::result << endl;
return 0;
}回答 3
Stack Overflow用户
回答已采纳
发布于 2020-01-03 15:21:52
一种可能的实现是使用自定义结构来存储数字，而不是内置类型。例如，您可以存储这样的数字：
template <int... Digits>
struct number<Digits... > { };注意:为了添加时的简单性，我将数字按反向顺序存储，因此数字275存储为number<5, 7, 2>。
Fibonacci只需要加法，所以您只需定义加法，例如模板add (实际实现请参见答案的结尾)。
然后，您可以很容易地定义fib模板：
template <int N>
struct fib_impl {
using type = add_t<
typename fib_impl<N-1>::type,
typename fib_impl<N-2>::type,
typename fib_impl<N-3>::type>;
};
template <>
struct fib_impl<0> { using type = number<0>; };
template <>
struct fib_impl<1> { using type = number<0>; };
template <>
struct fib_impl<2> { using type = number<1>; };
template <int N>
using fib = typename fib_impl<N>::type;使用适当的输出运算符(请参见下面)，您可以打印第100次Tribonacci号：
int main() {
std::cout << fib<100>{} << "\n";
}其中产出：
53324762928098149064722658虽然第100次没有出现在OEIS中，但您可以检查第37次是否正确：
static_assert(std::is_same_v<fib<37>, number<2, 5, 8, 6, 3, 4, 2, 3, 1, 1>>);operator<<的实现
std::ostream& operator<<(std::ostream &out, number<>) {
return out;
}
template <int Digit, int... Digits>
std::ostream& operator<<(std::ostream &out, number<Digit, Digits... >) {
// Do not forget that number<> is in reverse order:
return out << number<Digits... >{} << Digit;
}add模板的实现：
- 这是一个用于连接数字的小型
cat实用程序：
// Small concatenation utility:
template <class N1, class N2>
struct cat;
template <int... N1, int... N2>
struct cat<number<N1... >, number<N2... >> {
using type = number<N1... , N2...>;
};
template <class N1, class N2>
using cat_t = typename cat<N1, N2>::type;- 增加的实际执行情况：
template <class AccNumber, int Carry, class Number1, class Number2>
struct add_impl;
template <class AccNumber, int Carry>
struct add_impl<AccNumber, Carry, number<>, number<>> {
using type = std::conditional_t<Carry == 0, AccNumber, cat_t<AccNumber, number<1>>>;
};
template <class AccNumber, int Carry,
int Digit2, int... Digits2>
struct add_impl<AccNumber, Carry, number<>, number<Digit2, Digits2...>> {
using type = typename add_impl<
cat_t<AccNumber, number<(Digit2 + Carry) % 10>>,
(Digit2 + Carry) / 10,
number<Digits2... >, number<>>::type;
};
template <class AccNumber, int Carry,
int Digit1, int... Digits1>
struct add_impl<AccNumber, Carry, number<Digit1, Digits1... >, number<>> {
using type = typename add_impl<
cat_t<AccNumber, number<(Digit1 + Carry) % 10>>,
(Digit1 + Carry) / 10,
number<Digits1... >, number<>>::type;
};
template <class AccNumber, int Carry,
int Digit1, int... Digits1, int Digit2, int... Digits2>
struct add_impl<AccNumber, Carry, number<Digit1, Digits1... >, number<Digit2, Digits2...>> {
using type = typename add_impl<
cat_t<AccNumber, number<(Digit1 + Digit2 + Carry) % 10>>,
(Digit1 + Digit2 + Carry) / 10,
number<Digits1... >, number<Digits2... >>::type;
};- 短小的包装纸：
template <class... Numbers>
struct add;
template <class Number>
struct add<Number> {
using type = Number;
};
template <class Number, class... Numbers>
struct add<Number, Numbers... > {
using type = typename add_impl<
number<>, 0, Number, typename add<Numbers... >::type>::type;
};
template <class... Numbers>
using add_t = typename add<Numbers... >::type;Stack Overflow用户
发布于 2020-01-03 15:23:05
我不知道准备使用arbirtrary的细节为模板.但是，可以容纳大于long long的数字的玩具数字类型很容易编写：
template <long long H,long long L>
struct my_number {
static const long long high = H;
static const long long low = L;
static const long long mod = 10000000000;
static void print() {
std::cout << high << setw(10) << setfill('0') << low;
}
};它在low中存储结果的最后一个10位数，在high中存储前导位数。两个my_numbers可以通过
template <typename A,typename B>
struct sum {
static const long long low = (A::low + B::low) % A::mod;
static const long long high = A::high + B::high + (A::low + B::low) / A::mod;
using number = my_number<high,low>;
};对于3个数字：
template <typename A,typename B,typename C>
struct sum3 { using number = typename sum<A,sum<B,C>>::number; };如前所述，这只是一个玩具的例子。无论如何，一旦您有了一个可以表示足够大的数字的数字类型，您只需稍微修改一下就可以调整fib：
template<long long num> struct fib {
using result_t = typename sum3< typename fib<num-1>::result_t,
typename fib<num-2>::result_t,
typename fib<num-3>::result_t
>::number;
};
template<> struct fib<0> { using result_t = my_number<0,1>; };
template<> struct fib<1> { using result_t = my_number<0,1>; };
template<> struct fib<2> { using result_t = my_number<0,2>; };
template<> struct fib<3> { using result_t = my_number<0,4>; };
int main() {
fib<100>::result_t::print();
}我无法为fib<100>的正确值找到可靠的来源，因此不幸的是，我无法对此进行测试。
完整的例子是这里。
Stack Overflow用户
发布于 2020-01-03 16:10:41
您可以使用Boost版本的1.72和boost:多精度来完成这一任务。
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
template <int x>
struct fib
{
static constexpr boost::multiprecision::uint1024_t value = x * fib<x - 1>::value;
};
template <>
struct fib<0>
{
static constexpr boost::multiprecision::uint1024_t value = 1;
};
int main()
{
std::cout << fib<100>::value;
}输出：
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000这是使用2019和boost 1.72运行的。请注意，早期版本的boost::multiprecision不是完整的constexpr，因此这可能不会与早期版本的boost一起编译。
编辑:这是三等版本.这与最初的海报版本几乎是逐字的，唯一不同的是constexpr-enabled大数类与boost的用法。
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
template<long long num>
struct fib
{
static constexpr boost::multiprecision::uint1024_t value = fib<num - 1>::value + fib<num - 2>::value + fib<num - 3>::value;
};
template<>
struct fib<0>
{
static constexpr boost::multiprecision::uint1024_t value = 1;
};
template<>
struct fib<1>
{
static constexpr boost::multiprecision::uint1024_t value = 1;
};
template<>
struct fib<2>
{
static constexpr boost::multiprecision::uint1024_t value = 2;
};
template<>
struct fib<3>
{
static constexpr boost::multiprecision::uint1024_t value = 4;
};
int main()
{
std::cout << fib<100>::value;
}输出：
180396380815100901214157639 页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/59580362
复制相关文章
相似问题
腾讯云开发者
