另一道腾讯的面试题
看到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;}
[解决办法]
[解决办法]
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
这样多简单~
[解决办法]
[解决办法]
（rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()）%10 +1
这个概率都是10%了，嘿嘿~
[解决办法]
[解决办法]
凑个热闹
考察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%）
代码例子
- Java code
int rand10() { int r1, r2, r3=0; while (true) { r1 = rand7(); r2 = rand7(); r3 = (r1+r2)%10; if ((r3>5 || r3==0) && (Math.abs(r1-r2) <= (r3==8 ? 2 : 1))) continue; return r3+1; }}
[解决办法]
- Java code
int num = rand7()+rand7()-1;if(num>=1&&num<=10) return num;
[解决办法]
[解决办法]
- Java code
package com.cn.mishi;import java.util.Random;public class RandomTest { public static void main(String[] args) { int i = getRandomNumber(); int j = getRandomNumber(); int n = i * 7 + j; int k = n * 10; if (k >= 0 && k < 49) { System.out.println(1); } else if(k >= 49 && k < 49 * 2) { System.out.println(2); } else if(k >= 49*2 && k < 49 * 3) { System.out.println(3); } else if(k >= 49*3 && k < 49 * 4) { System.out.println(4); } else if(k >= 49*4 && k < 49 * 5) { System.out.println(5); } else if(k >= 49*5 && k < 49 * 6) { System.out.println(6); } else if(k >= 49*6 && k < 49 * 7) { System.out.println(7); } else if(k >= 49*7 && k < 49 * 8) { System.out.println(8); } else if(k >= 49*8 && k < 49 * 9) { System.out.println(9); } else if(k >= 49*9 && k < 49 * 10) { System.out.println(10); } } private static int getRandomNumber() { Random r = new Random(); return r.nextInt(7); }}
[解决办法]
小弟给个建议，大家看看可行否
在函数里调用2次rand7（），然后做字符串拼接，应该会等机会得到下列49个数
11 21 .......... 71
12 22 .......... 72
13 23 .......... 73
14 24 .......... 74
15 25 .......... 75
16 26 .......... 76
17 27 .......... 77
然后取其中10个映射1-10，出现其它的过滤，这样1-10的概率每个应该为10%的。
简单 清晰。
[解决办法]
[解决办法]
那就取4个数为一组映射一个数，这样不就可以去掉9个，留下40个了。减少循环次数了。
这个不是关键，我觉得比上面的让用户好理解，简单清晰。
[解决办法]
[解决办法]
[解决办法]
算法：
1) 先用ran7()实例出两个随机数，合并为n， 就可知取值范围：11~77,67个,每个数字的概率是相同的
2） 再用 (n-10)/67 将取值范围限定到 1~10
[解决办法]
- Java code
//除了0为4/49，其它的是5/49//(rand7()*7+rand7()-7)%10 for(int i=1;i<8;i++) { for(int j=1;j<8;j++) { System.out.printf("%2d,",(i*7+j-7)%10); } System.out.println(); }//结果如下： 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
[解决办法]
我出个想法啊，rand7()产生1~7的区间，那么我将它产生的区间转换为0~1这个区间，然后再转换为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-4)/4
这方法可行
[解决办法]
int rand10()
{
int a1 = rand7();
int a2 = rand7();
int a = a1 + a2;
if(a>10){
a = 10;
}
return a;
}
[解决办法]
新手来凑个热闹，我想用10次rand7（），加起来，应该是10到70中的任意一个数，
然后取除10取余数，余数应该是0到9之内的任意一个数吧，然后再加1
int rand10()
{
  int a = rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7();
  return a%10+1;
}
新手，要是错了的话，指出来就可以，别笑话~
[解决办法]
rand7()
可以这样来，0-0.7 1
0.7-1.4 2
1.4-2.1 3
2.1-2.8 4
2.8-3.5 5
3.5-4.2 6
4.2-4.9 7
4.9-5.6 8
5.6-6.3 9
6.3-7 10
太该就这意思，还需改进。。。。。
[解决办法]
[解决办法]
不用递归，不用会出现无限循环。
引用7进制的做法保证得到随机数的概率相同。例如（rand7-1）*7+rand7得到是00-66之间的全部七进制数。且保证概率相同。
但是涉及到对10取余，为了保证取余后概率相同，这个区间一定是0-10的整数倍。
00-666（七进制）表示数的范围是0-2400，所以对10取余后得到0-9的概率相同。
int rand10()
{
int sum=0;
for(int i=0; i<3; i++)
sum=7*sum+rand7()-1;
return sum%10+1;
}
保证概率相同，且时间复杂度可控。
详情见博客：http://blog.csdn.net/zmywhhit/article/details/6865521