给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
extern int r5();
int r7() {
return ((r5() & 0x01) << 2 ) | ((r5() & 0x01) << 1 ) | (r5() & 0x01);
}
其他回答
如果有人能就这一点给我反馈,那就太酷了,我使用了没有assert模式的JUNIT,因为在Eclipse中运行它很容易,也很快速,我也可以只定义一个主方法。顺便说一下,我假设rand5给出的值为0-4,加上1将得到1-5,rand7也是如此……所以讨论应该是解决方案,它的分布,而不是它是从0-4还是1-5…
package random;
import java.util.Random;
import org.junit.Test;
public class RandomTest {
@Test
public void testName() throws Exception {
long times = 100000000;
int indexes[] = new int[7];
for(int i = 0; i < times; i++) {
int rand7 = rand7();
indexes[rand7]++;
}
for(int i = 0; i < 7; i++)
System.out.println("Value " + i + ": " + indexes[i]);
}
public int rand7() {
return (rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5()) % 7;
}
public int rand5() {
return new Random().nextInt(5);
}
}
当我运行它时,我得到这样的结果:
Value 0: 14308087
Value 1: 14298303
Value 2: 14279731
Value 3: 14262533
Value 4: 14269749
Value 5: 14277560
Value 6: 14304037
这似乎是一个非常公平的分配,不是吗?
如果我将rand5()添加更少或更多次(其中次数不能被7整除),分布会清楚地显示偏移量。例如,将rand5()相加3次:
Value 0: 15199685
Value 1: 14402429
Value 2: 12795649
Value 3: 12796957
Value 4: 14402252
Value 5: 15202778
Value 6: 15200250
因此,这将导致以下结果:
public int rand(int range) {
int randomValue = 0;
for(int i = 0; i < range; i++) {
randomValue += rand5();
}
return randomValue % range;
}
然后,我可以更进一步:
public static final int ORIGN_RANGE = 5;
public static final int DEST_RANGE = 7;
@Test
public void testName() throws Exception {
long times = 100000000;
int indexes[] = new int[DEST_RANGE];
for(int i = 0; i < times; i++) {
int rand7 = convertRand(DEST_RANGE, ORIGN_RANGE);
indexes[rand7]++;
}
for(int i = 0; i < DEST_RANGE; i++)
System.out.println("Value " + i + ": " + indexes[i]);
}
public int convertRand(int destRange, int originRange) {
int randomValue = 0;
for(int i = 0; i < destRange; i++) {
randomValue += rand(originRange);
}
return randomValue % destRange;
}
public int rand(int range) {
return new Random().nextInt(range);
}
我尝试用不同的值替换destRange和originRange(甚至ORIGIN为7,DEST为13),我得到了这样的分布:
Value 0: 7713763
Value 1: 7706552
Value 2: 7694697
Value 3: 7695319
Value 4: 7688617
Value 5: 7681691
Value 6: 7674798
Value 7: 7680348
Value 8: 7685286
Value 9: 7683943
Value 10: 7690283
Value 11: 7699142
Value 12: 7705561
从这里我可以得出的结论是,你可以通过求和起始随机“目的地”时间来将任意随机改变为任意随机。这将得到一种高斯分布(中间值更有可能,边缘值更不常见)。然而,目标模量似乎均匀地分布在这个高斯分布中…如果能得到数学家的反馈就太好了……
最酷的是,成本是100%可预测的和恒定的,而其他解决方案导致无限循环的概率很小……
int rand7() {
int value = rand5()
+ rand5() * 2
+ rand5() * 3
+ rand5() * 4
+ rand5() * 5
+ rand5() * 6;
return value%7;
}
与选定的解决方案不同,该算法将在常数时间内运行。然而,它对rand5的调用比所选解决方案的平均运行时间多2次。
请注意,这个生成器并不完美(数字0比任何其他数字都有0.0064%的可能性),但对于大多数实际目的,保证恒定的时间可能比这种不准确性更重要。
解释
这个解源于数字15624能被7整除的事实,因此,如果我们可以随机且均匀地生成从0到15624的数字,然后对7取余,我们就可以得到一个近乎均匀的rand7生成器。将rand5滚动6次,将0到15624之间的数字统一生成,并使用这些数字组成以5为基数的数字,如下所示:
rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5
mod 7的属性允许我们稍微简化一下方程:
5^5 = 3 mod 7
5^4 = 2 mod 7
5^3 = 6 mod 7
5^2 = 4 mod 7
5^1 = 5 mod 7
So
rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5
就变成了
rand5 * 3 + rand5 * 2 + rand5 * 6 + rand5 * 4 + rand5 * 5 + rand5
理论
15624这个数字不是随机选择的,而是可以用费马小定理来发现的,该定理指出,如果p是质数,那么
a^(p-1) = 1 mod p
这就得到,
(5^6)-1 = 0 mod 7
(5^6)-1等于
4 * 5^5 + 4 * 5^4 + 4 * 5^3 + 4 * 5^2 + 4 * 5 + 4
这是一个以5为底的数,因此我们可以看到,这种方法可以用于从任何随机数发生器到任何其他随机数发生器。尽管在使用指数p-1时总是会引入对0的小偏差。
为了更准确地推广这种方法,我们可以有这样一个函数:
def getRandomconverted(frm, to):
s = 0
for i in range(to):
s += getRandomUniform(frm)*frm**i
mx = 0
for i in range(to):
mx = (to-1)*frm**i
mx = int(mx/to)*to # maximum value till which we can take mod
if s < mx:
return s%to
else:
return getRandomconverted(frm, to)
下面是Adam回答的Python实现。
import random
def rand5():
return random.randint(1, 5)
def rand7():
while True:
r = 5 * (rand5() - 1) + rand5()
#r is now uniformly random between 1 and 25
if (r <= 21):
break
#result is now uniformly random between 1 and 7
return r % 7 + 1
我喜欢把我正在研究的算法扔进Python,这样我就可以摆弄它们,我想我把它贴在这里,希望它对外面的人有用,而不是花很长时间来拼凑。
这是我在看过别人的答案后得出的最简单的答案:
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()结果的所有可能组合。我使用与解决方案代码中相同的筛选器进行测试。你可以看到所有的结果都是相等的,因为它们有相同的值。
你需要的函数是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