c++ - 不使用 for/while 循环的 Pascal 三角形计算

Question

我想从给定的数据集生成 Pascal 金字塔数据，如下所示

金字塔(1,2,3,4,5,6,7,8,9);

这就是我一直在做的，但它只到达第二层，而我希望它递归循环到顶部。

template<typename T>
const T Pyramid(T a, T b)
{   
    return a + b;
}

template<typename T, typename ...A>
const T Pyramid(T t1, T t2, A...a)
{

    return Pyramid(t1, t2) + Pyramid(t2, a...);
}

你能帮我填满下一层吗？ ;)

Answer 1

C++17

这是 C++17 的解决方案(使用 fold expressions ):

#include <iostream>
#include <stdexcept>
#include <utility>


using Integer = std::uint64_t;


constexpr auto Factorial(const Integer n)
{
    Integer factorial = 1;

    for (Integer i = 2; i <= n; ++i)
    {
        factorial *= i;
    }

    return factorial;
}

constexpr auto Binom(const Integer n, const Integer m)
{
    if (n < m)
    {
        throw std::invalid_argument("Binom: n should not be less than m");
    }

    return Factorial(n) / Factorial(m) / Factorial(n - m);
}

template <Integer... indices, typename... Types>
constexpr auto PyramidImplementation(std::integer_sequence<Integer, indices...>, Types... values)
{    
    return ((Binom(sizeof...(values), indices) * values) + ...);
}

template <typename... Types>
constexpr auto Pyramid(Types... values)
{
    return PyramidImplementation(std::make_integer_sequence<Integer, sizeof...(values)>{}, values...);
}

// ...

constexpr auto pyramid = Pyramid(1, 2, 3, 4, 5, 6, 7, 8, 9);

std::cout << "Pyramid = " << pyramid << std::endl;

Live demo

此解决方案不使用递归，因为 a[i] (i = 0 ... n - 1) 所需的结果可以计算为binom(n, i) * a[i] 的总和(对于 i = 0 ... n - 1)，其中 binom(n, m ) 是 binomial coefficient . Binom 函数以最简单的方式实现，因此它仅适用于较小的 n 值。

C++14

可以通过以下 PyramidImplementation 函数实现使代码与 C++14 兼容:

#include <type_traits>


template <Integer... indices, typename... Types>
constexpr auto PyramidImplementation(std::integer_sequence<Integer, indices...>, Types... values)
{
    using Do = int[];
    std::common_type_t<Types...> pyramid{};

    (void)Do{0, (pyramid += Binom(sizeof...(values), indices) * values, 0)...};

    return pyramid;
}

Live demo