转跳到内容

不妙的数学算法挑战


mamamama

只显示该作者

只有该作者的内容显示中。 返回到主题

推荐贴

题面背景虚构仅供娱乐

mama 最近在凹一个无良制作人做出来的奇怪游戏。其中有一个地城的地图如图所示,

有一座起始之岛和一座结束之岛以及十二座浮岛,岛屿间通过浮桥连接(包括连向起始之岛和结束之岛的桥)

mama 只要成功从起始之岛走到结束之岛就可以胜利通关

每次进入地城的时候,就会重新生成一次地图,岛屿都在原本的位置,但每座浮桥只有50%的概率存在(彼此独立判定)

为啥说制作人无良呢,因为制作人就是粗暴地设置了一个出现概率,而没有保证一定能通关

那么 mama 好奇一个问题,对于这样一个随机生成的地城,可以通关的概率是多少?

image.png.1fa868741ba861a9bf55ece5fe393881.png

我知道写个程序一瞬间就可以暴力枚举完,但是我画个更大的地图会快乐吗:mx014:

第一次发帖发点红包(这……这还是第一次啊

,由mamamama修改
注释
摸鱼奇才咖啡喵 摸鱼奇才咖啡喵 70.00节操 素许久不见的数学挑战题
链接到点评
2 分钟前, 抹消思绪 说道:

比起这个我好奇另一个问题,已知某个浮桥状况时如何快速确定是否连通,包括数据表示和算法。:mx051:

直接维护所有的连通集合,初始时每个岛对应一个集合,依次把存在的边两侧的集合合并就行(如果是同一个集合就不用处理了)

最后会得到若干个集合,在同一个集合里的点就是互相连通的

mamamama在看最新一期的月报时想起以前的月报一时兴起前往整理,发现以前留下的私房钱 8节操

链接到点评
1 小时前, 苍云静岳 说道:

因为量级比较小,建议考虑以下解法:

求和:缺12块的概率(1/2^12)*已知缺12块基础上可通关的条件概率(0)+缺11块的概率*缺11块可通关的概率+...+缺0块的概率*缺0块可通关的概率(1)

缺12/11/10/9块通关条件概率为0,缺0/1/2块通关条件概率为1。剩下345678的摆摆基本都有规律的。

具体的懒得算了。

另一个思路是从3*1到3*2一直到3*4考虑这个问题(3*n)的通解,具体的也懒得算了。

分类讨论或者容斥确实是个不错的思路:YangTuo_2:

不过……

3 小时前, mamamama 说道:

我画个更大的地图会快乐吗:mx014:

 

链接到点评
2 小时前, 苍云静岳 说道:

那么m*2的地图通关概率为(1-1/2^m)*p

这个好像不太对呢,浮岛间的竖边也是会影响连通性的,如果硬要算的话要对 m 也递推会好点

首先把概率转成计数问题,最后除掉一个 2^边数 变回概率

假设 f(m) 是有 条竖边的时候没有连通的方案数,那么枚举最后有连续有 k 条竖边,这些浮岛要么全部向左连边要么全部向右连边

大概就是 2*2^(k+1)-1 这么多的方案数,因此应该是 f(m)=sum( f(m-k-1) * (2*2^(k+1)-1) )

可能有点细节或者边界错误之类的

如果再加一列的话只会变得更复杂,我感觉这样不太可做

 

另外

7 小时前, mamamama 说道:

画个更大的地图

这句话并不代表地图具有“一般性”哦,它依然是具有很强的特殊性的,所以建议还是从原图出发呢:mx051:

我过几天如果没人解出来并且我还记得会再给点提示

mamamama路上捡到一枚勋章,然后把它交给了拍着手跳来跳去喊着“咸鱼”的萌妹子,获得4节操。

链接到点评
31 分钟前, fangaa 说道:

我个人见到概率就头疼,所以想了个不需要算概率的取巧方法:
先定义f(x,y)是这个问题x行y列时的答案,那么楼主想要的答案就是f(4,4)。
然后假设有一艘体积极大的船自上而下想要通过,若两岛之间有桥则不能通过。那么人能通过和船能通过刚好互斥,正巧桥存在的概率都是50%,也就是说f(x,y)+f(y,x)=1。
那对于这个例子f(4,4)=0.5。

 

正解:mx017:

链接到点评
  • 骚男锁定了本主题
游客
此主题已关闭。
×
×
  • 新建...

重要消息

为使您更好地使用该站点,请仔细阅读以下内容: 使用条款