shshsh_0510 发表于 2009-6-19 08:23:43

本帖最后由 shshsh_0510 于 2009-6-19 08:25 编辑

第二种是先花费100天,然后可以得到一个初始值,从而省掉前面一些人的判断。至于省多少,关键是看首个出现两次的人出现的天数的期望
设p(n)=P{第n-1天还没出现,第n天出现}
则 $p(n)=((100!)/(100^n*(100-(n-1))!))*(n-1)/100$
首个出现两次的人出现的天数的期望 E
$E=\sum_(i=1)^100{p(i)*i=12.2}$
于是平均省掉$\sum_(i=1)^11{100+100/i}=1212.851762天=3.3年$

shshsh_0510 发表于 2009-6-19 08:31:26

第3种方法分析比较复杂,所以留给大家:)
我认为二级计数者每个应该在10个左右最好。
另外,这个是目前似乎是最好成绩了,10年左右,是不是还可以更好些呢?还能好多少?

shshsh_0510 发表于 2009-6-23 12:01:23

12# shshsh_0510

这个题又想了一下,可以设想初始每人有一点的信息,然后通过放下、拾取,信息点开始在人间流动,直到最后有人收集了所有的点才结束。
显然固定一个收集人,则她成为这一过程的瓶颈,所以最好每个人都收集,然后汇总。
但是,收集过程中,往往最后的几人代价很高,所以每人手中的信息点数的不同状态数要尽量小!
想到一种方案,并编程试了一下,3000天可以50%左右的概率成功,所以期望在6000天。不知道他那个10年的是什么样的参数?
我的方法如下:
先两两配对,在X1次后,基本上变成50人有2点,50人0点了,然后再两两配对,X2次后,变成25人,每人4点,....
另外,指定一个收集者,给一定时间Y对剩下的人补漏,最后剩下的6个有16点的人统一由此收集者进行收集

我的参数大概为:
1点 -2 点的合并:700天
2-4:500,然后 100天收集补漏
4-8:400 ,100
8-16:350,100
最后汇总:750

感觉最少不会少于Nlog2N=664,不知道可以有多接近

bolizhou 发表于 2009-6-23 16:34:24

要能够把时间大量缩短才行,呵呵,看过《Prison Break》电视剧,觉得如果这个时间太久了,那么肯定有那些年纪大的或得了大病的囚徒,会孤注一掷地提前要求释放的。在那个20分钟内,一定有一个像迈克·斯科菲尔德的天才站出来的。
页: 1 [2]
查看完整版本: 一个囚徒问题