Расчет треугольника Паскаля без использования цикла for / while
Я хотел бы генерировать данные пирамиды Паскаля из заданного набора данных, который выглядит следующим образом
Pyramid(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...);
}
Не могли бы вы помочь мне заполнить следующие слои? 😉
Решение
C ++ 17
Вот решение C ++ 17 (используя сложить выражения):
#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;
Это решение не использует рекурсию, потому что необходимый результат для a[i] (i = 0 ... n - 1) можно рассчитать как сумму binom(n, i) * a[i] (за i = 0 ... n - 1), где binom(n, m) это биномиальный коэффициент. Binom Функция реализована самым простым способом, поэтому она будет работать только при небольших значениях n,
C ++ 14
Код можно сделать совместимым с C ++ 14 с помощью следующего PyramidImplementation реализация функции:
#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;
}
Другие решения
Других решений пока нет …