这道题你会做吗?codeforces程序算法网的一道入门级题

概述：本文翻译了NB程序员们常去的国际知名的算法竞赛网站codeforces的第259期的一道入门级算法题,程序员朋友,这道题你会做么?

代码测试需求：

程序响应时间限制：1秒以内

程序内存限制：256M以内

输入方法：标准输入

输出方法：标准输出

《彩虹小马》里的女孩Twilight Sparkle与她的朋友Rainbow Dash，Apple Jack 以及 Flutter Shy在一起玩骰子游戏，但是她一直都在输。回到城堡以后，Twilight Sparkle对游戏里使用的骰子很感兴趣。

骰子一共有m个面，第一面有一个点，第二面有两个点，以此类推，第m个面有m个点。Twilight Sparkle很清楚的知道，每当她丢一次骰子，都有可能随机出现其中的一个面。并且她还知道，每次扔出的概率都是独立的。现在请你帮助她计算下，当她扔出n次骰子后，所得的最大的点的预期值是多少？

输入值：包含2个整数，m和n （1 ≤ m, n ≤ 105)。

输出值：输出的结果对应于最大的点的预期值，结果误差在10-4范围内都视为正确答案。

示例，比如在假定m=2，n=2的情况下（即骰子只有两面，扔2次的情况）：

1. 你第一次扔了1个1，第二次扔了1个2，最大结果为2。
2. 你第一次扔了1个1，第二次扔了1个1，最大结果为1。
3. 你第一次扔了1个2，第二次扔了1个1，最大结果为2。
4. 你第一次扔了1个2，第二次扔了1个2，最大结果为2。

由于出现上述四种情况的概率都为0.25，那么预期值为

（2 + 1 + 2 + 2）* 0.25 = 7/4

一些输出结果：

Input

6 1

Output

3.500000000000

 

Input

6 3

Output

4.958333333333

 

Input

2 2

Output

1.750000000000

本文翻译自Little Pony and Expected Maximum

 

评论

2 楼 qq1376888124 2014-08-05  

joseph830727 写道

public void cal(int m, int n){
		long b = System.currentTimeMillis();
		double sum = 0;
		for(int i = 1; i <= m; i++){
			if(i == 1){
				sum += 1;
			}else if(i <= m){
				double t = Math.pow(i, n) - Math.pow(i - 1, n);
				sum += t * i;
			}
		}
		double result = sum / Math.pow(m, n);
		long e = System.currentTimeMillis();
		System.out.println(result);
		System.out.println(e - b);
	}

   

1 楼 joseph830727 2014-08-05  

public void cal(int m, int n){
		long b = System.currentTimeMillis();
		double sum = 0;
		for(int i = 1; i <= m; i++){
			if(i == 1){
				sum += 1;
			}else if(i <= m){
				double t = Math.pow(i, n) - Math.pow(i - 1, n);
				sum += t * i;
			}
		}
		double result = sum / Math.pow(m, n);
		long e = System.currentTimeMillis();
		System.out.println(result);
		System.out.println(e - b);
	}