另一道腾讯的面试题,该如何解决_J2SE

另一道腾讯的面试题
看到C#区此题讨论的比较火，转过来大家一起讨论讨论。

已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10() 随机1~10，要求考虑每个数字出现的概率问题。

最近比较忙，很少上来看，为了庆祝国庆顺便散个分。

散分规则：
1、达到题目要求且给出算法说明的加分。
2、在第1点的基础上算法效率高的多加分。
3、只写出算法但没有说明的视情况加分。

------解决方案--------------------
int rand10()
{
int nResult=0;

while(true)
{
nResult=rand7();
if(nResult<=5)
break;
}

while(true)
{
int n = rand7();
if (n==1)
continue;
else if(n>4)
nResult*=2;
else
nResult=nResult*2-1;
break;
}
return nResult ;
}

挺好，转贴过来，概率10%。
------解决方案--------------------
1. 通过 rand7()*7+rand7() 产生 8 9 10 11 …… 51 52 53 54 55 56 这49个数，每个数的出现机率相等
2. 只需要前面 4*10 个数，所以舍弃后面的9个数
3. 将8 9 10 11 转化为 1，12 13 14 15 转化为 2，……，44 45 46 47 转化为 10。公式是 (a-4)/4

Java code

int rand10(){int a;while( (a=rand7()*7+rand7()) > 47 );return (a-4)/4;}
------解决方案--------------------
探讨

1. 通过 rand7()*7+rand7() 产生  8 9 10 11 …… 51 52 53 54 55 56 这49个数，每个数的出现机率相等
2. 只需要前面 4*10 个数，所以舍弃后面的9个数
3. 将8 9 10 11 转化为 1，12 13 14 15 转化为 2，……，44 45 46 47 转化为 10。公式是 (a-4)/4
Java code


int ran……

------解决方案--------------------
rand7() + 3%rand7()

1  2/49
2 （2+1）/49 -> 3/49
3 （2+1）/49 -> 3/49
4 （2+1+4）/49 -> 7/49
5 （2+1+4）/49 -> 7/49
6 （2+1+4）/49 -> 7/49
7 （2+1+4）/49 -> 7/49
8 （1+4）/49 -> 5/49
9  4/49
10 4/49

这样多简单~
------解决方案--------------------
探讨

1. 通过 rand7()*7+rand7() 产生  8 9 10 11 …… 51 52 53 54 55 56 这49个数，每个数的出现机率相等
2. 只需要前面 4*10 个数，所以舍弃后面的9个数
3. 将8 9 10 11 转化为 1，12 13 14 15 转化为 2，……，44 45 46 47 转化为 10。公式是 (a-4)/4
Java code


int ran……

------解决方案--------------------
（rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()）%10 +1
这个概率都是10%了，嘿嘿~
------解决方案--------------------
探讨
引用:

1. 通过 rand7()*7+rand7() 产生 8 9 10 11 …… 51 52 53 54 55 56 这49个数，每个数的出现机率相等
2. 只需要前面 4*10 个数，所以舍弃后面的9个数
3. 将8 9 10 11 转化为 1，12 13 14 15 转化为 2，……，44 45 46 47 转化为 10。公式是 (a-……

------解决方案--------------------
凑个热闹

考察rand7()+rand7()的结果
2,3,4,5,6,7,8,9,10,11,12,13,14
2=1+1 --概率=1/7 * 1/7 = 1/49
3=1+2=2+1 --概率=1/7 * 1/7 + 1/7 * 1/7 = 2/49
4=1+3=2+2=3+1 --3/49
5=1+4=2+3=3+2=4+1 --4/49
6=1+5=2+4=3+3=4+2=5+1 -- 5/49
7=1+6=2+5=3+4=4+3=5+2=6+1 --6/49
8=1+7=2+6=3+5=4+4=5+3=6+2=7+1 --7/49
9=2+7=3+6=4+5=5+4=6+3=7+2 --6/49
10=3+7=4+6=5+5=6+4=7+3 --5/49
11=4+7=5+6=6+5=7+4 --4/49
12=5+7=6+6=7+5 --3/49
13=6+7=7+6 --2/49
14=7+7 --1/49
用rand7()+rand7()结果%10
1==11%10 --概率4/49
2==2%10==12%10 --1/49+3/49=4/49
3==3%10==13%10 --2/49+2/49=4/49
4==4%10==14%10 --3/49+1/49=4/49
5==5%10 --4/49
6==6%10 --5/49 去掉3+3的情况 --4/49
7==7%10 --6/49 去掉3+4和4+3的情况 --4/49
8==8%10 --7/49 去掉3+5和4+4和5+3的情况 --4/49
9==9%10 --6/49 去掉4+5和5+5的情况 --4/49
0==10%10 --5/49 去掉 5+5的情况 --4/49
可见，当r=(rand7()+rand7())%10大于5的时候，去掉上述的情况，就可以满足0-9的概率就都是4/49（也就是0-9的概率都是10%）