精华内容
下载资源
问答
  • 【白话经典算法系列之十随机生成和为S的N个正整数——投影法 随机生成和为S的N个正整数有很多种解法。下面讲解一种比较高效且比较有趣味性的解法——投影法。 以生成和为20的4个数为例,可以先生成随机生成0到...

    【白话经典算法系列之十三】随机生成和为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.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;
    }

    运算结果如下图所示:

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

     

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

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

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

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

     

    展开全文
  • 随机生成和为S的N个正整数——投影法   随机生成和为S的N个正整数有很多种解法。下面讲解一种比较高效且比较有趣味性的解法——投影法。  以生成和为20的4个数为例,可以先生成随机生成0到20之间的三个数字再...

    随机生成和为S的N个正整数——投影法 

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

        以生成和为204个数为例,可以先生成随机生成020之间的三个数字再排序,假设得到了4718。然后在X-Y数轴上画出这三个数,如下图:

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

    由图很容易看出ABBCCDDE这四段的长度和肯定为20。因此ABBCCDDE这四段的长度即和为204个数,这4个数分别为43112

     

    这种方法只要随机生成N - 1个小于S的不同数字,排序后计算两两差值就可以得到和为SN个正整数,因此效率还是比较高的。下面给出完整代码(随机生成N - 1个不同数可以参考《STL系列十一随机三趣题——随机重排,文件中随机取一行,生成N个随机数》):

    1. #include <cstdio>  
    2. #include <ctime>  
    3. #include <set>  
    4. #include <algorithm>  
    5. using namespace std;  
    6. //在[s, e)区间上随机取n个数并存放到a[]中  
    7. void GetRandomNum(int *a, int n, int s, int e)  
    8. {  
    9.     std::set<int> set_a;  
    10.     srand(time(NULL));  
    11.     for (int i = e - n; i < e; i++)  
    12.     {  
    13.         int num = (rand() % i) + s;  
    14.         if (set_a.find(num) == set_a.end())  
    15.             set_a.insert(num);  
    16.         else  
    17.             set_a.insert(i);  
    18.     }  
    19.     i = 0;  
    20.     std::set<int>::iterator pos;  
    21.     for (pos = set_a.begin(); pos != set_a.end(); pos++)  
    22.         a[i++] = *pos;  
    23. }  
    24. int main()  
    25. {  
    26.     const int NSUM = 20;  
    27.     const int NCOUNT = 4;  
    28.       
    29.     printf("           生成和为%d的%d个数 \n", NSUM, NCOUNT);  
    30.     printf("--- by MoreWindows( http://blog.csdn.net/MoreWindows )  ---\n\n");    
    31.       
    32.     int    a[NCOUNT];  
    33.       
    34.     GetRandNumberInRange(a, NCOUNT - 1, 0, NSUM);  
    35.     sort(a, a + NCOUNT - 1);  
    36.     a[NCOUNT - 1] = NSUM;  
    37.   
    38.     printf("  已经生成和为%d的%d个数: \n", NSUM, NCOUNT);  
    39.     printf("%d ", a[0]);  
    40.     for (int i = 1; i < NCOUNT; i++)  
    41.         printf("%d ", a[i] - a[i - 1]);  
    42.     putchar('\n');  
    43.     return 0;  

    展开全文
  • 【白话经典算法系列之十随机生成和为S的N个正整数——投影法 随机生成和为S的N个正整数有很多种解法。下面讲解一种比较高效且比较有趣味性的解法——投影法。 以生成和为20的4个数为例,可以先生成随机生成0到...

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

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

        以生成和为204个数为例,可以先生成随机生成020之间的三个数字再排序,假设得到了4718。然后在X-Y数轴上画出这三个数,如下图:

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

    由图很容易看出ABBCCDDE这四段的长度和肯定为20。因此ABBCCDDE这四段的长度即和为204个数,这4个数分别为43112

     

    这种方法只要随机生成N - 1个小于S的不同数字,排序后计算两两差值就可以得到和为SN个正整数,因此效率还是比较高的。下面给出完整代码(随机生成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.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;
    }
    

    运算结果如下图所示:

     

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

     

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

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

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

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

     

    欢迎大家讨论新颖的解法^_^,多多交流,开阔思路。

     

     

    《白话经典算法系列》专栏地址:http://blog.csdn.net/morewindows/article/category/859207

    转载请标明出处,原文地址:

    欢迎关注微博:http://weibo.com/MoreWindows


     

    展开全文
  • 【白话经典算法系列之十随机生成和为S的N个正整数 投影法

    分享一下我老师大神的人工智能教程!零基础,通俗易懂!http://blog.csdn.net/jiangjunshow

    也欢迎大家转载本篇文章。分享知识,造福人民,实现我们中华民族伟大复兴!

                   

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

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

        以生成和为204个数为例,可以先生成随机生成020之间的三个数字再排序,假设得到了4718。然后在X-Y数轴上画出这三个数,如下图:

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

    由图很容易看出ABBCCDDE这四段的长度和肯定为20。因此ABBCCDDE这四段的长度即和为204个数,这4个数分别为43112

     

    这种方法只要随机生成N - 1个小于S的不同数字,排序后计算两两差值就可以得到和为SN个正整数,因此效率还是比较高的。下面给出完整代码(随机生成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 = 0std::set<int>::iterator pos; for (pos = set_a.begin(); pos != set_a.end(); pos++)  a[i++] = *pos;}int main()const int NSUM = 20const 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;}

    运算结果如下图所示:

     

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

     

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

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

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

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

     

    欢迎大家讨论新颖的解法^_^,多多交流,开阔思路。

     

     

    《白话经典算法系列》专栏地址:http://blog.csdn.net/morewindows/article/category/859207

    转载请标明出处,原文地址:

    欢迎关注微博:http://weibo.com/MoreWindows


     

               

    给我老师的人工智能教程打call!http://blog.csdn.net/jiangjunshow

    这里写图片描述
    展开全文
  • 【白话经典算法系列之十随机生成和为S的N个正整数——投影法 分类: 白话经典算法系列 Windows编程2013-01-04 13:46 2459人阅读 评论(17) 收藏 举报 白话经典算法和为S的N个正整数投影法随机...
  • 【白话经典算法系列之十随机生成和为S的N个正整数——投影法   随机生成和为S的N个正整数有很多种解法。下面讲解一种比较高效且比较有趣味性的解法——投影法。  以生成和为20的4个数为例,可以先生成随机...
  • VB程序题:利用实验C的思想,随机产生3整数,按从小到大的顺序显示...Randomize '加上这句,每次产生随机数的第一次就不会总出现相同的数x = Int(Rnd * 901 + 100) '随机产生一个三正整数y = Int(Rnd * 901 + 1...
  • N个正整数随机排列

    千次阅读 2017-08-10 12:22:49
    这次我们要生成前N个正整数的一个随机排列 书中给出种算法如下: 前提:需要一个随机数生成函数randInt(begin,end),生成从begin 到 end 的随机数 算法一:  依次填入a[0]到a[n-1]的数组a,每次都不断...
  • 【白话经典算法系列之十随机生成和为S的N个正整数——投影法   随机生成和为S的N个正整数有很多种解法。下面讲解一种比较高效且比较有趣味性的解法——投影法。  以生成和为20的4个数为例,可以先生成...
  • 【白话经典算法系列之十随机生成和为S的N个正整数——投影法 http://blog.csdn.net/morewindows/article/details/8439393 觉得思路挺好的。 参考这种思想,实现了Java版的随机生成和为S的N个正整数。 ...
  • 题设:定义一类,该类中有一整型数组,类中定义一方法随机生成元素值为正整数的数组并求出其中的水仙花数,数组的元素的个数由参数指定。定义一参数为整数类型的构造函数初始化数组元素数。编写...
  • 用c++随机生成10小学生算术题的课设

    千次阅读 2019-12-28 14:36:50
    面向小学1~2年级学生,随机选择两个整数和加减法形成算式要求学生解答。 功能要求: (1)电脑随机出10道题,每题10分,程序结束时显示学生得分; (2)确保算式没有超出12年级的水平,只允许进行50以内的加减法,不...
  • 今天上班的时候网上看到题目很简单,题目是这样的:给定一个正整数n,需要输出一个长度为n的数组,数组元素是随机数,范围为0 – n-1,且元素不能重复。比如 n = 3 时,需要获取一个长度为3的数组,元素范围为0-2;...
  • 文章目录给你一生成1到5随机数的函数,用它写一函数生成1到7的随机数一、问题二、分析、错解四、解一五、解二六、拓展 一、问题 已知rand5()产生1-5的随机整数,利用该函数生成函数rand7()产生1-7的随机...

空空如也

空空如也

1 2 3 4 5 6
收藏数 101
精华内容 40
关键字:

随机生成三个正整数