给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
这里允许作业题吗?
这个函数进行粗略的“以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;
}
其他回答
extern int r5();
int r7() {
return ((r5() & 0x01) << 2 ) | ((r5() & 0x01) << 1 ) | (r5() & 0x01);
}
对于范围[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的幂。
给定一个生成1到5rand5()范围内随机整数的函数,编写一个生成1到7rand7()范围内随机整数的函数
在我建议的解决方案中,我只调用rand5一次
真正的解决方案
float rand7()
{
return (rand5() * 7.0) / 5.0 ;
}
这里的分布是缩放的,所以它直接取决于rand5的分布
整数解
int rand7()
{
static int prev = 1;
int cur = rand5();
int r = cur * prev; // 1-25
float f = r / 4.0; // 0.25-6.25
f = f - 0.25; // 0-6
f = f + 1.0; // 1-7
prev = cur;
return (int)f;
}
这里的分布取决于rand7(i) ~ rand5(i) * rand5(i-1)
rand7(0) ~ rand5(0) * 1
这里有很多解决方案没有产生均匀分布,许多评论指出了这一点,但这个问题并没有把它作为一个要求。最简单的解决方案是:
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
我首先想到的是这个。但我不知道它是否均匀分布。 在python中实现
进口随机 def rand5 (): 返回random.randint(1、5) def rand7 (): 返回((rand5() -1) * rand5()) %7)+1