给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到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();
?>
其他回答
就是这样,均匀分布,零rand5调用。
def rand7:
seed += 1
if seed >= 7:
seed = 0
yield seed
需要事先播种。
如果我们考虑尝试给出最有效答案的附加约束,即给定一个长度为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值的分布。
我相信有很多理论涵盖了这一点,我可能会在某个时候看一看并报告。
这是我在看过别人的答案后得出的最简单的答案:
def r5tor7():
while True:
cand = (5 * r5()) + r5()
if cand < 27:
return cand
Cand在[6,27]范围内,如果r5()的可能结果是均匀分布的,则可能结果是均匀分布的。你可以用下面的代码来测试我的答案:
from collections import defaultdict
def r5_outcome(n):
if not n:
yield []
else:
for i in range(1, 6):
for j in r5_outcome(n-1):
yield [i] + j
def test_r7():
d = defaultdict(int)
for x in r5_outcome(2):
s = sum([x[i] * 5**i for i in range(len(x))])
if s < 27:
d[s] += 1
print len(d), d
R5_outcome(2)生成r5()结果的所有可能组合。我使用与解决方案代码中相同的筛选器进行测试。你可以看到所有的结果都是相等的,因为它们有相同的值。
这个表达式足以得到1 - 7之间的随机整数
int j = ( rand5()*2 + 4 ) % 7 + 1;
面对这么复杂的答案,我觉得自己很蠢。
为什么不能:
int random1_to_7()
{
return (random1_to_5() * 7) / 5;
}
?