Code & Fun

第53天。

今天的题目是Implement Rand10() Using Rand7()

如果我们是用Rand10()去实现Rand7()的话就简单,因为 10 比 7 大,所以:

1
2
3
4
5
int rand7() {
int r;
while((r = rand10) > 7);
return r;
}

但是题目是用Rand7()去实现Rand10,所以我们需要转换一下。

由于1/10 = 1/2 * 1/5,所以我们可以用rand5()rand2()来实现rand10(),而rand5()rand2()又可以用rand7()来实现,所以:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int rand10() {
return rand5() + 5 * (rand2() - 1);
}
int rand2() {
int r;
while((r = rand7()) > 2) {
}
return r;
}
int rand5() {
int r;
while((r = rand7()) > 5) {
}
return r;
}

其期望为7/2 + 7/5,所以调用rand7()的次数会比较大,我们可以用rand7()去实现rand49(),由于49 = 7 * 7,所以我们只需要调用两次rand7()即可实现出rand49()
然后用rand49()去实现一个rand40(),而rand40() % 10 + 1即实现了rand10():

1
2
3
4
5
6
7
8
int rand10() {
int r;
while((r = rand49()) > 40);
return r % 10 + 1;
}
int rand49() {
return (rand7()-1)*7 + rand7();
}

本文首发于Code & Fun