头脑体操,用程序给闺女出算数题——我的头脑体操

闺女上一年级，放假了，老师要求假期里每天做20道100以内加减法的算术题。我一想，这好几十天，每天出20道，时间长了也够烦的。再说出出来的题，也不一定各种题目都能出到。干脆编个程序，自动出题得了。于是，程序的需求归纳为：

随机生成N道M以内非负整数加减法的算术题，题目应该在概率上均匀分布。

（注：以下C++代码在VS2008上调试运行通过）

准备：
为了将分布情况可视化，需要一个分布统计的类DistributionStatistic（见下），来记录2个加数和和，或者被减数、减数和差出现的次数等。每当显示出分布数据时，将其拷到Excel里，让Excel画出分布图。
DistributionStatistic类代码class DistributionStatistic { public: DistributionStatistic(int nDistributionCount): m_nDistributionCount(nDistributionCount), m_nCount(0) { assert(nDistributionCount > 0); m_pDistributionParam1 = new int[nDistributionCount]; m_pDistributionParam2 = new int[nDistributionCount]; m_pDistributionResult = new int[nDistributionCount]; memset(m_pDistributionParam1, 0, sizeof(int) * nDistributionCount); memset(m_pDistributionParam2, 0, sizeof(int) * nDistributionCount); memset(m_pDistributionResult, 0, sizeof(int) * nDistributionCount); } virtual ~DistributionStatistic(void) { delete[] m_pDistributionParam1; delete[] m_pDistributionParam2; delete[] m_pDistributionResult; } void DoStatistic(int param1, int param2, int result) { assert(param1 >= 0 && param1 < m_nDistributionCount); assert(param2 >= 0 && param2 < m_nDistributionCount); assert(result >= 0 && result < m_nDistributionCount); m_pDistributionParam1[param1]++; m_pDistributionParam2[param2]++; m_pDistributionResult[result]++; m_nCount++; } void Output(int nNum) { printf("\nCount: %d/%d\n\n", m_nCount, nNum); for (int i = 0; i < m_nDistributionCount; i++) { printf("%d:\t%d\t%d\t%d\n", i, m_pDistributionParam1[i], m_pDistributionParam2[i], m_pDistributionResult[i]); } } private: int m_nDistributionCount; int * m_pDistributionParam1; int * m_pDistributionParam2; int * m_pDistributionResult; int m_nCount; };
下面开始编写生成算术题的代码。先设置2个常整数M（缺省为100）和N（为了分布统计，得整大点，缺省为10000），见下。


常量声明及初始化const int M = 100; const int N = 10000;

另外，还要先写个产生[range_min, range_max]范围内随机数的函数Random，以便调用。

Random函数代码int Random(int range_min, int range_max) { return (int)((double)rand() / (RAND_MAX + 1) * (range_max + 1 - range_min) + range_min); }
做法一：
最直接的想法，随机生成2个[0, M]之间的数x和y。对于加法，如果其和不超过M，则采用，否则舍弃；对于减法，用大的那个数减去小的那个数。但是按照概率，加法有50%被舍弃，所以出出来的题，加法和减法的比率约为1:2，不满足均匀分布。所以对于减法，当第一个数x小于第二个数y的时候，也舍弃。这样可以达到概率上加法和减法比率为1:1。代码见下。

做法一代码void Method1() { DistributionStatistic dsAddition(M + 1); DistributionStatistic dsSubstraction(M + 1); int i = 0; while (i < N) { int bAddition = (rand() % 2) == 0; int x = Random(0, M); int y = Random(0, M); if (bAddition) { if (x + y <= 100) { printf(" %d + %d = %d\n", x, y, x + y); i++; dsAddition.DoStatistic(x, y, x + y); } } else { if (x >= y) { printf(" %d - %d = %d\n", x, y, x - y); i++; dsSubstraction.DoStatistic(x, y, x - y); } } } dsAddition.Output(N); dsSubstraction.Output(N); printf("\nMethod1:\n"); }
以加法为例，2个加数和和的分布情况如下（横坐标为题目中的数值0-100，纵坐标为对应数值出现的次数）。



虽然能解决问题，但毕竟做法一有舍弃50%的情况，效率低。所以改进成做法二。

做法二：
对于加法，第一个数x生成范围不变（仍是[0, M]），第二个数y随机生成的范围变为[0, M-x]，以保证x与y的和不会超过M（这样就不会有舍弃的情况）；而对于减法，第二个数y随机生成的范围变为[0, x]，以保证x与y的差不会是负数（这样也不会有舍弃的情况）。代码见下。

做法二代码void Method2() { DistributionStatistic dsAddition(M + 1); for (int i = 0; i < N; i++) { bool bAddition = (rand() % 2) == 0; if (bAddition) { int x = Random(0, M); int y = Random(0, M - x); printf(" %d + %d = %d\n", x, y, x + y); dsAddition.DoStatistic(x, y, x + y); } else { int x = Random(0, M); int y = Random(0, x); printf(" %d - %d = %d\n", x, y, x - y); } } dsAddition.Output(N); printf("\nMethod2:\n"); }
但是题目分布情况好像有点问题，跟做法一不同，做法二加法的分布图如下。



