n****e
发帖数: 678 | 1 Write a method to generate a random number between 1 and 7, given a method
that generates a random number between 1 and 5 (i.e., implement rand7()
using rand5()).
给出的解是：
public static int rand7() {
while (true) {
int num = 5 * (rand5() - 1) + (rand5() - 1);
if (num < 21) return (num % 7 + 1);
}
}
想问一下为什么这么做是对的？
如果这样写对吗？
while (true) {
int num = 5 * (rand5() - 1) + (rand5() - 1);
if (num < 7) return (num + 1);
}
或者
while (true) {
int num = 5 * (rand5() - 1) + (rand5() - 1);
if (num < 14) return (num % 7 + 1);
}
或者
while (true) {
int num = 4 * (rand5() - 1) + (rand5() - 1);
if (num < 14) return (num % 7 + 1);
}
多谢大牛指教！ |
z****e
发帖数: 54598 | |
a******e
发帖数: 710 | 3 int num = 5 * (rand5() - 1) + (rand5() - 1);
这一句生成0-24之间的整数且均匀分布。每个整数出现的概率都是相等的。
所以0-20这21个数出现的概率也是相等的。
取余数之后，每个余数0-6出现的概率也是相等的。 所以此算法是正确的。
效率问题：
这个算法循环一次就成功的概率为 21/25 = 84%。循环的次数服从几何分布。 平均复
杂度为25/21
你的第一种写法中，每次循环成功概率为7/25 = 14%。 平均复杂度为25/7。
所以cc150中的解法复杂度要好于你的解法。
【在 n****e 的大作中提到】
: Write a method to generate a random number between 1 and 7, given a method
: that generates a random number between 1 and 5 (i.e., implement rand7()
: using rand5()).
: 给出的解是：
: public static int rand7() {
: while (true) {
: int num = 5 * (rand5() - 1) + (rand5() - 1);
: if (num < 21) return (num % 7 + 1);
: }
: }
|
n****e
发帖数: 678 | 4 能讲讲为什么原来的做法是对的吗？
如果上面3中alternative都可以，那下面这个写法应该比解答的效率要高吧：
while (true) {
int num = 6 * (rand5() - 1) + (rand5() - 1);
if (num < 28) return (num % 7 + 1);
}
【在 z****e 的大作中提到】
: 可以
: 但是这样做效率就偏低
|
n****e
发帖数: 678 | 5 多谢解释啊！
那下面这个写法应该比解答的效率要高吧：
while (true) {
int num = 6 * (rand5() - 1) + (rand5() - 1);
if (num < 28) return (num % 7 + 1);
}
【在 a******e 的大作中提到】
: int num = 5 * (rand5() - 1) + (rand5() - 1);
: 这一句生成0-24之间的整数且均匀分布。每个整数出现的概率都是相等的。
: 所以0-20这21个数出现的概率也是相等的。
: 取余数之后，每个余数0-6出现的概率也是相等的。 所以此算法是正确的。
: 效率问题：
: 这个算法循环一次就成功的概率为 21/25 = 84%。循环的次数服从几何分布。 平均复
: 杂度为25/21
: 你的第一种写法中，每次循环成功概率为7/25 = 14%。 平均复杂度为25/7。
: 所以cc150中的解法复杂度要好于你的解法。
|
P*****f
发帖数: 2272 | 6 previous post mentioned, this is not evenly distributed
【在 n****e 的大作中提到】
: 能讲讲为什么原来的做法是对的吗？
: 如果上面3中alternative都可以，那下面这个写法应该比解答的效率要高吧：
: while (true) {
: int num = 6 * (rand5() - 1) + (rand5() - 1);
: if (num < 28) return (num % 7 + 1);
: }
|
n****e
发帖数: 678 | 7 想通了，
5 * (rand5() - 1) + (rand5() - 1);
前面这个系数5是不能随便改的，因为是rand5，所以只有系数为5的时候所生成的书才
是随机的。
这种情况下21是最大的被7整除的数，所以解答是这么给的。
多谢指教！
【在 n****e 的大作中提到】
: 多谢解释啊！
: 那下面这个写法应该比解答的效率要高吧：
: while (true) {
: int num = 6 * (rand5() - 1) + (rand5() - 1);
: if (num < 28) return (num % 7 + 1);
: }
|
n****e
发帖数: 678 | 8 恩，是的，多谢！
【在 P*****f 的大作中提到】
: previous post mentioned, this is not evenly distributed
|
