找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2376|回复: 6
收起左侧

[讨论] 38题我的一点思路

[复制链接]

47

主题

2

精华

379

积分

高级会员

Rank: 3Rank: 3

积分
379
发表于 3-2-2015 03:42 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
我是通过以下公式来递推的:
E(n)=E(n-1)+((n-1)*(n-2)/2-E(n-1)+(n-1))/(n-1);

n个点连通的期望边数=n-1个点连通的期望边数+1/连接n-1个点的连通分量和这第n个点的关键边被选中的概率

有n-1条关键边(被选择就连通了),剩余的变数为n-1个点可构建的总边数(n-1)*(n-2)/2减去构建n-1条边连通分量已搭建的边E(n-1),所以,概率为(n-1)/((n-1)*(n-2)/2-E(n-1)+(n-1))


我的代码如下:
public int connectThem(int n) {
                double dp[] = new double[n + 1];
                dp[2] = 1;
                for (int i = 3; i <= n; i++) {
                        dp【i】 = dp[i - 1] + ((i - 1) * (i - 2) / 2 - dp[i - 1] + (i - 1))
                                        / (i - 1);
                }
                return (int) Math.ceil(dp[n]);
        }


不过没AC,求指正。。。

47

主题

2

精华

379

积分

高级会员

Rank: 3Rank: 3

积分
379
 楼主| 发表于 3-2-2015 03:45 AM | 显示全部楼层
上面计算概率的方式是有放回的,这里是无放回的抽样 所以是不对的。。。

47

主题

2

精华

379

积分

高级会员

Rank: 3Rank: 3

积分
379
 楼主| 发表于 3-2-2015 03:48 AM | 显示全部楼层
上面计算的期望是有放回的,比如掷骰子,扔出6的概率是1/6,那么扔出6期望的次数是6,这种是无放回的,有放回的比如3个苹果其中一个青苹果两个红苹果,拿出青苹果平均需要拿2次,而不是3次,因为拿出不放回。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表