Massive Algorithms: 概率统计相关面试题

概率统计
已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10() 随机1~10。
分析：这题主要考的是对概率的理解。程序关键是要算出rand10，1到10，十个数字出现的考虑都为10%.根据排列组合，连续算两次rand7出现的组合数是7*7=49，这49种组合每一种出现考虑是相同的。怎么从49平均概率的转换为1到10呢？方法是：

1.rand7执行两次，出来的数为a1=rand7()-1，a2=rand7()-1.
2.如果a1*7+a2=40,重复第一步。参考代码如下所示：

int rand7()
{
    return rand() % 7 + 1;
}

int rand10()
{
    int a71, a72, a10;
    do
    {
        a71 = rand7() - 1;
        a72 = rand7() - 1;
        a10 = a71 * 7 + a72;
    } while (a10 >= 40);
    return (a71 * 7 + a72) / 4 + 1;
}

随机数相关面试题
给你一个数组，设计一个既高效又公平的方法随机打乱这个数组（此题和洗牌算法的思想一致）

void suffle(int a[], int n)

{

    while(n>1){

        swap(a[n-1], a[rand()%n]);

        n--;

    }

}

2、有一苹果，两个人抛硬币来决定谁吃这个苹果，先抛到正面者吃。问先抛这吃到苹果的概率是多少？

　　这种题目一看似乎答案就是1/2，但其实认真细想并没有那么简单。给所有的抛硬币操作从1开始编号，显然先手者只可能在奇数（1,3,5,7…）次抛硬币得到苹果，而后手只可能在偶数次（2,4,6,8…）抛硬币得到苹果。设先手者得到苹果的概率为p，第1次抛硬币得到苹果的概率为1/2，在第3次（3,5,7…）以后得到苹果的概率为p/4（这是因为这种只有在第1次和第2次抛硬币都没有抛到正面（概率为1/4=1/2*1/2）的时候才有可能发生，而且此时先手者在此面临和开始相同的局面）。所以可以列出等式p=1/2+p/4，p=2/3。如题，大家懂得……

　　还可以这样算，1/2 + 1/8 + 1/16 +……+1/2^(奇数) = 2/3.

3、一条长度为l的线段，随机在其上选2个点，将线段分为3段，问这3个子段能组成一个三角形的概率是多少？　　

　　设随机选取的两个数为x，y，并令y>x，则把长度为1的线段截得的三段长度为x， y-x ，1-y，根据三角形两边和大于第三边以及两边之差小于第三边的定理，可以列出方程组 y>1-y; x<1-x; x+(1-y)>y-x; 即x<1/2; y>1/2; y>x+1/2;

　　画图可以算得概率为1/8.

4、一个面试题：快速生成10亿个不重复的18位随机数的算法(从n个数中生成m个不重复的随机数)

5、你有两个罐子以及50个红色弹球和50个蓝色弹球，随机选出一个罐子然后从里面随机选出一个弹球，怎么给出红色弹球最大的选中机会?在你的计划里，得到红球的几率是多少?

　　题目意思是两个罐子里面放了50红色和50蓝色弹球，然后我任选一个罐子，从中选中一个红球的最大概率，是设计一个两个罐子里怎么放这100球的计划。一个罐子：1个红球另一个罐子：49个红球，50个篮球几率=1/2+(49/99)*(1/2)=74.7%。

7、A和B2人投硬币,正面A得1元,反面B得一元.起始时A有1元,B有100元. 游戏持续进行,直到其中1人破产才终止.

问:(出自投行面试题)

　　1.如果硬币正反概率相同,游戏的期待长度(expected duration)是几次投掷?

　　2.如果硬币是不公正的,正面概率为P,反面概率为Q.(P+Q=1), 那么游戏的期待长度(expectedduration)是几次投掷?

目前认为只有奇数次才可能破产。

　　第一问：1*1/0.5 + 3*1/0.5^3 + 5*1/0.5^5

9、平均要取多少个(0,1)中的随机数才能让和超过1。答案： e 次，其中e是自然对数的底

Read full article from 概率统计

概率统计相关面试题

Labels

Popular Posts