to implement rand7() by rand5()
主要思路是构造一个解空间映射$$A$$到另一个解空间$$B$$，就这个题目而言需要注意的是从$$A$$中值映射到$$B$$中值的数量应该是相等的。
按照上面思路：
构造一个$$5\times 5 $$的矩阵循环填充 3 遍 1-7，共计 21 个取值空间其余以 0 补齐，如果返回值为 0，在来一次。
1
2
3
4
5
6
| int val = 0;
result[5 * 5] = [1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 0, 0, 0, 0];
while (val == 0) {
val = result[rand5() * rand5()];
}
rerurn val;
|
改良一下，其实这是需要 21 个解，即为 7 的倍数，如何靠 rand5() 的运算构造出就可以了。
考虑一下 rand5() 最大是 5，最小是 1，则$$rand5() \times rand5() = [1, 25]$$, 然后取$$[1, 21]$$重新映射到$$[1, 7]$$。
demo：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| import random
def rand5():
return random.randint(1, 5)
def rand7():
while (True):
i = 5 * (rand5() - 1) + rand5()
if 21 >= i:
break
return i % 7 + 1
if __name__ == "__main__":
try:
state = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0}
while (True):
state[rand7()] += 1
except KeyboardInterrupt:
print state
exit
|