c++ - 计算斐波那契数的模板元编程

Question

最近在一次工作面试中，我被要求给出三级斐波那契数列第 100 个元素的结果(Fib(n)=Fib(n-1)+Fib(n-2)+Fib(n-3) )。我完成了数学归纳法，构造了一个类来表示大于 long long 的数字。然后要求我通过模板元编程来实现它。问题是结果会超出 long long 的范围，而我不这样做知道如何解决这个问题。这是我使用模板元编程的代码。

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;
}

Answer 1

一种可能的实现是使用自定义结构来存储数字而不是内置类型。例如，您可以存储这样的数字:

template <int... Digits>
struct number<Digits... > { };

注意:为了添加时简单起见，我以相反的顺序存储数字，因此数字 275存储为number<5, 7, 2> .

斐波那契仅需要加法，因此您只需定义加法，例如模板 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

虽然 OEIS 中不存在第 100 个，你可以检查第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模板:

1. 这是一个小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;