给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
如果我们考虑尝试给出最有效答案的附加约束,即给定一个长度为m(1-5)的均匀分布整数的输入流I,输出一个长度为m(1-7)的均匀分布整数的流O,长度为L(m)。
最简单的分析方法是将流I和O分别视为5元数和7元数。这是通过主答案的思想来实现的,即取流a1, a2, a3,…- > a1 + a2 + 5 * 5 ^ 2 * a3 + . .流O也是如此。
然后如果我们取长度为m的输入流的一段,选n s.t, 5^m-7^n=c,其中c>0,且尽可能小。然后有一个从长度为m的输入流到1到5^m的整数的统一映射,还有一个从1到7^n的整数到长度为n的输出流的统一映射,当映射的整数超过7^n时,我们可能不得不从输入流中丢失一些情况。
这就给出了L(m)的值约为m (log5/log7)也就是。82米。
上述分析的难点是方程5^m-7^n=c,它不容易精确求解,而在1到5^m的均匀值超过7^n的情况下,我们失去了效率。
问题是如何接近m (log5/log7)的最佳可能值。例如,当这个数字接近一个整数时,我们能否找到一种方法来实现这个精确的整数值输出?
如果5^m-7^n=c,那么从输入流中,我们有效地生成了一个从0到(5^m)-1的均匀随机数,并且不使用任何高于7^n的值。但是,这些值可以被保存并再次使用。它们有效地生成了从1到5^m-7^n的统一数字序列。所以我们可以尝试使用这些,并将它们转换成7位数,这样我们就可以创建更多的输出值。
如果我们让T7(X)是由大小为X的均匀输入导出的随机(1-7)整数的输出序列的平均长度,并假设5^m=7^n0+7^n1+7^n2+…+ 7 ^ nr + s, s < 7。
那么T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0)因为我们有一个无长度序列,概率为7^n0/5^m,残差长度为5^m-7^n0,概率为(5^m-7^n0)/5^m)。
如果我们一直代入,我们得到:
T7(5^m) = n0x7^n0/5^m + n1x7^n1/5^m + ... + nrx7^nr/5^m = (n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/5^m
因此
L(m)=T7(5^m)=(n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/(7^n0+7^n1+7^n2+...+7^nr+s)
另一种说法是:
If 5^m has 7-ary representation `a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r
Then L(m) = (a1*7 + 2a2*7^2 + 3a3*7^3+...+rar*7^r)/(a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r)
最好的情况是上面的原始情况,即5^m=7^n+s,其中s<7。
然后机械师》(5 ^ m) = nx (7 ^ n) / (7 ^ n + s) = o (n + 1) = m (Log5 / Log7) + o(1)美国之前。
最坏的情况是我们只能找到k和s.t 5^m = kx7+s。
Then T7(5^m) = 1x(k.7)/(k.7+s) = 1+o(1)
其他情况介于两者之间。看看对于很大的m,我们能做得多好,也就是说,我们能多好地得到误差项,这将是很有趣的:
T7(5^m) = m (Log5/Log7)+e(m)
一般来说,似乎不可能实现e(m)=o(1)但希望我们可以证明e(m)=o(m)。
整个问题取决于5^m的7位数字对不同m值的分布。
我相信有很多理论涵盖了这一点,我可能会在某个时候看一看并报告。
其他回答
这里有很多解决方案没有产生均匀分布,许多评论指出了这一点,但这个问题并没有把它作为一个要求。最简单的解决方案是:
int rand_7() { return rand_5(); }
1 - 5范围内的随机整数显然在1 - 7范围内。从技术上讲,最简单的解决方法是返回一个常数,但那太琐碎了。
然而,我认为rand_5函数的存在是一个转移注意力的问题。假设问题是“生成一个均匀分布的伪随机数生成器,输出范围为1 - 7”。这是一个简单的问题(技术上不简单,但已经解决了,所以您可以查阅它)。
另一方面,如果问题被解释为你实际上有一个真正的随机数生成器,用于范围为1 - 5的整数(而不是伪随机),那么解决方案是:
1) examine the rand_5 function
2) understand how it works
3) profit
因为1/7是一个以5为底的无限小数,所以没有(完全正确的)解可以在常数时间内运行。一个简单的解决方案是使用拒绝抽样,例如:
int i;
do
{
i = 5 * (rand5() - 1) + rand5(); // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1; // result is now uniformly random between 1 and 7
这个循环的预期运行时间为25/21 = 1.19次迭代,但是永远循环的概率非常小。
下面使用随机数发生器在{1,2,3,4,5,6,7}上产生均匀分布,在{1,2,3,4,5}上产生均匀分布。代码很混乱,但逻辑很清晰。
public static int random_7(Random rg) {
int returnValue = 0;
while (returnValue == 0) {
for (int i = 1; i <= 3; i++) {
returnValue = (returnValue << 1) + SimulateFairCoin(rg);
}
}
return returnValue;
}
private static int SimulateFairCoin(Random rg) {
while (true) {
int flipOne = random_5_mod_2(rg);
int flipTwo = random_5_mod_2(rg);
if (flipOne == 0 && flipTwo == 1) {
return 0;
}
else if (flipOne == 1 && flipTwo == 0) {
return 1;
}
}
}
private static int random_5_mod_2(Random rg) {
return random_5(rg) % 2;
}
private static int random_5(Random rg) {
return rg.Next(5) + 1;
}
我玩了一下,我为这个Rand(7)算法写了“测试环境”。例如,如果你想尝试哪种分布给你的算法,或者需要多少次迭代才能生成所有不同的随机值(对于Rand(7) 1-7),你可以使用它。
我的核心算法是:
return (Rand5() + Rand5()) % 7 + 1;
和亚当·罗森菲尔德的分布一样均匀。(我将其包含在代码片段中)
private static int Rand7WithRand5()
{
//PUT YOU FAVOURITE ALGORITHM HERE//
//1. Stackoverflow winner
int i;
do
{
i = 5 * (Rand5() - 1) + Rand5(); // i is now uniformly random between 1 and 25
} while (i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1;
//My 2 cents
//return (Rand5() + Rand5()) % 7 + 1;
}
这个“测试环境”可以采用任何Rand(n)算法并测试和评估它(分布和速度)。只需将代码放入“Rand7WithRand5”方法并运行代码片段。
一些观察:
亚当·罗森菲尔德(Adam Rosenfield)的算法并不比我的算法分布得更好。不管怎样,两种算法的分布都很糟糕。 本机Rand7(随机的。Next(1,8))完成,因为它在大约200+迭代中生成了给定间隔内的所有成员,Rand7WithRand5算法的顺序为10k(约30-70k) 真正的挑战不是编写从Rand(5)生成Rand(7)的方法,而是生成几乎均匀分布的值。
PHP解决方案
<?php
function random_5(){
return rand(1,5);
}
function random_7(){
$total = 0;
for($i=0;$i<7;$i++){
$total += random_5();
}
return ($total%7)+1;
}
echo random_7();
?>