日期:2014-05-20  浏览次数:20944 次

一道腾讯的面试题
已知有个rand7()的函数,返回1到7随机自然数,让利用这个rand7()构造rand10() 随机1~10。


------解决方案--------------------
1/7的概率得到1,2
3/7的概率得到4,6,8,10
3/7的概率得到3,5,7,9
这个概率明显不是每个数都是10%
------解决方案--------------------
刚刚理解错了。
。。。。
应该是对的。每个数的概率相同。。。
但是可能存在一个问题,两个while里面产生的随机数会相同,如果运行太快的话
------解决方案--------------------
C# code

class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Rand10());
            Console.Read();
        }
        static int Rand10()
        {
            Random ran = new Random();
            return ran.Next(0, 3) + Rand7();
        }
        static int Rand7()
        {
            Random ran = new Random();
            return ran.Next(1, 7);
        }
    }

------解决方案--------------------
好像要完全利用Rand7,那我搞错了
------解决方案--------------------
做两次随机.将它们看做二位7进制数的两个位,那么这个7进制数可以表示的最大值为:

6*7 + 6 = 48;然后把这个数10等分即4.8,即可建立一个区间的对应关系.

前面说那么复杂其实就是算出这个数的10进制值除去4.8 丢弃小数位后+1...

int rand10 (){
return ((int)(((rand7()-1)*7 + (rand7()-1)) / 4.8)) + 1;
}
------解决方案--------------------
汗..搞懵了.
因为要+1,所以要除的应该是48 / 9 ≈ 5.3333333...
------解决方案--------------------
探讨
汗..搞懵了.
因为要+1,所以要除的应该是48 / 9 ≈ 5.3333333...

------解决方案--------------------
此楼错误,正解在13楼。

code=C#using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
class Program
{

static Random r = new Random();

static void Main(string[] args)
{
Console.WriteLine("".PadLeft(20, '='));
TestRnd(rand7);
Console.WriteLine("".PadLeft(20, '='));
TestRnd(Rnd10);
Console.WriteLine("".PadLeft(20, '='));
}

static int rand7()
{
return r.Next(1, 8);
}

static int Rnd10()
{
return (rand7() * 7 + rand7()) % 10 + 1;
}

static void TestRnd(Func<int> RndFunc)
{
Enumerable.Range(0, 1000000)
.Select(x => RndFunc())
.GroupBy(x => x, (x, y) => new { x, y = y.Count() / 1000000.0 })
.OrderBy(x => x.x)
.ToList()
.ForEach(x => Console.WriteLine("{0} 概率 {1:0.0000}", x.x, x.y));
}
}
}code
====================
1 概率 0.1425
2 概率 0.1431
3 概率 0.1428
4 概率 0.1434
5 概率 0.1433
6 概率 0.1426
7 概率 0.1423
====================
1 概率 0.1019
2 概率 0.1022
3 概率 0.1019
4 概率 0.1020
5 概率 0.1021
6 概率 0.1020
7 概率 0.1021
8 概率 0.0812
9 概率 0.1022
10 概率 0.1024
====================
Press any key to continue . . .
------解决方案--------------------
探讨

C# code

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