java实现第五届蓝桥杯绳圈

绳圈

题目描述

今有 100 根绳子，当然会有 200 个绳头。

如果任意取绳头两两配对，把所有绳头都打结连接起来。最后会形成若干个绳圈（不考虑是否套在一起）。

我们的问题是：请计算最后将形成多少个绳圈的概率最大？

注意：结果是一个整数，请通过浏览器提交该数字。不要填写多余的内容。

public class Main {

    public static void main(String[] args) {

        double[][] dp = new double[101][101];

        dp[1][1] = 1;  //当前只有一根绳子，只能形成一个绳圈，且概率为1

        for(int i = 2;i < 101;i++) {  //绳子数

            for(int j = 1;j < 101;j++) {  //绳圈数

                if(j > i)  //此时的情形不可能出现,即此时概率为0

                    continue;

                dp[i][j] = dp[i - 1][j]*(2*i - 2) / (2*i - 1) + dp[i][j -1]/(2*i - 1);

            }

        }

        double max = 0;

        int maxI = 0;

        for(int i  = 1;i < 101;i++) {

            if(max < dp[100][i]) {

                max = dp[100][i];

                maxI = i;

            }

        }

        System.out.println(maxI);

    }

}

巴特西

java实现第五届蓝桥杯绳圈

最新文章

热门文章