如果给你一个问题：“随机产生和为S的N个正整数”， 你会如何做呢？
针对该问题，解决的方法有很多种。在这篇文章中，我将为大家给出两种比较好理解的解决方法：一个是“尺子法”；另外一个是“锯木头法”。 (名字随便取的，主要是方便理解用)。
方法一：尺子法
思想：将给定值S看成一个尺子的长度，那么，生成N个和为S的正整数的问题就变成在尺子中寻找出N-1个不同的刻度，加上最小刻度0和最大刻度S， 一共有N+1个刻度。然后，从小到大，计算出相邻刻度的长度，这些长度就可以认为是随机的，因为尺子中产生的N-1个刻度是随机的。
有了上述思想，我们只要如下三个步骤就能完成这个功能。
- 验证参数S和N的正确性
- 尺子中产生N-1个不同刻度
- 计算相邻刻度之间的值
/***
* <p>
* 随机产生和为sum(如10)的num(如5)个正整数
* </p>
*
* @param num
* 期望产生的随机数个数
* @param sum
* 所有产生随机数的和
* @return 返回满足和为sum的num个随机正整数组成的数组
*/
public Integer[] random(int num, int sum) {
/**
* Step1: 验证参数正确性
*/
if (num < 1) {
throw new IllegalArgumentException("产生随机数个数的num不能小于1");
}
if (sum < num) {
throw new IllegalArgumentException("产生随机数个数的num不能大于和sum");
}
if (sum <= 0) {
throw new IllegalArgumentException("sum需要为正整数");
}
/**
* Step2: 0~sum之间随机产生num-1个不同的刻度
*/
Random rand = new Random();
Set<Integer> locations = new TreeSet<>();
while (locations.size() < num - 1) {
locations.add(rand.nextInt(sum - 1) + 1);
}
locations.add(0);
locations.add(sum);
/**
* Step3: 计算出相邻刻度的差，计算出来的长度就可以代表一个随机数
*/
Integer[] locationsArray = locations.toArray(new Integer[] {});
Integer[] resultArray = new Integer[num];
for (int i = 0; i < num; i++) {
resultArray[i] = locationsArray[i + 1] - locationsArray[i];
}
return resultArray;
}
方法二：锯木头法
思想：锯木头法的思想则是将S看成木头的长度，随机产生和为S的N个正整数的问题转换成锯N-1次木头，将产生N段小木头，N段的小木头其长度和就是S。
有了上述思想，我们便可以通过如下几个步骤实现该方法：
- 验证参数S和N的正确性
- 锯N-1次木头
在锯木头的时候，需要考虑可锯的长度。
/***
* <p>
* 随机产生和为sum(如10)的num(如5)个正整数
* </p>
*
* @param num
* 期望产生的随机数个数
* @param sum
* 所有产生随机数的和
* @return 返回满足和为sum的num个随机正整数组成的数组
*/
public int[] random2(int num, int sum) {
/**
* Step1: 验证参数正确性
*/
if (num < 1) {
throw new IllegalArgumentException("产生随机数个数的num不能小于1");
}
if (sum < num) {
throw new IllegalArgumentException("产生随机数个数的num不能大于和sum");
}
if (sum <= 0) {
throw new IllegalArgumentException("sum需要为正整数");
}
/**
* 如果只有一个 直接返回
*/
if (num == 1) {
return new int[] { sum };
}
/**
* Step2: 锯木头的方法
*/
Random rand = new Random();
int[] randomNumbers = new int[num];
// 剩余数
int remainingNum = sum;
for (int i = 0; i < num - 1; i++) {
/**
* 可以锯掉可选值
* remaining - (num - (i+1)) + 1 = remainingNum - num + i + 1
*/
int randNum = rand.nextInt(remainingNum - num + i + 1) + 1;
remainingNum -= randNum;
randomNumbers[i] = randNum;
}
/**
* 最后一个直接赋值即可
*/
randomNumbers[num - 1] = remainingNum;
return randomNumbers;
}
详细代码及某次测试运行结果如下：
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
/**
* @author wangmengjun
*
*/
public class RandomExample_1 {
/***
* <p>
* 随机产生和为sum(如10)的num(如5)个正整数
* </p>
*
* @param num
* 期望产生的随机数个数
* @param sum
* 所有产生随机数的和
* @return 返回满足和为sum的num个随机正整数组成的数组
*/
public Integer[] random(int num, int sum) {
/**
* Step1: 验证参数正确性
*/
if (num < 1) {
throw new IllegalArgumentException("产生随机数个数的num不能小于1");
}
if (sum < num) {
throw new IllegalArgumentException("产生随机数个数的num不能大于和sum");
}
if (sum <= 0) {
throw new IllegalArgumentException("sum需要为正整数");
}
/**
* Step2: 0~sum之间随机产生num-1个不同的刻度
*/
Random rand = new Random();
Set<Integer> locations = new TreeSet<>();
while (locations.size() < num - 1) {
locations.add(rand.nextInt(sum - 1) + 1);
}
locations.add(0);
locations.add(sum);
/**
* Step3: 计算出相邻刻度的差，计算出来的长度就可以代表一个随机数
*/
Integer[] locationsArray = locations.toArray(new Integer[] {});
Integer[] resultArray = new Integer[num];
for (int i = 0; i < num; i++) {
resultArray[i] = locationsArray[i + 1] - locationsArray[i];
}
return resultArray;
}
/***
* <p>
* 随机产生和为sum(如10)的num(如5)个正整数
* </p>
*
* @param num
* 期望产生的随机数个数
* @param sum
* 所有产生随机数的和
* @return 返回满足和为sum的num个随机正整数组成的数组
*/
public int[] random2(int num, int sum) {
/**
* Step1: 验证参数正确性
*/
if (num < 1) {
throw new IllegalArgumentException("产生随机数个数的num不能小于1");
}
if (sum < num) {
throw new IllegalArgumentException("产生随机数个数的num不能大于和sum");
}
if (sum <= 0) {
throw new IllegalArgumentException("sum需要为正整数");
}
/**
* 如果只有一个 直接返回
*/
if (num == 1) {
return new int[] { sum };
}
/**
* Step2: 锯木头的方法
*/
Random rand = new Random();
int[] randomNumbers = new int[num];
// 剩余数
int remainingNum = sum;
for (int i = 0; i < num - 1; i++) {
/**
* 可以锯掉可选值
* remaining - (num - (i+1)) + 1 = remainingNum - num + i + 1
*/
int randNum = rand.nextInt(remainingNum - num + i + 1) + 1;
remainingNum -= randNum;
randomNumbers[i] = randNum;
}
/**
* 最后一个直接赋值即可
*/
randomNumbers[num - 1] = remainingNum;
return randomNumbers;
}
}
import java.util.Arrays;
/**
* @author wangmengjun
*
*/
public class Main {
public static void main(String[] args) {
RandomExample_1 example1 = new RandomExample_1();
int num = 6;
int sum = 30;
System.out.println(String.format("随机产生和为%d的%d个正整数", sum, num));
for (int i = 1; i <= 10; i++) {
System.out.println(String.format("第%d遍random()产生结果 -- %s", i,
Arrays.toString(example1.random(num, sum))));
System.out.println(String.format("第%d遍random2()产生结果 -- %s", i,
Arrays.toString(example1.random2(num, sum))));
}
}
}
随机产生和为30的6个正整数
第1遍random()产生结果 -- [2, 4, 4, 6, 5, 9]
第1遍random2()产生结果 -- [24, 1, 2, 1, 1, 1]
第2遍random()产生结果 -- [6, 4, 1, 1, 6, 12]
第2遍random2()产生结果 -- [17, 1, 5, 5, 1, 1]
第3遍random()产生结果 -- [1, 15, 1, 6, 3, 4]
第3遍random2()产生结果 -- [2, 4, 1, 7, 9, 7]
第4遍random()产生结果 -- [16, 1, 1, 4, 5, 3]
第4遍random2()产生结果 -- [11, 4, 6, 5, 1, 3]
第5遍random()产生结果 -- [4, 4, 6, 7, 4, 5]
第5遍random2()产生结果 -- [6, 13, 1, 3, 6, 1]
第6遍random()产生结果 -- [10, 1, 16, 1, 1, 1]
第6遍random2()产生结果 -- [18, 7, 2, 1, 1, 1]
第7遍random()产生结果 -- [4, 1, 10, 8, 2, 5]
第7遍random2()产生结果 -- [8, 6, 6, 4, 3, 3]
第8遍random()产生结果 -- [1, 6, 3, 8, 1, 11]
第8遍random2()产生结果 -- [4, 7, 3, 7, 2, 7]
第9遍random()产生结果 -- [3, 5, 13, 3, 1, 5]
第9遍random2()产生结果 -- [13, 4, 1, 4, 2, 6]
第10遍random()产生结果 -- [4, 5, 12, 3, 3, 3]
第10遍random2()产生结果 -- [17, 3, 7, 1, 1, 1]
相关推荐
1.5.6. 输入两个整数 n 和 m，从数列 1，2，3.......n 中 随意取几个数 ....... 116 1.5.7. 输入一个表示整数的字符串，把该字符串转换成整数并输出.............. 118 1.5.8. 给出一个数列，找出其中最长的单调...
输入一个正整数n (1<n)，再输入n 个整数，将最小值与第一个数交换，最大值与最后一个数交换，然后输出交换后的n 个数。 （25）抓住肇事者 一辆卡车违反交通规则，撞人后逃跑。现场共有三个目击者，但都没有记住车号...
第2行有N个用空格隔开的正整数，为所产生的随机数。 输出格式 输出也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。 p.s.c#实现，输出一...
验证非正整数（负整数 + 0） ^((-\d+)|(0+))$ 验证长度为3的字符：^.{3}$ 验证由26个英文字母组成的字符串：^[A-Za-z]+$ 验证由26个大写英文字母组成的字符串：^[A-Z]+$ 验证由26个小写英文字母组成的字符串：^...
6.22 如何在一个文件中判断声明为extern的数组的大小(例如，数组定义和大小在另一个文件中)？sizeof操作符似乎不行。 6.23 sizeof返回的大小是以字节计算的，怎样才能判断数组中有多少个元素呢？ 第7章 内存...
TSP问题的遗传算法设计与实现 （１）编码问题：由于这是⼀个离散型的问题，我们采⽤整数编码的⽅式，⽤1－ｎ来表⽰n个城市，1－n的任意⼀个排列就构成了问 题的⼀个解。可以知道，对于n个城市的TSP问题，⼀共有n!种...
例如定义一个包含N个指向返回指向字符的指针的函数的指针的数组？ 11 1.22 如何声明返回指向同类型函数的指针的函数?我在设计一个状态机，用函数表示每种状态，每个函数都会返回一个指向下一个状态的函数的指针...
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行每行包括三个正整数m、s、t。m表示家长的序号，s、t分别表示该家长空闲时 间段的起始时间和终止时间，s小于t。注意两个数字的最后两位表示分钟。 比如1645 表示16时45分 样本如下： 6 1 800 1100 2 800 ...
结构化程序设计由于采用了模块分解与功能抽象，自顶向下、分而治之的方法，从而有效地将一个较复杂的程序系统设计任务分解成许多易于控制和处理的子任务，便于开发和维护。 虽然结构化程序设计方法具有很多的优点，...
其中 n为正整数，则最后一行的语句频度在最坏情况下是（D ） 郴州都市网 www.0735.cc郴州人才网 www.CZHR.com www.989.org 《数据结构 1800题》 A. O（n） B. O(nlogn) C. O(n3) D. O(n2) 【南京理工大学 ...
特点：将 a 和 b 先转换为二进制，按位操作，对应位置上的两个数字，相同时，该位整体结果为0，不同时，该位的整体结果为 1 使用场合：快速交换两个数字 5 ^ 3 101 011 ========== 110 结果为 6 练习： ...
RSA RSA_Encryption_Algorithm 使用python实现RSA加密算法 RSA加密过程： 1.随机生成两个大质数p...5.工业标准的私钥d一般是2048位的正整数,故n的取值也是2000位左右的十进制整数,意味着 p 和 q这两个质数以及也是接近1
的连续正整数序列 和为 S 的两个数字 N 数之和 三数之和 二维数组 构建乘积数组 顺时针打印矩阵 数据统计 数组中出现次数超过数组长度一半的数字 第一个只出现一次的字符 连续子数组的最大和 扑克牌顺子 字符串 表示...
其中FILE应为大写，它实际上是由系统定义的一个结构， 该结构中含有文件名、文件状态和文件当前位置等信息。 在编写源程序时不必关心FILE结构的细节。例如：FILE *fp； 表示fp是指向FILE结构的指针变量，通过fp ...
例如定义一个包含N 个指向返 回指向字符的指针的函数的指针的数组？ . . . . . . . . . . . . . . 3 1.8 函数只定义了一次, 调用了一次, 但编译器提示非法重定义了。. . 4 1.9 main() 的正确定义是什么？ void main...
与开发人员在测试组环境多次重复以上步骤，发现11群的计次表话单有时正常，有时其出中继群号就为一个随机值，发生异常的频率比较高。为什么其它群的话单正常，唯独11群不正常呢？11群是四个群中最小的群，其中继计...