给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
#!/usr/bin/env ruby
class Integer
def rand7
rand(6)+1
end
end
def rand5
rand(4)+1
end
x = rand5() # x => int between 1 and 5
y = x.rand7() # y => int between 1 and 7
..尽管这可能被认为是作弊。
其他回答
以下是我的发现:
Random5产生1~5的范围,随机分布 如果我们运行3次并将它们加在一起,我们将得到3~15个随机分布的范围 在3~15范围内执行算术 (3~15) - 1 = (2~14) (2~14)/2 = (1~7)
然后我们得到1~7的范围,这是我们正在寻找的Random7。
这里有很多解决方案没有产生均匀分布,许多评论指出了这一点,但这个问题并没有把它作为一个要求。最简单的解决方案是:
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
这里允许作业题吗?
这个函数进行粗略的“以5为基数”的数学运算,生成0到6之间的数字。
function rnd7() {
do {
r1 = rnd5() - 1;
do {
r2=rnd5() - 1;
} while (r2 > 1);
result = r2 * 5 + r1;
} while (result > 6);
return result + 1;
}
简单的解决方案已经被很好地覆盖了:为一个random7结果取两个random5样本,如果结果超出了产生均匀分布的范围,就重新做一次。如果你的目标是减少对random5的调用次数,这是非常浪费的——对于每个random7输出,对random5的平均调用次数是2.38,而不是2,这是由于丢弃样本的数量。
你可以通过使用更多的random5输入一次生成多个random7输出来做得更好。对于使用31位整数计算的结果,最优结果是使用12次调用random5生成9个random7输出,平均每个输出调用1.34次。它是高效的,因为244140625个结果中只有2018983个需要废弃,或者不到1%。
Python演示:
def random5():
return random.randint(1, 5)
def random7gen(n):
count = 0
while n > 0:
samples = 6 * 7**9
while samples >= 6 * 7**9:
samples = 0
for i in range(12):
samples = samples * 5 + random5() - 1
count += 1
samples //= 6
for outputs in range(9):
yield samples % 7 + 1, count
samples //= 7
count = 0
n -= 1
if n == 0: break
>>> from collections import Counter
>>> Counter(x for x,i in random7gen(10000000))
Counter({2: 1430293, 4: 1429298, 1: 1428832, 7: 1428571, 3: 1428204, 5: 1428134, 6: 1426668})
>>> sum(i for x,i in random7gen(10000000)) / 10000000.0
1.344606
对于范围[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的幂。