Implement Rand10() Using Rand7()

LeetCode

第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();
}