离死亡还有 往生已逝的放废话的空间 大家好,我又来开挖坑不埋的数学题系列了

往生已逝的放废话的空间

往生已逝のゴミ言葉箱【心跳回忆百科全书建设中】

大家好,我又来开挖坑不埋的数学题系列了

大家好,我又来开挖坑不埋的数学题系列了,不过这些题目基本都是原创的。


这次的传话问题的灵感来自于:我接到了同事打来的一个电话,告诉我明天公司停电不上班。

一个理想的传话系统应该是1传2,2传4,如此指数扩散开。
比如说一个8个人的办公室,一个人A获知消息后,应该打电话给B,然后AB打电话给CD,然后ABCD打电话给EFGH,这样无疑效率是最高的。

然而,现实生活中不一定会那么理想,A打给B后,在通知C的时候可能会发现,刚刚B已经通知过他了。

于是,为了将这个传话模型改造的更加现实化,制定规则如下:
1,每个电话用时不计,冷却时间为1分钟。简单说两个电话就是2分钟。
2,不存在占线问题,如果A和B和D同时打电话通知C,视为这1分钟C接到三个电话,其中随机一个是新消息,其他的均为“已得知”。
3,每个人接到消息后,会立刻传话给另一个随机【未传话过的】人,如此继续下去,比如说A第一个电话打给B,第二个打给C,第三个绝对不会再打给B,因为A知道曾经通知过他,同理,因为B是通过A得知消息的,他在传话的过程中自然也不会再去通知A。
4,每个人不会一直打电话下去,毕竟他也知道有同事会帮忙,如果他连续打了三个电话都是“已得知”的结果,他将不会继续再打电话。

好,规则就以上几条,下面是问题。
1,依然是刚才八个人的办公室:如果搞这么一次通知,
a,第一个通知者(A)打电话次数的期望是?
b,平均每个人打电话次数的期望是?
c,8人均得知此消息的概率是?
d,未接到这次通知的人数的期望是?

如果这个算法我想到了解决的办法,我会进而计算一下更复杂的问题。
比如100个人的大办公室,依然是上面四个问题的话,结果大概会是多少呢?
---【日常系】 | 留言:3 | 引用:0 |
<<苍之涛 | 主页 | ……拔牙果然效果拔群>>

留言

看到这个很有意思
首先b问题是不是应该换成非A的电话期望,因为A和其他人的都不同。
写了个程序模拟了一下
可见按这个模型通知人数有相当大的保证,不过在n=100时总会有少数几个人通知不到。
n=8:(100000次)
A;5.697
其他:3.241
全通知几率:100000/100000
期望通知人数:8
总期望时间:6.887

n=100:(10000次)
A;10.003
其他:4.187
全通知几率:3292/10000
期望通知人数:98.8544
总期望时间:14.6587
2013-07-13 Sat 18:48 | URL | pipikaqiu [ 编辑 ]
噢噢pipikaqiu大,您看到这篇日志实在是我的荣幸。

这道题目我大概思考了一下,感觉除了程序模拟以外似乎没有什么靠谱的数学算法,加上今天上班也没工夫去算,回来能看到您计算的结果真是太好了。

模拟的结果说实话跟我估测的差距很大
令我意外的是:
1,8人模型概率居然如此之高。
不过仔细想了一下,考虑极端情况,A通知完B后,B去通知的每一个人都是A刚通知过的,这样A就一直在给新人打电话,不会停止,这样反而会增加全通知到的可能性。
这样看来8人还想通知不全,只能期冀于A通知BCD三人后,再去联络EFG三人均已知的循环圈了了,概率相当之小。
2,A和其他人的次数居然相差如此之多。
开始我认为A会比其他人多2次左右,这个数字随着人数增多而逐渐平均化,现在看来我大错特错,人数越多,这个初始条件的放大就越夸张,到了100人时居然会高出一倍有余。这一点是反我的直觉的。
3,8人模型居然如此冗余——其他所有人平均只会打3.24个电话,考虑到3个是保底数值,可见每个人真正通知到的人只有0.24个么orz。
4,总期望的时间很有趣,仿佛是log2(X)的两倍多一些,照这样推测250人大概需要用时18秒左右。

另外,昨天有朋友跟我反应了一下题目中可能出现的一个谬误:CD两人均开始打电话时,按照题意可能会互相打电话,这样虽然结果是双方都是已知,但总有一人违反了“只给未知人打电话”的规则,不过似乎也是极端情况,不大会影响处理,您看怎么规定这种现象为好?

往生已逝
2013.7.13
2013-07-13 Sat 19:31 | URL | 往生已逝 [ 编辑 ]
往生大您好,

关于A和其他人的平均次数相差这点我当时做完实验没有仔细考虑相差这么大是否合理。我觉得主要导致差异的地方在于其他人被通知到的时间有早有晚。如果很早被通知到那么打电话的数量就比较大,而晚被通知的人基本就是打3个电话就停止了。然后在取平均的时候就把平均打电话的数量拉下来了。而A永远处在第一个打电话的位置所以他的平均时间就相对于别人要长很多。

关于那个小bug的问题现在我的程序是就是简单的按照两人都获得对方已知的信息处理的。过两天到周二的时候我再弄一下程序统计一下这种情况的出现次数,看会不会的结果有比较大的影响,周一毕业论文交稿先忙一阵去
2013-07-14 Sun 21:18 | URL | pipikaqiu [ 编辑 ]

发表留言















只对管理员显示

引用

| 主页 |