C++值元编程
——永远不要在OJ上使⽤值元编程，过于简单的没有优势，能有优势的编译错误。
背景
2019年10⽉，我在学习算法。有⼀道作业题，输⼊规模很⼩，可以⽤打表法解决。具体⽅案有以下三种：
1. 运⾏时预处理，⽣成所需的表格，根据输⼊直接到对应项，稍加处理后输出；
2. ⼀个程序⽣成表格，作为提交程序的⼀部分，后续与⽅法1相同，这样就省去了运⾏时计算的步骤；
3. 以上两种⽅法结合，编译期计算表格，运⾏时直接查询，即元编程（metaprogramming）。
做题当然是⽤⽅法1或2，但是元编程已经埋下了种⼦。时隔⼤半年，我来补上这个坑。
题⽬
描述
将正整数nn表⽰成⼀系列正整数之和，n=n1+n2+...+n k n=n1+n2+...+n k，其中n1≥n2≥...≥n k≥1n1≥n2≥...≥n k≥1，
k≥1k≥1。正整数nn的这种表⽰称为正整数nn的划分。
输⼊
标准的输⼊包含若⼲组测试数据。每组测试数据是⼀⾏输⼊数据，包括两个整数NN和KK。（ 0≤N≤500≤N≤50，0≤K≤N0≤K≤N ）
输出
对于每组测试数据，输出以下三⾏数据：
第⼀⾏: NN划分成KK个正整数之和的划分数⽬
第⼆⾏: NN划分成若⼲个不同正整数之和的划分数⽬
第三⾏: NN划分成若⼲个奇正整数之和的划分数⽬
样例输⼊
5 2
样例输出
2
3
3
提⽰
第⼀⾏: 4+1，3+2
第⼆⾏: 5，4+1，3+2
第三⾏: 5，1+1+3，1+1+1+1+1+1
解答
标准的动态规划题。⽤dp[c][i][j]表⽰把i分成c个正整数之和的⽅法数，其中每个数都不超过j。
第⼀⾏。初始化：由i≤ji≤j是否成⽴决定dp[1][i][j]的值，当i≤ji≤j时为1，划分为i=ii=i，否则⽆法划分，值为0。
递推：为了求dp[c][i][j]，对i=i1+i2+...+i c i=i1+i2+...+i c，i1≥i2≥...≥i c i1≥i2≥...≥i c中的最⼤数i1分类讨论，最⼩为 1，最⼤不超过i−1，因为c≥2，同时不超过j，因为定义。最⼤数为n时，对于把i−n分成c−1 个数，每个数不超过n的划分，追加上n可得i的⼀个划分。n只有这些取值，没有漏；对于不同的n，由于最⼤数不⼀样，两个划分也不⼀样，没有多。故递推式为：
dp[c][i][j]=min{i−1,j}
∑
n=1dp[c−1][i−n][n ]
dp[K][N][N]即为所求ans1[K][N]。
第⼆⾏。可以把递推式中的dp[c - 1][i - n][n]修改为dp[c - 1][i - n][n - 1]后重新计算。由于只需⼀个与c ⽆关的结果，可以省去c这⼀维度，相应地改变递推顺序，每轮累加。
另⼀种⽅法是利⽤已经计算好的ans1数组。设i=i1+i2+...++i c−1+i c，其中i1≥i2≥...≥i c+1≥i c≥0，则
i1−(c−1)≥i2−(c−2)≥...≥i c−1−1≥i c≥0，且i1−(c−1)+i2−(c−2)+...+i c−1−1+i c=i−c(c−1)
2，故把
i 划分成
c 个不同正整数之和的划分数⽬等于ans[c][i - c * (c - 1) / 2]，遍历c累加即得结果。
第三⾏。想法与第⼆⾏相似，也是⼀个对应，此处从略。另外，数学上可以证明，第⼆⾏和第三⾏的结果⼀定是⼀样的。
#include <iostream>
#include <algorithm>
constexpr int max = 50;
int dp[max + 1][max + 1][max + 1] = { 0 };
int ans1[max + 1][max + 1] = { 0 };
int ans2[max + 1] = { 0 };
int ans3[max + 1] = { 0 };
int main()
{
int num, k;
for (int i = 1; i <= max; ++i)
for (int j = 1; j <= max; ++j)
dp[1][i][j] = i <= j;
for (int cnt = 2; cnt <= max; ++cnt)
for (int i = 1; i <= max; ++i)
for (int j = 1; j <= max; ++j)
{
auto min = std::min(i - 1, j);
for (int n = 1; n <= min; ++n)
dp[cnt][i][j] += dp[cnt - 1][i - n][n];
}
for (int cnt = 1; cnt <= max; ++cnt)
for (int i = 1; i <= max; ++i)
ans1[cnt][i] = dp[cnt][i][i];
for (int i = 1; i <= max; ++i)
for (int cnt = 1; cnt <= i; ++cnt)
{
int j = i - cnt * (cnt - 1) / 2;
if (j <= 0)
break;
ans2[i] += ans1[cnt][j];
}
for (int i = 1; i <= max; ++i)
for (int cnt = 1; cnt <= i; ++cnt)
{
int j = i + cnt;
if (j % 2)
continue;
j /= 2;
ans3[i] += ans1[cnt][j];
}
while (std::cin >> num)
{
std::cin >> k;
std::cout << ans1[k][num] << std::endl;
std::cout << ans2[num] << std::endl;
std::cout << ans3[num] << std::endl;
}
}
值元编程基础
元编程是指计算机程序能把其他程序作为它们的数据的编程技术。在⽬前的C++中，元编程体现为⽤代码⽣成代码，包括宏与模板。当我们使⽤了std::vector<int>中的任何⼀个名字时，std::vector 类模板就⽤模板参数int, std::allocator<int>实例化为std::vector<int, std::allocator<int>>模板类，这是⼀种元编程，
不过我们通常不这么讲。
()()()()
狭义的C++模板元编程（template metaprogramming，TMP）包括值元编程、类型元编程，以及两者的相交。本⽂讨论的是值元编程，即为编译期值编程。
在C++中有两套⼯具可⽤于值元编程：模板和constexpr。C++模板是图灵完全的，这是模板被引⼊C++以后才被发现的，并不是C++模板的初衷，因此⽤模板做计算在C++中算不上⼀等⽤法，导致其语法⽐较冗长复杂。constexpr的初衷是提供纯正的编译期常量，后来才取消对计算的限制，但不能保证计算⼀定在编译期完成。总之，这两套⼯具都不完美，所以本⽂都会涉及。
严格来说，constexpr不符合上述对元编程的定义，但它确实可以提供运⾏时程序需要的数据，所以也归⼊元编程的类别。
constexpr式值元编程
从constexpr开始讲，是因为它与我们在C++中惯⽤的编程范式——过程式范式是⼀致的。
constexpr关键字在C++11中被引⼊。当时，constexpr函数中只能包含⼀条求值语句，就是return语句，
返回值可以⽤于初始化constexpr变量，作模板参数等⽤途。如果需要分⽀语句，⽤三⽬运算符?:；如果需要循环语句，⽤函数递归实现。⽐如，计算阶乘：
constexpr int factorial(int n)
{
return n <= 1 ? 1 : (n * factorial(n - 1));
}
while语句都可以用for改写对于编译期常量i，factorial(i)产⽣编译期常量；对于运⾏时值j，factorial(j)产⽣运⾏时值，也就是说，constexpr可以视为对既有函数的附加修饰。
然⽽，多数函数不⽌有⼀句return语句，constexpr对函数体的限制使它很难⽤于中等复杂的计算任务，为此C++14放宽了限制，允许定义局部变量，允许if-else、switch-case、while、for等控制流。factorial函数可以改写为：
constexpr int factorial(int n)
{
int result = 1;
for (; n > 1; --n)
result *= n;
return result;
}
也许你会觉得factorial函数的递归版本⽐循环版本易懂，那是因为你学习递归时接触的第⼀个例⼦就是它。对于C++开发者来说，⼤多数情况下⾸选的还是循环。
计算单个constexpr值⽤C++14就⾜够了，但是传递数组需要C++17，因为std::array的operator[]从C++17开始才是constexpr的。
整数划分问题的constexpr元编程实现需要C++17标准：
#include <iostream>
#include <utility>
#include <array>
constexpr int MAX = 50;
constexpr auto calculate_ans1()
{
std::array<std::array<std::array<int, MAX + 1>, MAX + 1>, MAX + 1> dp{};
std::array<std::array<int, MAX + 1>, MAX + 1> ans1{};
constexpr int max = MAX;
for (int i = 1; i <= max; ++i)
for (int j = 1; j <= max; ++j)
dp[1][i][j] = i <= j;
for (int cnt = 2; cnt <= max; ++cnt)
for (int i = 1; i <= max; ++i)
for (int j = 1; j <= max; ++j)
{
auto min = std::min(i - 1, j);
for (int n = 1; n <= min; ++n)
dp[cnt][i][j] += dp[cnt - 1][i - n][n];
}
for (int cnt = 1; cnt <= max; ++cnt)
for (int i = 1; i <= max; ++i)
ans1[cnt][i] = dp[cnt][i][i];
return ans1;
}
constexpr auto calculate_ans2()
{
constexpr auto ans1 = calculate_ans1();
std::array<int, MAX + 1> ans2{};
constexpr int max = MAX;
for (int i = 1; i <= max; ++i)
for (int cnt = 1; cnt <= i; ++cnt)
{
int j = i - cnt * (cnt - 1) / 2;
if (j <= 0)
break;
ans2[i] += ans1[cnt][j];
}
return ans2;
}
int main()
{
constexpr auto ans1 = calculate_ans1();
constexpr auto ans2 = calculate_ans2();
for (int cnt = 1; cnt <= 10; ++cnt)
{
for (int i = 1; i <= 10; ++i)
std::cout << ans1[cnt][i] << ' ';+
std::cout << std::endl;
}
std::cout << std::endl;
for (int i = 1; i <= 50; ++i)
std::cout << ans2[i] << ' ';
std::cout << std::endl;
int num, k;
while (std::cin >> num)
{
std::cin >> k;
std::cout << ans1[k][num] << std::endl;
std::cout << ans2[num] << std::endl;
std::cout << ans2[num] << std::endl;
}
}
模板式值元编程
模板式与C++11中的constexpr式类似，必须把循环化为递归。事实上C++模板是⼀门函数式编程语⾔，对值元编程和类型元编程都是如此。
程序控制流有三种基本结构：顺序、分⽀与循环。
顺序
在函数式编程中，数据都是不可变的，函数总是接受若⼲参数，返回若⼲结果，参数和结果是不同的变量；修改原来的变量是不允许的。对于C++模板这门语⾔，函数是类模板，也称“元函数”（metafunction）；参数是模板参数；运算结果是模板类中定义的静态编译期常量（在C++11以前，常⽤enum来定义；C++11开始⽤constexpr）。
⽐如，对于参数x，计算x+1 和x2的元函数：
template<int X>
struct PlusOne
{
static constexpr int value = X + 1;
};
template<int X>
struct Square
{
static constexpr int value = X * X;
};
这⾥假定运算数的类型为int。从C++17开始，可以⽤auto声明⾮类型模板参数。
顺序结构，是对数据依次进⾏多个操作，可以⽤函数嵌套来实现：
std::cout << PlusOne<1>::value << std::endl;
std::cout << Square<2>::value << std::endl;
std::cout << Square<PlusOne<3>::value>::value << std::endl;
std::cout << PlusOne<Square<4>::value>::value << std::endl;
或者借助constexpr函数，回归熟悉的过程式范式：
template<int X>
struct SquareAndIncrease
{
static constexpr int calculate()
{
int x = X;
x = x * x;
x = x + 1;
return x;
}
static constexpr int value = calculate();
};
void f()
{
std::cout << SquareAndIncrease<5>::value << std::endl;
}
过程式⽅法同样可以⽤于分⽀和循环结构，以下省略；函数式⽅法可以相似地⽤于值元编程与类型元编程，所以我更青睐（主要还是逼格更⾼）。
分⽀
C++模板元编程实现分⽀的⽅式是模板特化与模板参数匹配，⽤⼀个额外的带默认值的bool类型模板参数作匹配规则，特化false或true的情形，另⼀种情形留给主模板。
⽐如，计算x的绝对值：
template<int X, bool Pos = (X > 0)>
struct AbsoluteHelper
{
static constexpr int value = X;
};
template<int X>
struct AbsoluteHelper<X, false>
{
static constexpr int value = -X;
};
如果你怕⽤户瞎写模板参数，可以再包装⼀层：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。