分多次累计随机出某指定整数（多次随机整数，其和固定）的方法 -

Surmounting

浏览: 67828 次
性别:
来自: 北京

最近访客更多访客>>

film

zxjun8771

leigh94

OSSEZTEC

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

分多次累计随机出某指定整数（多次随机整数，其和固定）的方法

博客分类：

算法

随机多次整数累计参数

分多次累计随机出某指定整数（多次随机整数，其和固定）的方法

Spads

摘要

本文描述了同过 n 次取随机整数，使其总和为 m 的方法，并对该方法给出了数学证明。

正文

本文分为 5 个部分

---------- ---------- ---------- ----------

1、提出问题

2、解法程序

3、测试结果

4、测试程序

5、公式证明

【提出问题】

---------- ---------- ---------- ----------

有 n 次机会，每次随机一个整数。希望这 n 个整数之和是 m ；该怎么随机呢？

对于编程语言，惯例是提供了随机函数 r() ，得到 [0, 1) 之间的一个随机浮点数。所以从编程角度来说，随机一个整数，最常见的方式就是通过对 L * r() 向下取整来获取某一个范围内的整数。以上问题就转变成为了，如何获得合适的 L ，来满足 n 次随机的整数之和为 m 。

传统的做法，就是用 2 * m / n 来做这个 L 。问题是因为取整这个操作，让这种算法会产生比较大的误差。具体误差有多大，下边测试结果一栏会详细描述。

【解法程序】 —— 以 Java 程序为例

---------- ---------- ---------- ----------

/**
 * <b>获取总量固定多次随机的倍率</b><br/>
 * 当程序需要通过一定次数随机，每次随机一个整数，最终获取总和一定的值，
 * 可通过此方法获得随机倍率。<br/>
 * 在获取此倍率 <code>randomLimit</code> 之后，每次随机时通过
 * <code>(int) (new Random().nextDouble() * randomLimit)</code> 获得随机
 * 结果。<br/><br/>
 * 本方法的核心算法，基于证明了如下二个关系式：
 * <pre>
 * (int) (2 * totalNum / chanceCount) + 1 < randomLimit
 * (int) (2 * totalNum / chanceCount) + 2 > randomLimit
 * </pre>
 * 具体推算方法，请见 Spads 的 Shane Loo Li 发表的日志。<br/>
 * http://blog.csdn.net/shanelooli/article/details/10831811
 * @param	totalNum	最终希望各随机值相加后的总量
 * @param	chanceCount	随机次数
 * @return	每次随机，[0, 1) 标准随机值应该乘以的倍率
 */
static public double getRandomLimit(int totalNum, int chanceCount)
{
	double calculateBase = 2.0 * totalNum / chanceCount;
	int calculateBaseInt = (int) calculateBase;
	double randomLimit = (calculateBaseInt + 2) * (calculateBaseInt + 1)
			/ (2 * calculateBaseInt - calculateBase + 2);
	return randomLimit;
}

【测试结果】

---------- ---------- ---------- ----------

目标总和为 5000000

随机次数 20000

简易方法：实际随机数的总和 = 4993051，误差 = 0.1389%

Spads Shane的新方法：实际随机数的总和 = 4997315，误差 = 0.0537%

随机次数 50000

简易方法：实际随机数的总和 = 4946686，误差 = 1.10661%

Spads Shane的新方法：实际随机数的总和 = 4992772，误差 = 0.1445%

随机次数 150000

简易方法：实际随机数的总和 = 4915701，误差 = 1.16858%

Spads Shane的新方法：实际随机数的总和 = 5003719，误差 = 0.0743%

随机次数 500000

简易方法：实际随机数的总和 = 4758806，误差 = 4.48234%

Spads Shane的新方法：实际随机数的总和 = 4997350，误差 = 0.0530%

随机次数 1000000

简易方法：实际随机数的总和 = 4502306，误差 = 9.99529%

Spads Shane的新方法：实际随机数的总和 = 5003257，误差 = 0.0651%

随机次数 3000000

简易方法：实际随机数的总和 = 3602468，误差 = 27.279479%

Spads Shane的新方法：实际随机数的总和 = 4999469，误差 = 0.0106%

随机次数 5000000

简易方法：实际随机数的总和 = 2500655，误差 = 49.499820%

Spads Shane的新方法：实际随机数的总和 = 5000972，误差 = 0.0194%

随机次数 8000000

简易方法：实际随机数的总和 = 1598759，误差 = 68.680180%

