编程之法:面试和算法心得

 主页   资讯   文章   代码   电子书 

概率统计

1

已知有个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.如果a17+a2<40,b=(a17+a2)/4+1;如果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; }



**2**

给你5个球,每个球被抽到的可能性为30、50、20、40、10,设计一个随机算法,该算法的输出结果为本次执行的结果。输出A,B,C,D,E即可。


**3**

2D平面上有一个三角形ABC,如何从这个三角形内部随机取一个点,且使得在三角形内部任何点被选取的概率相同。


**4**

英雄升级,
- 从0级升到1级,概率100%。
- 从1级升到2级,有1/3的可能成功;1/3的可能停留原级;1/3的可能下降到0级;
- 从2级升到3级,有1/9的可能成功;4/9的可能停留原级;4/9的可能下降到1级。

每次升级要花费一个宝石,不管成功还是停留还是降级。求英雄从0级升到3级平均花费的宝石数目。

提示:从第n级升级到第n+1级成功的概率是(1/3)^n(指数),停留原级和降级的概率一样,都为[1-(1/3)^n]/2)。

**5**

甲包8个红球 2个蓝球,乙包2个红球 8个蓝球。抛硬币决定从哪个包取球,取了11次,7红4蓝。注,每次取后还放进去,只抛一次硬币。问选的是甲包的概率?

提示:贝叶斯公式 + 全概率公式作答。


**6**

一个桶里面有白球、黑球各100个,现在按下述规则取球:
- i 、每次从通里面拿出来两个球;
- ii、如果取出的是两个同色的求,就再放入一个黑球;
- ii、如果取出的是两个异色的求,就再放入一个白球。
问:最后桶里面只剩下一个黑球的概率是多少?


**7**

一个文件中含有n个元素,只能遍历一遍,要求等概率随机取出其中之一。

提示:5个人抽5个签,只有一个签意味着“中签”,轮流抽签,5个人中签的概率一样大,皆为1/5,也就是说,抽签先后顺序不影响公平性。