| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2333 人关注过本帖, 1 人收藏
标题:题目,绳圈,小弟没思路,
只看楼主 加入收藏
ljx小子
Rank: 8Rank: 8
来 自:星星
等 级:蝙蝠侠
威 望:2
帖 子:222
专家分:916
注 册:2013-10-7
收藏
得分:5 
个人想法:
刚开始拿一个绳,开始找绳头,会有两种情况:1、和自己本省另一个绳头结合概率1/199和其他198/199。。。因此概率大的肯定是和别的绳子结合但总会有某一时刻使得
198*197*196……/199*198*197*196……小于等于1/199这样的条件下跳出,在次重复选择,直到可选绳头数为0

。。。。。。。。。。。
2014-03-25 20:12
pangshch
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:2
帖 子:443
专家分:1966
注 册:2013-4-9
收藏
得分:0 
以下是引用loveClangage在2014-3-25 19:02:13的发言:

我觉得,不是这个,怎么有可能每条绳头都这么巧成环,
我也不是很明白, 希望有人指正,


[ 本帖最后由 pangshch 于 2014-3-27 10:13 编辑 ]
2014-03-25 22:33
loveClangage
Rank: 8Rank: 8
来 自:广东云浮
等 级:蝙蝠侠
帖 子:326
专家分:891
注 册:2013-8-23
收藏
得分:0 
回复 12楼 pangshch
题目是求:
    我们的问题是:请计算最后将形成多少个绳圈的概率最大
多少个圈?那肯定是个整数吧

编写的程序,不能改变世界,却可以改变自己...
2014-03-26 19:44
wsj3000
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:78
专家分:161
注 册:2009-8-4
收藏
得分:0 
汗。。。。题目不严密啦。。。。不要被圈圈迷倒了,关键不是圈圈,而是选绳子。
---------------------------------------------------------------------------
过程是这样的,选绳子,圈圈子,最后都成了圈圈。
其实这个过程可以修改一下,是等效的。
选绳子,放一堆,最后把每一堆绳子圈圈子(因为任意个绳子都可以成一个圈圈)。
因为只计算圈圈个数(也就是堆的个数),所以圈圈根本不重要,分堆后,堆数就是圈圈数。
最终,问题变成:
100个绳子,任意选N个,知道选完为止,问多少堆的概率最大?
--------------------------------------------------------------
绳子有编号吗?有编号的话,那就。。。。。自己想吧
2014-03-27 14:46
loveClangage
Rank: 8Rank: 8
来 自:广东云浮
等 级:蝙蝠侠
帖 子:326
专家分:891
注 册:2013-8-23
收藏
得分:0 
回复 14楼 wsj3000
100个对100来打圈啊

编写的程序,不能改变世界,却可以改变自己...
2014-03-27 15:30
wsj3000
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:78
专家分:161
注 册:2009-8-4
收藏
得分:0 
回复 15楼 loveClangage
没懂你什么意思,一跟绳子,两个头,接起来就是一个圈,100根绳子,结成1跟长绳,最后两头接起来,也是一个圈。所以,N根绳子,都可以组成一个圈圈。
--------------------------------------
在一次圈圈过程中,最后所有绳子都变成圈圈了,这是把所有绳子的圈圈解开,每个圈圈堆成一堆,堆数就是圈圈数,所以我说选堆就是圈圈子,没区别。
收到的鲜花
  • _c_c2014-03-27 23:38 送鲜花  1朵   附言:我很赞同
2014-03-27 15:37
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
题目的描述已经够清晰了,我不知道是什么把各位绕在了里面。下面我再细化一下题目中包含的条件。

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生成过各种初始绳子数量下最终绳圈数量的概率分布,这是一条从原点开始迅速上升,到达极值后开始迅速下降之后无限接近数轴的曲线。

随着初始绳子数量的增大,极值点所对应的坐标逐渐右移。

这么规律的行为使我认定一定存在一个极值与绳数的优美的映射关系,可惜我的水平有限,也没有足够的时间容我分析它。
收到的鲜花
  • _c_c2014-03-27 23:39 送鲜花  1朵   附言:我很赞同
  • 神机军师2014-03-28 11:11 送鲜花  5朵   附言:我很赞同,大爱斑竹啊

重剑无锋,大巧不工
2014-03-27 17:28
蚕头燕尾
Rank: 10Rank: 10Rank: 10
来 自:Gryffindo
等 级:贵宾
威 望:12
帖 子:734
专家分:1546
注 册:2013-3-24
收藏
得分:0 
楼主能给说下最后杨大哥的答案对不对么?


学习编程,为的是表达自己的思想,而不是被别人的思想所禁锢。要先明白自己想干嘛,而不要先问别人让你干嘛。               

                                                                                                                    Black Cat      Hello Tomorrow~
2014-03-27 20:50
mary92
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2014-3-28
收藏
得分:0 
我的思路如下:
100条绳最多可以形成100个圈,最少一个圈,不可能形成不成全的连接,
 圈数      每个圈的构成                        解释及说明
  1         100=100          ,其中1代表形成圈的数量,100代表该圈由100条绳连接而成;
  2         1+99=100,2+98=100,3+97=100,...,50+50=100,共有50种分解(即将100分解为两个正整数相加的所有可能分解方法);
  3         a+b+c=100              ,即求将100分解为三个 “合理”整数相加的的所有可能的分解方法;
  .
  .   
  .
 100     1+1+1+...+1=100           仅有一种分解;

此外如果考虑一个“确定”圈的不同连接方式(比如说由2条绳构成的圈有2种连接方式),问题复杂度将进一步提高,
2014-03-28 00:42
mary92
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2014-3-28
收藏
得分:0 
对于“确定”圈的连接方式数解法如下:

假设一“确定”圈由n条绳构成,每条绳一端标记为0,一端标记1,则可以设定一n位2进制数与该“确定”圈的一连接方式相对应。按顺时针方向仅读入每条绳的“首遇”端标记并置于对应2进制位。如n=3,“首遇”端标记序列为 1 1 1 则对应3位二进制数1 1 1;故  一由n条绳构成的“确定”圈有2的n次幂种连接方式。
2014-03-28 01:13
快速回复:题目,绳圈,小弟没思路,
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020159 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved