题目的描述已经够清晰了,我不知道是什么把各位绕在了里面。下面我再细化一下题目中包含的条件。
1.绳子没有编号,所有的绳子都视为一样(亦没有长短之分,这个条件很重要)。
2.绳圈不考虑大小之分。只要沿一个绳头沿着连接的绳子能走回到起始的位置就是一个圈 。
3.打结的过程是随机取两个绳头系在一起。重复这一过程直到没有结可打。
最终的结果是这些绳子形成若干个圈。
由于打结的过程是随机的,所以每一次从所有的绳子都独立存在到打完所有的结后形成的圈数都不一定相同。当然即使形成的圈数相同,可能圈的形状也不同(比如4根绳子形成的两个圈,可以是三根成一个圈,一根单独成圈;或者两根成一个圈,另两根成一个圈),但请注意,形状不在这个题目的考虑范围之内。题目只是问最后形成多少个圈的概率最大。
分析这个题目先从这个打结的过程入手。
设有N根绳子。这时有2N个绳头。
我们具像化这个过程。
先从这2N个绳头里取一个出来(由于绳子视为一样,所以当前这2N个绳头没有区别,这时不必考虑取某个绳头的概率,或者说它们概率都一样)。
然后再从剩下的2N-1个绳头中取一个出来,与之前取出的系在一起。
系完之后将可能出现两种结果:
1、后取的绳头与先取的绳头属于同一根绳子。这时会形成一个圈。
2、后邓的绳头与先取的绳头不属于同一根绳子。这时不会形成圈。
不管结果是形成圈还是不形成圈,打完一次结之后剩下的绳子数量都会比之前减少1。(要么一根绳子形成了圈,要么两根绳子系在一起形成一根更长的绳子。再次提醒,题目关注的是圈数,对绳子的长度是忽视的)
现在说说上面两种结果出现的概率各是多少。
对于情况1,要形成一个圈,第二次取的绳头必须得是和第一次取的绳头属于同一根绳子。而每根绳子有且只有两个绳头,所以剩余的2N-1个绳头中只有一个与第一次取的绳头属于同一根绳子。
所以形成一个圈的概率是 1/(2N-1)
对于情况2,它是情况1的补集,所以不形成圈的概率是 1 - 1/(2N-1)
在上面分析的基础上我们来考虑这样的中间状态。
假设经过若干次打结后剩余i根绳子并形成了j个圈的概率为f(i, j)。
这时我们再打一次结,剩余的绳子数将是i-1。
这次打结形成一个圈的概率是1/(2i-1),不形成圈的概率是1 - 1/(2i-1)
这时,形成j个圈的情况有以下两种可能:
1.在这次打结之前已经有j个圈,这次打结没有形成圈。
2.在这次打结之前有j-1个圈,这次打结形成一个圈。
由此,这时形成j个圈的概率是
f(i-1, j) = f(i, j) * (1 - 1/(2i-1)) + f(i, j-1) * 1/(2i-1)
最后再说说f(i, j)的意义。
f(N,j)表示初始时存在j个圈的概率。
f(i,0)表示有i根绳子时没有圈的概率。
对于没有圈的情况只能形成于之前一直没有形成圈,并且这次打结也没有形成圈这一过程。
所以f(i,0) = f(i + 1, 0) * (1 - 1/(2i-1))
而初始状态下(一个结都还没打时)
f(N,0) = 1
f(N,j) = 0 (j > 0)
f(0,j)表示绳头全部打完后,有j个圈的概率。
题目要的就是概率值最大的f(0,j)所对应的这个j。
以上就是我解这题的全部分析过程。其中用到的概率知识很简单。代码就不重复贴了。
我用matlab生成过各种初始绳子数量下最终绳圈数量的概率分布,这是一条从原点开始迅速上升,到达极值后开始迅速下降之后无限接近数轴的曲线。
随着初始绳子数量的增大,极值点所对应的坐标逐渐右移。
这么规律的行为使我认定一定存在一个极值与绳数的优美的映射关系,可惜我的水平有限,也没有足够的时间容我分析它。