文档章节

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

王孟君
 王孟君
发布于 2016/10/12 20:09
字数 1717
阅读 448
收藏 21

如果给你一个问题:“随机产生和为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]

© 著作权归作者所有

王孟君

王孟君

粉丝 227
博文 94
码字总数 221044
作品 0
杭州
高级程序员
私信 提问
加载中

评论(2)

Leoops
Leoops
加个不重复的规则呢
剑啸月
剑啸月
萌新来抢沙发了。
《编程珠玑》第一章:开篇——排序

最近,在看一本名为《编程珠玑》的书,提高自己编写代码的能力和思路。里面描述的都是用c或c++来写,自己决定用java来实现里面提到的一些思路。这一章,讲述如何在容量限制的范围下,对数据量...

陈凯俊
2012/11/14
0
4
RSA的安全性---学习笔记(不包含数学关系的推导)

最近了解了RSA算法的安全性的基本原理,简单记录一下方便以后回顾(不包含数学公式的推导以及产生大质数和求模反元素的具体算法)。 RSA加密解密的数学公式: c=m^e%n m=c^d%n 需要的数学条件:...

duanbowen
2017/05/17
0
0
高级shell脚本(for、while、if、case)

1、编写脚本/root/bin/createuser.sh,实现如下功能:使用一个用户名做为参数,如果指定参数的用户存在,就显示其存在,否则添加之,并生成8位随机口令并存在一个文件中,初步提示改口令,显示...

Lightmisa
2017/09/17
0
0
RSA算法详解

前言 总括: 本文详细讲述了RSA算法详解,包括内部使用数学原理以及产生的过程。 原文博客地址:RSA算法详解 知乎专栏&&简书专题:前端进击者(知乎)&&前端进击者(简书) 博主博客地址:D...

秦至
2018/02/04
0
0
百度之星程序设计大赛(1)——连续正整数

题目描述: 一个正整数有可能可以被表示为n(n>=2)个连续正整数之和,如: 15=1+2+3+4+5 15=4+5+6 15=7+8 请编写程序,根据输入的任何一个正整数,找出符合这种要求的所有连续正整数序列。 输...

晨曦之光
2012/03/09
179
0

没有更多内容

加载失败,请刷新页面

加载更多

typescript 接口 函数类型 可索引类型

函数类型 可索引类型 数字索引签名 字符串索引签名 数字索引签名返回值 必须是 字符串索引签名返回值的子集 只读索引签名

lilugirl
今天
3
0
Oracle SQL语法实例合集

如需转载请注明出处https://my.oschina.net/feistel/blog/3052024 目的:迅速激活Oracle SQL 参考:《Oracle从入门到精通》 ------------------------------------------------------------......

LoSingSang
今天
2
0
增加 PostgreSQL 服务进程的最大打开文件数

https://serverfault.com/questions/628610/increasing-nproc-for-processes-launched-by-systemd-on-centos-7 要在systemd的配置里加才行...

helloclia
今天
2
0
组合模式在商品分类列表中的应用

在所有的树形结构中最适合的设计模式就是组合模式,我们看看常用商品分类中如何使用。 先定义一个树形结构的商品接口 public interface TreeProduct { List<TreeProduct> allProducts(...

算法之名
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部