Spads Shane的新方法：实际随机数的总和 = 4996882，误差 = 0.0623%

随机次数 13000000

简易方法：实际随机数的总和 = 0，误差 = 100.0000%

Spads Shane的新方法：实际随机数的总和 = 4999994，误差 = 0.0001%

随机次数 20000000

简易方法：实际随机数的总和 = 0，误差 = 100.0000%

Spads Shane的新方法：实际随机数的总和 = 4995380，误差 = 0.0924%

可以见到，无论多少次随机，简易方法比 Spads Shane 的新方法误差都要大。当随机次数较多时，简易方法误差显著增加；如果随机次数和最终所需的和达到同一个数量级，简易方法的误差就会极大，使得这种方法无法再使用。

以上测试结果报告，由下边给出的测试程序直接生成。

【测试程序】

---------- ---------- ---------- ----------

public void testRandomLimit()
{
	// 指定多次随机的整数加起来的预期总和，并显示
	int totalNum = 5000000;
	System.out.println("目标总和为 " + totalNum);

	// 随机次数
	int[] chanceCounts = {
			20000, 50000, 150000, 500000, 1000000, 3000000,
			5000000, 8000000, 13000000, 20000000
		};

	// 二种方法
	String[] reportTitles = {"\n简易方法：\t\t", "\nSpads Shane的新方法：\t"};
	double[] randomLimits = new double[2];

	// 一个随机数生成对象即可解决问题，没必要重复生成此对象
	Random ran = new Random();

	// 遍历各种随机次数，分别测评
	for (int index, methodIndex, chanceIndex = -1;
			++chanceIndex != chanceCounts.length; )
	{
		// 获取本次测评的随机次数，并显示
		StringBuilder report = new StringBuilder();
		int chanceCount = chanceCounts[chanceIndex];
		report.append("\n随机次数 ").append(chanceCount);

		// 分别指定传统方法的随机倍率，和 Spads Shane 新方法的随机倍率
		randomLimits[0] = 2.0 * totalNum / chanceCount;
		randomLimits[1] = getRandomLimit(totalNum, chanceCount);

		// 分别测评二种方法，最终显示结果报告
		for (methodIndex = -1; ++methodIndex != 2; )
		{
			report.append(reportTitles[methodIndex]);

			int realCount = 0;
			double randomLimit = randomLimits[methodIndex];

			for (index = -1; ++index != chanceCount; )
				realCount += (int) (ran.nextDouble() * randomLimit);
			report.append("实际随机数的总和 = ").append(realCount);

			double error = Math.abs(realCount - totalNum) / (double) totalNum;
			int percent = (int) (error * 100);
			report.append("， 误差 = ").append(percent).append('.');
			String decimalStr = "0000";
			if (percent != 100)
			{
				decimalStr = String.valueOf((int) (error * 1000000) - percent);
				if (decimalStr.length() < 4)
					report.append("0000".substring(decimalStr.length()));
			}
			report.append(decimalStr).append('%');
		}
		System.out.println(report.toString());
	}
}

【公式证明】

---------- ---------- ---------- ----------

之前我们看到，程序以一个并不太复杂的四则运算式，通过目标总和 m 与随机次数 n ，得到了随机倍率参量 L 。L 自身将是一个大于 1 的实数。因为如果 L <= 1 ，则 int(L * r()) 恒为 0 。

设 Z = 2m / n

L = [int(Z) + 1][int(Z) + 2] / [2int(Z) - Z + 2]

其中 int(x) 为向下取整函数。

接下来，我们来证明这个公式的正确性。

1、通过概率核心定律，求得 L 与 m, n 的关系

概率核心定律，认为有 p 概率发生的事情，在尝试多次后，其发生比例趋近于 p 。

设用 L * r() 取随机数，平均结果为 R ，可知 R * n = m ，即 2R = Z。

这里 r() 为产生 [0, 1) 随机数的函数。

我们总是可以把 L 表示成 a + b ，其中 a = int(L)，b∈[0, 1) 。因为 L > 1 ，所以 a >= 1 。

于是能够获得用 L, a 表示的 R 的表达式；其中最重要的一点，就是因为取整这种运算的存在，所以随机出 a 的概率，要小于其余整数。

R = { ∑(0 * 1/L) + (1 * 1/L) + (2 * 1/L) + ... + [(a - 1) * 1/L] } + a * (L - a)/L

根据等差数列求和公式，求 R 的表达式具体形式

R = [0/L + (a - 1)/L] * a / 2 + a * (L - a) / L

Z = 2R

