首页 > 试题广场 >

无聊的牛牛和羊羊

[编程题]无聊的牛牛和羊羊
  • 热度指数:53 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
牛牛和羊羊非常无聊.他们有n + m个共同朋友,他们中有n个是无聊的,m个是不无聊的。每个小时牛牛和羊羊随机选择两个不同的朋友A和B.(如果存在多种可能的pair(A, B),任意一个被选到的概率相同。),然后牛牛会和朋友A进行交谈,羊羊会和朋友B进行交谈。在交谈之后,如果被选择的朋友之前不是无聊会变得无聊。现在你需要计算让所有朋友变得无聊所需要的时间的期望值。

输入描述:
输入包括两个整数n 和 m(1 ≤ n, m ≤ 50)


输出描述:
输出一个实数,表示需要时间的期望值,四舍五入保留一位小数。
示例1

输入

2 1

输出

1.5
/***
*这个题完全就是数学题了吧。。。
*/
importjava.util.Scanner;
 
publicclassMain {
    publicstaticvoidmain(String[] args) {
        Scanner scanner = newScanner(System.in);
        while(scanner.hasNext()) {
            intn = scanner.nextInt();
            intm = scanner.nextInt();
            float[] dp = newfloat[m + 1];
            if(m == 0) {
                System.out.println(0);
                return;
            }
            if(m == 1) {
                floatres = (n + 1) / 2.0f;  //和下面的不同,此处已知m=1
                String r = String.format("%.1f", res);
                System.out.println(r);
                return;
            }
            dp[1] = (n+ m) / 2.0f;  //注意此处
            for(inti = 2; i <= m; i++) {
                dp[i] = p1(m + n-i, i) + p2(m + n -i, i) * (dp[i-1] + 1) + p3(m + n -i, i) * (dp[i-2] + 1);
            }
            String r = String.format("%.1f", dp[m]);
            System.out.println(r);
        }
 
    }
 
    privatestaticfloatp1(intn, intm) {
        intc1 = n * (n-1) / 2;
        ints = (n + m) * (n + m -1) / 2;
        floatres = c1 * 1.0f / (s - c1);
        returnres;
    }
 
    privatestaticfloatp2(intn, intm) {
        intc1 = n * (n-1) / 2;
        intc2 = n * m;
        ints = (n + m) * (n + m -1) / 2;
        floatres = c2 * 1.0f / (s - c1);
        returnres;
    }
 
    privatestaticfloatp3(intn, intm) {
        intc1 = n * (n-1) / 2;
        intc3 = m * (m  -1) / 2;
        ints = (n + m) * (n + m -1) / 2;
        floatres = c3 * 1.0f / (s - c1);
        returnres;
    }
 
}

发表于 2018-08-31 13:01:27 回复(1)