直观地想想，和为100的题目包括：0+100，1+99，……，100+0，共101种；和为99的共100种，和为98的共99种，以此类推，和为0的为1种。所以如果题目均匀分布的时候，和的分布数据应该是等差的，即是线性变化的，不应该画出这种非线形的图形。造成这种非线形分布曲线的原因，就是由于第二个数以第一个数为基础生成的。看来前2种做法各有缺点，得再找出一种即没有舍弃的情况，又能均匀分布的做法。

做法三：
假设M=100，所有M以内非负整数加法的题目见如下三角形表格：

100+0
99+0
99+1
98+0
98+1
98+2
…
…
…
…
2+0
…
…
…
2+98
1+0
1+1
…
…
1+98
1+99
0+0
0+1
0+2
…
0+98
0+99
0+100


它们的总个数应该是：

所以，基本的思路是：为每道题设置一个索引值（比如0+0索引为0，0+1索引为1，0+100索引为100，1+0索引为101，以此类推），然后随机生成一个[0, S-1]随机数r，将其作为索引值，找到其对应的题目。
从索引值r转换到对应题目的2个加数（x和y），稍微有点麻烦。转换公式为：


约束条件为：


所以在代码实现中，x从0循环到M，每次计算出y，一旦y满足约束条件，则x+y即为r对应的题目。

减法与加法类似，转换公式为：


约束条件为：


在代码中，x从0循环到M，每次计算出y，如果y满足约束条件，则x-y即为r对应的题目。整个做法三的代码如下。

做法三代码void Method3() { DistributionStatistic dsAddition(M + 1); int nSum = (M + 2) * (M + 1) / 2; printf(" Sum: %d\n", nSum); for (int i = 0; i < N; i++) { int r = Random(0, nSum - 1); bool bAddition = (rand() % 2) == 0; if (bAddition) { int s; int x; for (x = 0; x <= M; x++) { s = (2 * M + 3 - x) * x / 2; if (r - s <= M - x) break; } int y = r - s; printf(" %d + %d = %d\n", x, y, x + y); dsAddition.DoStatistic(x, y, x + y); } else { int s; int x; for (x = 0; x <= M; x++) { s = (x + 1) * x / 2; if (r - s <= x) break; } int y = r - s; printf(" %d - %d = %d\n", x, y, x - y); } } dsAddition.Output(N); printf("\nMethod3:\n"); }
此做法的分布图如下。



此做法虽然解决了前2种做法的问题，但是它又出现一个新问题，即x的循环造成生成每道题的时间复杂度从O(1)变为O(M)。所以效率上还需要提高，于是基于这一做法，进行一些改进，实现做法四。

做法四：
将做法三的加法题目的三角形表格和减法题目的三角形表格相扣，生成一个矩形表格，见下。

100+0
100-100
100-99
100-98
…
100-2
100-1
100-0
99+0
99+1
99-99
99-98
…
…
99-1
99-0
98+0
98+1
98+2
98-98
…
…
…
98-0
…
…
…
…
…
…
…
…
2+0
…
…
…
2+98
2-2
2-1
2-0
1+0
1+1
…
…
1+98
1+99
1-1
1-0
0+0
0+1
0+2
…
0+98
0+99
0+100
0-0


题目的总个数是（假设M=100）：


这时，从[0, S-1]随机数r转换为x、y和加减运算符就比较简单了（直接计算，无需循环）。如下：
x = r / (M+2)
y1 = r % (M+2)
如果x+y1<=M，则y=y1，题目为x+y；否则y=M+1-y1，题目为x-y。代码如下。

做法四代码void Method4() { DistributionStatistic dsAddition(M + 1); int nSum = (M + 2) * (M + 1); for (int i = 0; i < N; i++) { int r = Random(0, nSum - 1); int x = r / (M + 2); int y1 = r % (M + 2); int y; if (x + y1 <= M) { y = y1; printf(" %d + %d = %d\n", x, y, x + y); dsAddition.DoStatistic(x, y, x + y); } else { y = M + 1 - y1; printf(" %d - %d = %d\n", x, y, x - y); } } dsAddition.Output(N); printf("\nMethod4:\n"); }
做法四解决了前三种做法的几个问题，应该说无论从均匀分布上，还是效率上，都是最好的。

这个问题应该说比较简单，用到的只是些中学数学的知识。本人一直使用“做法”，而避免使用“算法”这个词，为的是避免自己觉得像是在作算法研究。赋闲在家，头脑不免变得迟钝，为了避免人们所说的“头脑动脉硬化症”，经常思考思考生活中的小问题，保持头脑灵活，不让其“生锈”。这不，给闺女出题，变成了我的头脑体操。

延伸阅读