随机生成和为S的N个正整数
随机生成和为S的N个正整数——投影法
随机生成和为S的N个正整数有很多种解法。下面讲解一种比较高效且比较有趣味性的解法——投影法。
以生成和为20的4个数为例，可以先生成随机生成0到20之间的三个数字再排序，假设得到了4，7，18。然后在X-Y数轴上画出这三个数，如下图：
然后将这些数值投影到Y轴上，可得下图：
由图很容易看出AB，BC，CD，DE这四段的长度和肯定为20。因此AB，BC，CD，DE这四段的长度即和为20的4个数，这4个数分别为4，3，11，2。
这种方法只要随机生成N - 1个小于S的不同数字，排序后计算两两差值就可以得到和为S的N个正整数，因此效率还是比较高的。下面给出完整代码（随机生成N - 1个不同数可以参考《STL系列十一随机三趣题——随机重排，文件中随机取一行，生成N个随机数》）：
- #include <cstdio>
- #include <ctime>
- #include <set>
- #include <algorithm>
- using namespace std;
- //在[s, e)区间上随机取n个数并存放到a[]中
- void GetRandomNum(int *a, int n, int s, int e)
- {
- std::set<int> set_a;
- srand(time(NULL));
- for (int i = e - n; i < e; i++)
- {
- int num = (rand() % i) + s;
- if (set_a.find(num) == set_a.end())
- set_a.insert(num);
- else
- set_a.insert(i);
- }
- i = 0;
- std::set<int>::iterator pos;
- for (pos = set_a.begin(); pos != set_a.end(); pos++)
- a[i++] = *pos;
- }
- int main()
- {
- const int NSUM = 20;
- const int NCOUNT = 4;
- printf(" 生成和为%d的%d个数 \n", NSUM, NCOUNT);
- printf("--- by MoreWindows( http://blog.****.net/MoreWindows ) ---\n\n");
- int a[NCOUNT];
- GetRandNumberInRange(a, NCOUNT - 1, 0, NSUM);
- sort(a, a + NCOUNT - 1);
- a[NCOUNT - 1] = NSUM;
- printf(" 已经生成和为%d的%d个数: \n", NSUM, NCOUNT);
- printf("%d ", a[0]);
- for (int i = 1; i < NCOUNT; i++)
- printf("%d ", a[i] - a[i - 1]);
- putchar('\n');
- return 0;
- }