给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
你需要的函数是rand1_7(),我写了rand1_5(),这样你就可以测试它并绘制它。
import numpy
def rand1_5():
return numpy.random.randint(5)+1
def rand1_7():
q = 0
for i in xrange(7): q+= rand1_5()
return q%7 + 1
其他回答
对于范围[1,5]到[1,7],这相当于用一个5面骰子滚动一个7面骰子。
然而,如果不“浪费”随机性(或者在最坏的情况下永远运行),就无法做到这一点,因为7的所有质因数(即7)都不能整除5。因此,最好的方法是使用拒绝抽样来获得任意接近于不“浪费”随机性的结果(例如,将多个5面骰子摇到5^n“足够接近”7的幂)。这个问题的解决方案已经在其他答案中给出了。
更一般地说,用p面骰子掷k面骰子的算法将不可避免地“浪费”随机性(并且在最坏的情况下永远运行),除非“每个质数能除k也能除p”,根据B. Kloeckner的“用骰子模拟骰子”中的引理3。例如,举一个更实际的例子,p是2的幂,k是任意的。在这种情况下,这种“浪费”和无限的运行时间是不可避免的,除非k也是2的幂。
int randbit( void )
{
while( 1 )
{
int r = rand5();
if( r <= 4 ) return(r & 1);
}
}
int randint( int nbits )
{
int result = 0;
while( nbits-- )
{
result = (result<<1) | randbit();
}
return( result );
}
int rand7( void )
{
while( 1 )
{
int r = randint( 3 ) + 1;
if( r <= 7 ) return( r );
}
}
为什么不简单一点呢?
int random7() {
return random5() + (random5() % 3);
}
由于取模,在这个解中得到1和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值的分布。
我相信有很多理论涵盖了这一点,我可能会在某个时候看一看并报告。