随机生成和为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;
- }
相关推荐
第2行有N个用空格隔开的正整数,为所产生的随机数。 输出格式 输出也是2行,第1行为1个正整数M,表示不相同的随机数的个数。第2行为M个用空格隔开的正整数,为从小到大排好序的不相同的随机数。 p.s.c#实现,输出一...
输入一个正整数n (1<n),再输入n 个整数,将最小值与第一个数交换,最大值与最后一个数交换,然后输出交换后的n 个数。 (25)抓住肇事者 一辆卡车违反交通规则,撞人后逃跑。现场共有三个目击者,但都没有记住车号...
6.22 如何在一个文件中判断声明为extern的数组的大小(例如,数组定义和大小在另一个文件中)?sizeof操作符似乎不行。 6.23 sizeof返回的大小是以字节计算的,怎样才能判断数组中有多少个元素呢? 第7章 内存...
例如定义一个包含N个指向返回指向字符的指针的函数的指针的数组? 11 1.22 如何声明返回指向同类型函数的指针的函数?我在设计一个状态机,用函数表示每种状态,每个函数都会返回一个指向下一个状态的函数的指针...
RSA RSA_Encryption_Algorithm 使用python实现RSA加密算法 RSA加密过程: 1.随机生成两个大质数p...5.工业标准的私钥d一般是2048位的正整数,故n的取值也是2000位左右的十进制整数,意味着 p 和 q这两个质数以及也是接近1
特点:将 a 和 b 先转换为二进制,按位操作,对应位置上的两个数字,相同时,该位整体结果为0,不同时,该位的整体结果为 1 使用场合:快速交换两个数字 5 ^ 3 101 011 ========== 110 结果为 6 练习: ...
12、输入一个数据n,计算斐波那契数列(Fibonacci)的第n个值 1 1 2 3 5 8 13 21 34 规律:一个数等于前两个数之和 //计算斐波那契数列(Fibonacci)的第n个值 public class Fibonacci{ public static void main...
为此,LINGO为用户提供了两个可选部分:输入集成员和数据的数据部分(Data Section)和为决策变量设置初始值的初始部分(Init Section)。 3.1 模型的数据部分 3.1.1 数据部分入门 数据部分提供了模型相对静止部分...
例如定义一个包含N 个指向返 回指向字符的指针的函数的指针的数组? . . . . . . . . . . . . . . 3 1.8 函数只定义了一次, 调用了一次, 但编译器提示非法重定义了。. . 4 1.9 main() 的正确定义是什么? void main...