## 概率统计
**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.如果a1*7+a2<40,b=(a1*7+a2)/4+1;如果a1*7+a2>=40,重复第一步。参考代码如下所示:
```c
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,也就是说,抽签先后顺序不影响公平性。
- 程序员如何准备面试中的算法
- 第一部分 数据结构
- 第一章 字符串
- 1.0 本章导读
- 1.1 旋转字符串
- 1.2 字符串包含
- 1.3 字符串转换成整数
- 1.4 回文判断
- 1.5 最长回文子串
- 1.6 字符串的全排列
- 1.10 本章习题
- 第二章 数组
- 2.0 本章导读
- 2.1 寻找最小的 k 个数
- 2.2 寻找和为定值的两个数
- 2.3 寻找和为定值的多个数
- 2.4 最大连续子数组和
- 2.5 跳台阶
- 2.6 奇偶排序
- 2.7 荷兰国旗
- 2.8 矩阵相乘
- 2.9 完美洗牌
- 2.15 本章习题
- 第三章 树
- 3.0 本章导读
- 3.1 红黑树
- 3.2 B树
- 3.3 最近公共祖先LCA
- 3.10 本章习题
- 第二部分 算法心得
- 第四章 查找匹配
- 4.1 有序数组的查找
- 4.2 行列递增矩阵的查找
- 4.3 出现次数超过一半的数字
- 第五章 动态规划
- 5.0 本章导读
- 5.1 最大连续乘积子串
- 5.2 字符串编辑距离
- 5.3 格子取数
- 5.4 交替字符串
- 5.10 本章习题
- 第三部分 综合演练
- 第六章 海量数据处理
- 6.0 本章导读
- 6.1 关联式容器
- 6.2 分而治之
- 6.3 simhash算法
- 6.4 外排序
- 6.5 MapReduce
- 6.6 多层划分
- 6.7 Bitmap
- 6.8 Bloom filter
- 6.9 Trie树
- 6.10 数据库
- 6.11 倒排索引
- 6.15 本章习题
- 第七章 机器学习
- 7.1 K 近邻算法
- 7.2 支持向量机
- 附录 更多题型
- 附录A 语言基础
- 附录B 概率统计
- 附录C 智力逻辑
- 附录D 系统设计
- 附录E 操作系统
- 附录F 网络协议
- sift算法
- sift算法的编译与实现
- 教你一步一步用c语言实现sift算法、上
- 教你一步一步用c语言实现sift算法、下
- 其它
- 40亿个数中快速查找
- hash表算法
- 一致性哈希算法
- 倒排索引关键词不重复Hash编码
- 傅里叶变换算法、上
- 傅里叶变换算法、下
- 后缀树
- 基于给定的文档生成倒排索引的编码与实践
- 搜索关键词智能提示suggestion
- 最小操作数
- 最短摘要的生成
- 最长公共子序列
- 木块砌墙原稿
- 附近地点搜索
- 随机取出其中之一元素