另一道腾讯的面试题

Question

看到C#区此题讨论的比较火，转过来大家一起讨论讨论。已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10() 随机1~10，要求考虑每个数字出现的概率问题。
最近比较忙，很少上来看，为了庆祝国庆顺便散个分。
散分规则：
        1、达到题目要求且给出算法说明的加分。
        2、在第1点的基础上算法效率高的多加分。
        3、只写出算法但没有说明的视情况加分。

Answer 1

这个题在网上讨论的很多哦一google能搜到一大把

Answer 2

rand7()的函数  是自己写的么？

Answer 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%。

Answer 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
int rand10(){int a;while( (a=rand7()*7+rand7()) > 47 );return (a-4)/4;}

Answer 5

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这样多简单~

Answer 6

影响  想了一个  不知道对不对   还希望多批评指正哦
public static int ran10() {
int a10 ;
while( (a10 = ran7()+ran7() - 1) > 10) ;
return a10;
}
说明 
1 ran7()+ran7() - 1   1到13  
2  10 之后的删去
3  返回

Answer 7

（rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()+rand7()）%10 +1
这个概率都是10%了，嘿嘿~

Answer 8

http://topic.csdn.net/u/20110929/09/2d6e075a-9a8a-4e9e-9b15-0a80ec94210f.html

Answer 9

凑个热闹考察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%）代码例子
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;
    }
}

Answer 10

int num = rand7()+rand7()-1;
if(num>=1&&num<=10)
  return num;

Answer 11

"-1" 为了最小可以得到num=1

Answer 12

因为5个数一组，10个数字就需要 5*10 = 50个数，同理，6个数一组需要60个数
而两次rand7()的概率分布是 7*7 = 49，不能满足上述的50和60，所以4个数一组需要40个数，49可以满足
11L的思路和我的思路差不多，11L的每个数的概率是1/49，所以四个数一组就是4/49的概率，去掉58-56的9种情况，即去掉9/49，剩余的40/49平分到10个数字，我的思路也是找到4/49的概率组合，然后去掉9种概率，剩余的都是4/49的概率，也能达到平分，效率上可能11L要好一些，相对运算少一些，虽然去掉9种情况的判断上是两种都差不多

Answer 13

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

Answer 14

小弟给个建议，大家看看可行否在函数里调用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%的。简单 清晰。

Answer 15

那不就是11L说的吗，你这样的思路是直接拼成rand7()*10+rand7()，11L是rand7()*7+rand7()，大同小异，11L的也没有不简单清晰啊
我的思路是(rand7()+rand7())%10，去掉>5的情况下前后两个rand7()的差距在某个范围内的9种情况，相对不太好理解，不过思路上是差不多的。

Answer 16

算法：1) 先用ran7()实例出两个随机数，合并为n， 就可知取值范围：11~77,67个,每个数字的概率是相同的
2） 再用 (n-10)/67 将取值范围限定到 1~10 

Answer 17

//除了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,

Answer 18

我出个想法啊，rand7()产生1~7的区间，那么我将它产生的区间转换为0~1这个区间，然后再转换为1~10这个区间

Answer 19

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
这方法可行

Answer 20

int rand10()
{
  int a1 = rand7();
  int a2 = rand7();
  int a = a1 + a2;
  if(a>10){
    a = 10;
  }
  return a;
}

Answer 21

新手来凑个热闹，我想用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;
}
新手，要是错了的话，指出来就可以，别笑话~

Answer 22

新手来凑个热闹，我想用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;
}
新手，要是错了的话，指出来就可以，别笑话~

Answer 23

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
太该就这意思，还需改进。。

Answer 24

不用递归，不用会出现无限循环。
引用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