注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

solution

世人行动,实系幻影; 他们忙乱,真是枉然。

 
 
 

日志

 
 

今天看到的很有意思的东西  

2008-04-28 01:58:20|  分类: 可分享 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1、一个国家人们只想要男孩,每个家庭都会一直要孩子,只到他们得到一个男孩。如果生的是女孩,他们就会再生一个。如果生了男孩,就不再生了。那么,这个国家里男女比例如何?

最严格的方法是直接计算男孩和女孩数量的期望,都是1,所以男女比例平衡。另一种说法是每个孩子的概率都是1:1,所以总的来看,最终的比例也将是1:1。这种说法可以用概率里面的"停时"的概念严格化,其实也不简单。比如,如果每个家庭一直要孩子,直到男孩比女孩数多一个,这时候如何分析?

停时:tau称为独立同分布随机变量X_1, X_2, cdots的停时,若{tau=n}{X_{n+1}, X_{n+2}, cdots}独立。

停时定理:EX_i<inftyRightarrow

"停时"是一个很深刻的概念,也非常有用。比如如果题目改成“如果每个家庭一直都要孩子,直到男孩比女孩数多一个,或者生到了100个小孩(是不是有点太多了)为止”,这时候如果直接算期望可不是一件容易的事情,但用停时定理一步就能得出结果。

2、在一条高速公路上,在30分钟内看到一辆汽车的可能性是0.95,那么在10分钟内看到一辆车的概率是多少(假设过车的概率是恒定的)?

这个题目我觉得是所有题目里面最有意思的一个(海岛分金更有意思,但2old)。会做得举手...

只需注意一个事实:下一辆车来的时间和已经等待多久无关(等公交车不算)。这种概率分布称为Poisson分布...记事件A:0-10分钟无车,B:10-20分钟无车,C:20-30分钟无车,则A,B,C互相独立,而,所以... 

3、魔方总共有(8! × 38−1) × (12! × 212−1)/2 = 43252003274489856000=4.3× 1019个不同的状态。每个状态看作图上的一个点,则解魔方问题可以视作求一个超大图上的路径问题。这个图是如此之大,使得看上去求最短路这么简单的问题都变得非常困难,事实上,用计算机也不可能直接算。

虽然这个图是如此之大,而且边很少(每个顶点只引出12条边),但这个图的直径却非常小。可以证明,任何一种魔方的状态,都可以在26步之内复原。(见Optimal solutions for Rubik's Cube)

4、素数筛法的复杂度

性能调优--永远超乎想象,里面提到了素数筛法的复杂度,作者用实验发现此筛法是线形的。

所谓素数筛法就是那个求小于n的所有素数最简单的算法:

bool* prime(int n) {
bool *p = new bool[n];
memset(p, 0, sizeof p);
for (int i = 2; i < n; i++)
if (!p[i])
for (int j = 2*i; j < n; j+=i)
p[j] = true;
return p;
}

此算法复杂度实际为 。在可以测试的范围内,的确是接近线形的,虽然实际上不是。下面是如何估计sumfrac1p:

 

更精确的,

 

注意此估计可直接得出素数有无穷多个

 5、堆积木--能伸出桌面多远?

n个长度为1的砖块,叠起来能伸出桌面多远?(只考虑方块各平面都与桌面平行的情况)。

下面这种放法,很多人高中学物理的时候都见过吧?它用N个砖块伸出了大约1/2ln(N)。

20070412202939140

上面这种叠放方法称为Harmonic Stacks,但它是最优的吗?下面这个例子可以看出,在3个砖块,我们就已经能做的更好了。

20070413122130796

上面这个能继续往上堆么?很不幸

20070413123314578

下面这个也不行

20070412203007703

如果在上面再压很多砖块就可以了

20070412203054218

下面是一种叠放方法,可以做到大约O(lnN).

20070412203214750

但它也不是最优的,下面是20个和30个方块的最优叠放方法,它比上面的要好

20070412203239218

20070412203258531

下面是砖块数目比较少的时候的最优叠放方法。

20070412203126765

 

20070412203140218

不过说了这么多,上面的方法都只能做到ln(N)的量级,而下面这个方法可以用N个砖块,往前伸出 N^(1/3)的长度。

20070412203320187

而且,Mike Paterson及其合作者证明了,这种方法在量级上已经是最优的了!

 

 


  评论这张
 
阅读(214)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017