算法可爱小问题-探讨

from hphp

?持续更新，欢迎指教、讨论、转载，转载请注明出处~

1. 黑白球比例问题
• 想象一个管道对你抛球（白色或黑色），你无法确切记录球的个数（由于实际数量过大），如何可以知道尽量精确的比例？

• ---

  记录每一段的比例，做平均
• 精确到更大的单位进行记录，如某个量级设为一个单位
2. 如何产生随机数
3. 旅行商、最短路径、最短路径回到起点
• 经典问题
4. google的PageRank
5. 生男孩、女孩比例问题
• 经典问题，如果每个家庭都会在诞生出一枚男婴之后停止生育，那么在样本足够大的情况下，男多？女多？

• ---

  从简单的枚举角度出发
• 从随机的大样本环境下，不同的分割角度出发

  ---

  ---

• 同理，红绿灯问题、赌徒的必赢心理：认为如果之前一直是红灯，则下一盏是绿灯的几率更大一些；认为之前一直在输，则下一局翻盘的几率更大； -- 这种想法是不科学的
• 从正面解释就是，独立事件间的概率无关，如果前后的红绿灯是完全无关的，那么下一盏的概率是既定的；而如果赌场是完全公平的，恰巧你又一直在输，那么下一场翻盘的机会不变。
• 但是从直觉上看： 1. 人们容易感觉如果前面一直是红灯，或者一直在输，那么已经是小概率事件，如果再遇到一次则概率上更小；2. 日常生活中我们很难遇到如此“倒霉”的事情。
• 然而实际上，1. 一直遇到同一种待遇出现的概率是在整体输赢的情况下的其中一种而已，诚然这种概率很小，在前后待遇无关的情况下，之前的结果无法对下一个结果造成影响；但是可以认为如果出门，一路上一直碰到红灯，或者出去赌一直输的概率并不高
• 2. 如前所述~