白话经典算法系列之十三随机生成和为S的N个正整数——投影法

た入场券 2023-06-18 07:57 58阅读 0赞

### **【白话经典算法系列之十三】随机生成和为S的N个正整数——投影法** ###

随机生成和为S的N个正整数有很多种解法。下面讲解一种比较高效且比较有趣味性的解法——投影法。

以生成和为20的4个数为例，可以先生成随机生成0到20之间的三个数字再排序，假设得到了4，7，18。然后在X-Y数轴上画出这三个数，如下图：

![format_png][]

然后将这些数值投影到Y轴上，可得下图：

![format_png 1][]

由图很容易看出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个随机数][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.csdn.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;
    }

运算结果如下图所示：

![format_png 2][]

这种“投影法”能有效解决随机生成和为S的N个正整数，其算法本质是**通过“投影”得到各数据之间的长度差，而且这些长度差之和即投影线段的总长度显然会等于最大数据的值减去最小数据的值**。

下面分析下算法的时间复杂度：

算法分为生成随机的N-1个数+排序+遍历共费时O(N \* logN) +O(N \* logN) + O(N)，整体时间复杂度为O(N \* logN)。

算法的最主要费时操作在排序上，如果数据量不是太大，使用基数排序（见[《【白话经典算法系列之十】一道有趣的GOOGLE面试题解法》][GOOGLE]）可以将排序操作的时间复杂度降低到O(N)。

其次在生成随机的N-1个数时，虽然只要调用rand()随机函数N-1次，但由于使用了set来做数据存储的容器，因此每次插入数据前的查找要费时O(logN)，插入新数据时也要费时O(logN)，可以改用hast\_set来进一步提高效率（见《[STL系列之六 set与hash\_set][STL_ set_hash_set]》）。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEyMTIvMjYvMTM1NjUwODA0NV84NTMxLlBORw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEyMTIvMjYvMTM1NjUwODA2MF8yMTk4LlBORw?x-oss-process=image/format,png
[STL_N]: http://blog.csdn.net/morewindows/article/details/7659532
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEyMTIvMjYvMTM1NjUwODE1OF8xNDYyLlBORw?x-oss-process=image/format,png
[GOOGLE]: https://blog.csdn.net/rocling/article/details/103333553
[STL_ set_hash_set]: http://blog.csdn.net/morewindows/article/details/7029587