随机产生和为S的N个正整数

如果给你一个问题:“随机产生和为S的N个正整数”, 你会如何做呢?

 

针对该问题,解决的方法有很多种。在这篇文章中,我将为大家给出两种比较好理解的解决方法:一个是“尺子法”;另外一个是“锯木头法”。 (名字随便取的,主要是方便理解用)。

 

方法一:尺子法

 

思想:将给定值S看成一个尺子的长度,那么,生成N个和为S的正整数的问题就变成在尺子中寻找出N-1个不同的刻度加上最小刻度0和最大刻度S 一共有N+1个刻度然后,从小到大,计算出相邻刻度的长度,这些长度就可以认为是随机的,因为尺子中产生的N-1个刻度是随机的。

有了上述思想,我们只要如下三个步骤就能完成这个功能。

 

  1. 验证参数S和N的正确性
  2. 尺子中产生N-1个不同刻度
  3. 计算相邻刻度之间的值

 

/***
	 * <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

 


 

有了上述思想,我们便可以通过如下几个步骤实现该方法:

 

  1. 验证参数S和N的正确性
  2. 锯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]

 

本页内容版权归属为原作者,如有侵犯您的权益,请通知我们删除。
JVMjava 一、常见配置 1、堆设置 -Xms:初始堆大小 -Xmx:最大堆大小 -XX:NewSize=n:设置年轻代大小 -XX:NewRatio=n:设置年轻代和年老代的比值。如:为5,表示年轻代与年老代比值为1:5,年轻代占整个年轻代年老代和的1/6 -XX:SurvivorRatio=n:年轻代中Eden区与两个Survivor区的比值。注意Survivor区有两个。如:8,表示Eden:Survivor=8:2,一个Survivor区占整个年轻代的1/10 -XX:MaxPermSize=n

Java为什么能够跨平台? - 2016-09-23 14:09:05

  这也许是个萌新的问题,但我也想把它记录下来,作为Java学习的开始。   在这个大型企业软件横行的时代,Java的使用率越来越高,当然依旧不少的人不喜欢Java,因为它的设计过于笨重,但其开发效率高也是不可否认的一个优点。   言归正传,今天我们讨论下为什么Java是跨平台的语言,我们知道汇编语言的优点及其显著,就是运行速度极快,因为其就是机器指令的助记符。但缺点也是很突出的,除了读不懂以外(本人弱渣),就是汇编是体系结构依赖的语言。如有8086指令集,也有MIPS指令集等等,而像C,C++就会先翻译成
方法一:     import  java.awt.*;   import  java.awt.image.*;   import  java.io.*;   import  javax.swing.*;   import  com.sun.image.codec.jpeg.*;   public   class  WaterSet {       /** */ /**        * 给图片添加水印        *         * @param filePath        *        
    最近项目上要调用其他系统的WebService(Axis搭建),由于接收数据较大耗时4分钟左右,所以要设置超时时间,而且系统中已有jar包的原因,导致许多方法都不能用,最终用HttpClient。 方法一:使用JaxWsDynamicClientFactory调用WebService public static Object call(String wsdl,String method,String requestStr){JaxWsDynamicClientFactory factory = J

深刻理解IdentityHashMap - 2016-09-23 14:09:05

新建POJO package test;public class Cat {private String name;private Integer age;public Cat(String name, Integer age) {super();this.name = name;this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}public In

成为java高手的八大条件 - 2016-09-23 14:09:05

成为java高手的八大条件 世界上并没有成为高手的捷径,但一些基本原则是可以遵循的。兄弟连JavaEE培训导师,告诉你学习java有这样的素质才能成为高手! 1、扎实的基础 数据结构、离散数学、编译原理,这些是所有计算机科学的基础,如果不掌握它们,很难写出高水平的程序。程序人人都会写,但当你发现写到一定程度很难再提高的时候,就应该想想是不是要回过头来学学这些最基本的理论。不要一开始就去学OOP,即使你再精通OOP,遇到一些基本算法的时候可能也会束手无策。因此多读一些计算机基础理论方面的书籍是非常有必要的。

MySQL助理配置 - 2016-09-23 14:09:05

基本配置   你需要经常察看以下3个配置项。不然,可能很快就会出问题。 innodb_buffer_pool_size:这是你安装完InnoDB后第一个应该设置的选项。缓冲池是数据和索引缓存的地方:这个值越大越好,这能保证你在大多数的读取操作时使用的是内存而不是硬盘。典型的值是5-6GB(8GB内存),20-25GB(32GB内存),100-120GB(128GB内存)。 innodb_log_file_size:这是redo日志的大小。redo日志被用于确保写操作快速而可靠并且在崩溃时恢复。一直到MyS
9个基于Java的搜索引擎框架   1.Java全文搜索引擎框架Lucene   毫 无疑问,Lucene是目前最受欢迎的Java全文搜索框架,准确地说,它是一个全文检索引擎的架构,提供了完整的查询引擎和索引引擎,部分文本分析引 擎。Lucene为开发人员提供了相当完整的工具包,可以非常方便地实现强大的全文检索功能。下面有几款搜索引擎框架也是基于Lucene实现的。 官方网站: http://lucene.apache.org/   2.开源Java搜索引擎Nutch   Nutch 是一个开源Java实

Quartz定时任务的实现及详解 - 2016-09-23 04:09:09

Quartz定时任务的实现及详解 平常工作中经常遇到写定时任务的,这次做一次记录和解析分享给大家,共同学习进步,遇到写的不对的地方也请大家指教 用例:比如每天凌晨我们要让系统定时执行一些耗费服务器的事情,或者其他的一些定时任务 相关的jar包在附件,如有需要自行下载 1、 首先怎么启动这个Quartz呢? 在项目启动的时候,让web.xml读取我们的定时器配置文件,如下所示 param-namecontextConfigLocation/param-nameparam-value/WEB-INF/conf

JDBC连接数据库的步骤详解 - 2016-09-23 04:09:09

   Java Code  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 8