使用rand5实现rand7

题目描述

已知rand5()可以等概率随机获得[0,1,2,3,4]中的一个数字。要求用rand5()来实现一个rand7()，使得rand7()可以等概率获得[0,1,2,3,4,5,6]中的一个数字。

思路解析

对rand5()随机两次，获得一个坐标(x,y)，x=rand5，y=rand5。坐标(x,y)有25种可能，选取每3个坐标代表[0,1,2,3,4,5,6]中的一个数字，会用掉21个坐标。当(x,y)落在剩余的4个坐标中时，重复生成(x,y)，直到(x,y)有对应的数字。

代码实现

int rand5();
int rand7() {
	//坐标(x,y)和数字的映射
	int matrix[][5] = {
		{0, 0, 0, 1, 1},
		{1, 2, 2, 2, 3},
		{3, 3, 4, 4, 4},
		{5, 5, 5, 6, 6},
		{6, -1, -1, -1, -1}
	}
	
	int x = rand5(), y = rand5();
	while (matrix[x][y] == -1) {
		x = rand5();
		y = rand5();
	}
	return matrix[x][y];
}

概率分析

rand7()获得[0,1,2,3,4,5,6]中的每个数字的概率为3/25 + 4/25 * 3/25 + 4/25 * 4/25 * 3/25 +... =1/7，符合题意。