找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: wjjal
收起左侧

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

[复制链接]

47

主题

2

精华

379

积分

高级会员

Rank: 3Rank: 3

积分
379
 楼主| 发表于 3-2-2015 04:39 AM | 显示全部楼层
wjjal 发表于 3-2-2015 03:48 AM
上面计算的期望是有放回的,比如掷骰子,扔出6的概率是1/6,那么扔出6期望的次数是6,这种是无放回的,有放 ...

稍微改了下代码,改成有放回抽样,还是AC不了。。。求大牛指点
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];
                        double remain = (i - 1) * (i - 2) / 2 - dp[i - 1] + i - 1;
                        double need = i - 1;
                        int step = 1;
                        double sum = 0;
                        while (remain >= need) {
                                double got = (1 - sum) * need / remain;
                                sum += got;
                                dp【i】 += got * step;
                                step++;
                                remain--;
                        }
                }
                return (int) Math.ceil(dp[n]);
        }
发表于 3-2-2015 11:34 AM | 显示全部楼层
wjjal 发表于 3-2-2015 04:39 AM
稍微改了下代码,改成有放回抽样,还是AC不了。。。求大牛指点
public int connectThem(int n) {
                dou ...

why ceil
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

47

主题

2

精华

379

积分

高级会员

Rank: 3Rank: 3

积分
379
 楼主| 发表于 3-2-2015 08:34 PM | 显示全部楼层

不是应该上取整吗?求曹神指点。。。边数肯定是整数啊,我查网上公式,有用round的,不理智为啥四舍五入,不过我照抄的计算公式也没AC。。。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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