= [a(a - 1) + 2a(L - a)] / L

= (2aL - a^2 - a) / L

2、证明 a = int(Z) + 1 ，开始的推论

因为 a = L - b ，b∈[0, 1) ，所以为证明 a = int(Z) + 1 ，只需要证明如下二个关系式：

int(Z) + 1 < L①

int(Z) + 2 > L②

为此，我们需要用可以确定范围的已知量，来表示 int(Z) 。

我们总是可以把 Z 表示成 int(Z) + c ，其中 c∈[0, 1) 。

根据之前的推论，我们知道 Z = (2aL - a^2 - a) / L

将 L = a + b ，b∈[0, 1) 代入上式

Z = [2a(a + b) - a^2 - a] / (a + b)

= (a^2 + 2ab - a) / (a + b)

= [(a + b)^2 - b^2 - a] / (a + b)

= a + b - (a + b^2) / (a + b)

至此，我们看到 Z = int(Z) + c = a + b - (a + b^2) / (a + b)

如果 b - (a + b^2) / (a + b) 是一个能够把绝对值范围控制在 1 以内的量，就可以通过取整原则，求得用 a, b 表示的 c 的表达式。

3、证明 b - (a + b^2) / (a + b) ∈ [-1, 0)

先证明

b - (a + b^2) / (a + b) < 0

↑

b < (a + b^2) / (a + b)

↑∵ a + b = L > 1 > 0

b(a + b) < a + b^2

↑

ab + b^2 < a + b^2

↑

ab < a

↑∵ a >= 1 > 0

b < 1

原题得证

再证明

b - (a + b^2) / (a + b) >= -1

↑

(a + b^2) / (a + b) - b <= 1

↑

(a + b^2) / (a + b) <= 1 + b

↑∵ a + b = L > 1 > 0

a + b^2 <= (a + b)(1 + b)

↑

a + b^2 <= a + ab + b + b^2

↑

0 <= ab + b

原题得证

因此，可知 b - (a + b^2) / (a + b) ∈ [-1, 0)

4、证明 a = int(Z) + 1 ，原题得证

根据上边的结论，

Z = int(Z) + c = a + b - (a + b^2) / (a + b)

int(Z) + c = a - 1 + [1 + b - (a + b^2) / (a + b)]

因为 b - (a + b^2) / (a + b) ∈ [-1, 0)

所以 1 + b - (a + b^2) / (a + b) ∈ [0, 1)

证明，如果 A + B = C + D ，A, C 为整数，B, D∈[0, 1) ，那么 B = D

∵ A + B = C + D

∴ A - C = D - B

若 A - C = 0 ，则 B = D

若 A - C >= 1 ，则 D - B = A - C >= 1

↑

D >= 1 + B

∵ D < 1 且 B >= 0

∴ D >= 1 + B 不成立。

∴ A - C >= 1 不成立。

∴ B = D 且 A = C

因此可知 c = 1 + b - (a + b^2) / (a + b) 且 int(Z) = a - 1

a = int(Z) + 1

5、求得 L 用 Z 的表达式

Z = (2aL - a^2 - a) / L

ZL = 2int(Z)L + 2L - [int(Z) + 1]^2 - int(Z) - 1

ZL - 2L - 2int(Z)L = -1 - [int(Z) + 1]^2 - int(Z)

L * [2 + 2int(Z) - Z] = [int(Z) + 1]^2 + int(Z) + 1

L = [int(Z)^2 + 2int(Z) + 1 + int(Z) + 1] / [2 + 2int(Z) - Z]

L = [int(Z)^2 + 3int(Z) + 2] / [2int(Z) - Z + 2]

L = [int(Z) + 1][int(Z) + 2] / [2int(Z) - Z + 2]

本文还发表于在其它网站

CSDN ： http://blog.csdn.net/shanelooli/article/details/10831811

中国开源社区： http://my.oschina.net/shane1984/blog/158439

51CTO ： http://shanelooli.blog.51cto.com/5523233/1286679

分享到：

Spads 工作组为 Cikers 项目编写的密码库使 ... | 辞职谈话的观察者之心，职业追求与工作行事 ...

2013-09-01 18:06
浏览 956
评论(0)
论坛回复 / 浏览 (0 / 1779)
分类:编程语言
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

分多次累计随机出某指定整数（多次随机整数，其和固定）的方法

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

分多次累计随机出某指定整数（多次随机整数，其和固定）的方法

评论

发表评论

相关推荐

CIKERS Shane 20191022

最近访客更多访客>>